Inspired by the smoothing barrier augmented Lagrangian function in Liu et al. (Math Methods Oper Res 96(3):351-382, 2022), we propose a primal-dual interior-point relaxation algorithm for second-order cone programming, called IPRSOCP. Two features of the IPRSOCP algorithm are as follows. One is that the iterative points of the proposed algorithm need not lie inside the interior region, convening the use of warmstart. The other is that an explicit form of the Schur complementmatrix is explored such that the low-rank structure of the Schur complement matrix can be used to improve numerical stability and efficiency. Under suitable assumptions, it is shown that the barrier parameter in the IPRSOCP algorithm tends to zero and the generated sequence of iterations is globally convergent to the solution. Numerical results demonstrate that the IPRSOCP algorithm is competitive with the open-source benchmark solvers, SeDuMi, SDPT3, and ECOS, in terms of robustness and efficiency.

In this paper, we propose a stochastic Levenberg-Marquardt algorithm based on trust region for stochastic nonlinear least squares problems, where the stochastic Jacobians and gradients are used instead of the exact Jacobians and gradients. We show that the estimates and models of the objective function are probabilistically accurate if the number of samples at each iteration is chosen appropriately. Further, we prove that at least one accumulation point of the sequence generated by the proposed algorithm is a stationary point of the objective function with probability one.

We consider a fluid queue with working vacations. Once the buffer becomes empty during the normal working period, the buffer will enter a working vacation period during which the outflow rate of fluids will be switched to a lower rate than that in normal working period. After this working vacation period, if the buffer is non-empty, the outflow rate of fluids will be switched to normal rate immediately; otherwise, the buffer will enter another working vacation until the buffer is non-empty after one working vacation. For such a fluid queue, based on the utility function, we analyze the strategic behavior of the fluids, regarding the joining/balking dilemma, under the fully observable case, almost observable case and fully unobservable case. Furthermore, the expected equilibrium social benefits under different cases are discussed. At last, the optimal social benefit strategy is analyzed and the inefficiency of the equilibrium strategies is quantified via the Price of Anarchy (PoA) measure.

This paper is devoted to the study of optimality to a nonsmooth vector equilibrium problem with set, cone and equality constraints. Using a new approach for the Karush-Kuhn-Tucker-type efficiency condition to such problem, we introduce the constraint qualification of the (CQ1) and (CQ2) types via Clarke’s subdifferentials and Michel-Penot’s subdifferentials. We next provide, by using these subdifferentials, some Karush-Kuhn-Tucker (KKT for short) type necessary optimality conditions for efficiency to such problem. Under suitable assumptions on the generalized quasiconvexity/the ?-convexity, some KKT-type necessary optimality conditions become sufficient optimality conditions. Additionally, we provide some KKT-type necessary and sufficient optimality conditions for an efficient solution which does not require that the ordering cone in the objective space has a nonempty interior to those problems. Some illustrative examples are also proposed for our findings.

Companies use different existing products or services to create probabilistic goods. When consumers purchase goods, they calculate their net utility based on the price of the product and thus determine their purchase behaviour. We propose a model related to opaque sales, through which we can determine the optimal price of multiple products and calculate the average profit of the firm and the average net utility of the consumer. Based on the above model, we also present a condition that allows the company to profit from all products when the consumer evaluation presents a particular distribution. This model can be used to help enterprises develop the optimal pricing strategy of products to achieve the desired profit.

This paper considers the single-machine scheduling problem with slack due date. The decision needs to determine the optimal job sequence when the due date of jobs is determined. Slack due date means that the due date is equal to its processing time plus a constant, where the constant is the decision variable. The aim is to assign the slack due date and minimize the objective function. The objective function includes the early work, late work and slack due dates. In this paper, we discuss two problems with slack due date. For the first problem, we address the range of slack due date by cost coefficients, and design a dynamic programming algorithm to solve the proposed problem. It is proved that the optimal solution can be obtained in O(n³P³ log n) time. For the latter problem, we address the time-window assignment problem, and present a dynamic programming algorithm by determining the rang of due date of time window in O(n⁴P⁵ log n(1 + P)) time. Finally, a numerical example is presented to illustrate the feasibility of these algorithms.

Given a connected graph $G=(V, E)$, a rainbow disconnection $k$-coloring of $G$ is a $k$-edge coloring of $G$ such that for each pair of vertices $u, v \in V$, there is a rainbow (edge) cut of $u, v$, which is a subset $\mathrm{RC}(u, v) \subseteq E$ such that $u, v$ are disconnected in $G \backslash \mathrm{RC}(u, v)$ and that all edges in $\mathrm{RC}(u, v)$ have different colors. The minimum integer $k$ such that $G$ admits a rainbow disconnection $k$-coloring is the rainbow disconnection number of $G$, denoted by $\operatorname{rd}(G)$. It has been shown that $\operatorname{rd}(G)$ is closely related to the maximum number $\lambda^{+}(G)$ of edge disjoint paths among all pairs of vertices in $G$. In this paper, we propose a polynomial-time algorithm for finding a rainbow disconnection $\operatorname{rd}(G)$-coloring of a 2-tree, a graph $G$ formed by starting with a triangle and then repeatedly adding vertices in such a way that each added vertex is adjacent to two ends of an edge. Moreover, the algorithm shows that $\operatorname{rd}(G)=\lambda^{+}(G)$ if $G$ is a 2-tree. This justifies a conjecture of Bai et al. [MR4385957] in 2-trees, which states that $\operatorname{rd}(G)$ is either $\lambda^{+}(G)$ or $\lambda^{+}(G)+1$ for each graph $G$.

In the face of large-scale datasets in many practical problems, it is an effective method to design approximation algorithms for maximizing a regularized submodular function in a semi-streaming model. In this paper, we study the monotone regularized submodular maximization with a matroid constraint and present a single-pass semistreaming algorithm using multilinear extension function and greedy idea. We show that our algorithm has an approximation ratio of $\left(\frac{(\beta-1)\left(1-\mathrm{e}^{-\alpha}\right)}{\beta+\alpha \beta-\alpha}, \frac{\beta(\beta-1)\left(1-\mathrm{e}^{-\alpha}\right)}{\beta+\alpha \beta-\alpha}\right)$ and a memory of $O(r(M))$, where $r(M)$ is the rank of the matroid and parameters $\alpha, \beta>1$. Specifically, if $\alpha=1.18$ and $\beta=9.784$, our algorithm is ( $0.302,2.955$ )-approximate. If $\alpha=1.257$ and $\beta=3.669$, our algorithm is $(0.2726,1)$-approximate.

For a mean-CVaR model with cardinality constraint, we consider the situation where the true distribution of underlying uncertainty is unknown. We develop a distributionally robust mean-CVaR model with cardinality constraint (DRMCC) and construct the ambiguity set by moment information. We propose a discretization approximation to the moment-based ambiguity set and present the stability analysis of the optimal values and optimal solutions of the resulting discrete optimization problems as the sample size increases. We reformulate the DRMCC model as a bilevel optimization problem. Moreover, we propose a modified bilevel cutting-plane algorithm to solve the DRMCC model. Finally, some preliminary numerical test results are reported. We give the in-sample performance and out-of-sample performance of the DRMCC model.

In this paper, a new notion called E-optimality is proposed by virtue of improvement sets E for uncertain multiobjective optimization problems, which has close connections to many known robustness concepts and can be seen as a unified approach to dealingwithmultiobjectiverobust efficiency. Subsequently,we discuss the existence of E-optimal solutions and obtain existence results under mild assumptions. By means of linear and nonlinear scalarizing functions, some characterizations of E-optimal solutions are well established, respectively. Finally, several examples are given to show the effectiveness of the results.

The extended trust-region subproblem (eTRS)—the trust-region subproblem equipped with some additional linear constraints, has received lots of attention in recent years. As one of the quadratically constrained quadratic programming problems, eTRS can be solved via the methods of general quadratic programs—the semidefinite programming (SDP) relaxation and its related global optimization techniques are the most commonly used instruments. Recently, researchers use second-order cone (SOC) constraints to strengthen SDP, and the speeds of the previous algorithms have been improved. In this paper, we study eTRS from the computational point of view. A class of eTRS is provided, bringing huge computational pressure to the SOC-accelerated algorithms. However, the reformulation linearization technique has extremely promising effect of acceleration. With the two classes of constraints on hand for acceleration, a new branch and bound algorithm is proposed. Numerical experiments show that the new algorithm runs faster than several algorithms in the literature as well as the solver Gurobi for certain types of eTRS.

With wide-spread real-world applications, low-rank and sparse matrix recovery, where the concerned matrix with incomplete data is divided into a low-rank part and a sparse part, recently has attracted significant interest. To solve this structured non-convex optimization problem, we propose a non-monotone alternating Newton-like directional method which essentially updates two blocks of variables associated with the low-rank part using a single step of simple line-search along the Newton-like descent directions and another block of variables associated with the sparse part using a nonmonotone search. In particular, the non-monotone search technique helps our method find a better Newton-like descent direction in the next step. Moreover, we prove the global convergence of the proposed algorithm and discuss the iteration number in given precision under some mild conditions. Finally, computational results show the efficiency of the developed algorithm.

In this paper, we study the extremal geometric measure of quantum entanglement of superposition states of several symmetric pure states with parameters. This problem is equivalent to calculate their minimum entanglement value or maximum entanglement value. We propose the block coordinate descent (BCD) method to calculate the minimum entanglement value and establish its convergence analysis. We propose a gradient projection ascent with min-oracle(GPAM) method to calculate the maximum entanglement value. The subproblems of these two problems are optimization problems with a complex unit spherical constraint. The complex unit sphere is a Riemannian manifold. We propose an inexact Riemannian Newton-CG method to solve this Riemannian optimization problem. The numerical examples are presented to demonstrate the effectiveness of the proposed methods.

In this paper, we construct a bounded rationality function of weakly cooperative equilibrium point of multi-objective population games (WCEPOMPG) by virtue of nonlinear scalarization function. We investigate lower semicontinuity of the bounded rationality function and present a relationship between the level set of zero of the bounded rationality function and WCEPOMPG. By applying these properties, we first consider the generalized well-posedness for WCEPOMPG in the setting of multiplevalued assumption of solution set. Then, we obtain the uniqueness of solution set on a dense residual set with the stable assumption of vector payoff functions. Moreover, we investigate the well-posedness of WCEPOMPG on the dense residual set. As a special case, we obtain the generalized well-posedness and well-posedness of cooperative equilibria for single-objective population games, respectively.

Given a set of clients and a set of facilities with different priority levels in a metric space, the Budgeted Priority p-Median problem aims to open a subset of facilities and connect each client to an opened facility with the same or a higher priority level, such that the number of opened facilities associated with each priority level is no more than a given upper limit, and the sum of the client-connection costs is minimized.In this paper, we present a data reduction-based approach for limiting the solution search space of the Budgeted Priority $p$-Median problem, which yields a $(1+ \varepsilon$ )-approximation algorithm running in $O(n d \log n)+\left(p \varepsilon^{-1}\right)^{p \varepsilon^{-O(1)}} n^{O(1)}$ time in $d$ dimensional Euclidean space, where $n$ is the size of the input instance and $p$ is the maximal number of opened facilities. The previous best approximation ratio for this problem obtained in the same time is $(3+\varepsilon)$.

The problem of maximizing submodular functions with constraints has attracted widespread attention in the past few decades. In recent years, the extensions of submodular functions were studied, such as lattice submodular functions, diminishing return submodular (DR-submodular) functions and $k$-submodular functions. A $k$ submodular function is a generalization of a submodular function to $k$ dimensions. Many machine learning problems can be cast as $k$-submodular maximization problems, for example, influence maximization with $k$ kinds of topics and sensor placement with $k$ kinds of sensors. Recently, the unprecedented growth in modern datasets makes it necessary to design streaming algorithms. This paper investigates the problem of maximizing a nonnegative normalized $k$-submodular function with the multi-knapsack constraint (also called the $d$-knapsack constraint) in the streaming model. To address this problem, we design an efficient streaming algorithm that runs in one pass, stores at most $O\left(\frac{b \log b}{\varepsilon}\right)$ elements and queries at most $O\left(\frac{d k \log b}{\varepsilon}\right)$ per element where $b$ is a constant after the normalization of the problem. This streaming algorithm also can achieve a $\left(\frac{1}{2(1+d)}-\varepsilon\right)$-approximation when the objective function $f$ is monotone and $\left(\frac{1}{3+2 d}-\varepsilon\right)$-approximation when the objective function $f$ is non-monotone.