Asia-Pacific Journal of Operational Research

In this paper, we conduct a convergence rate analysis of the augmented Lagrangian method with a practical relative error criterion designed in Eckstein and Silva [Mathematical Programming, 141, 319–348 (2013)] for convex nonlinear programming problems. We show that under a mild local error bound condition, this method admits locally a Q-linear rate of convergence. More importantly, we show that the modulus of the convergence rate is inversely proportional to the penalty parameter. That is, an asymptotically superlinear convergence is obtained if the penalty parameter used in the algorithm is increasing to infinity, or an arbitrarily Q-linear rate of convergence can be guaranteed if the penalty parameter is fixed but it is sufficiently large. Besides, as a byproduct, the convergence, as well as the convergence rate, of the distance from the primal sequence to the solution set of the problem is obtained.

This work analyzes the alternating minimization (AM) method for solving double sparsity constrained minimization problem, where the decision variable vector is split into two blocks. The objective function is a separable smooth function in terms of the two blocks. We analyze the convergence of the method for the non-convex objective function and prove a rate of convergence of the norms of the partial gradient mappings. Then, we establish a non-asymptotic sub-linear rate of convergence under the assumption of convexity and the Lipschitz continuity of the gradient of the objective function. To solve the sub-problems of the AM method, we adopt the so-called iterative thresholding method and study their analytical properties. Finally, some future works are discussed.

This paper is devoted to study the Painlevé–Kuratowski convergence of solution sets for perturbed symmetric set-valued quasi-equilibrium problems (SSQEP)${}_n$ via improvement sets. By virtue of the oriented distance function, the sufficient conditions of Painlevé–Kuratowski convergence of efficient solution sets for (SSQEP)${}_n$ are obtained through a new nonlinear scalarization technical. Then, under ${\mathrm{\Gamma }}_C$-convergence of set-valued mappings, the Painlevé–Kuratowski convergence of weak efficient solution sets for (SSQEP)${}_n$ is discussed. What’s more, with suitable convergence assumptions, we also establish the sufficient conditions of lower Painlevé–Kuratowski convergence of Borwein proper efficient solution sets for (SSQEP)${}_n$ under improvement sets. Some interesting examples are formulated to illustrate the significance of the main results.

Stochastic optimization models based on risk-averse measures are of essential importance in financial management and business operations. This paper studies new algorithms for a popular class of these models, namely, the mean-deviation models in multistage decision making under uncertainty. It is argued that these types of problems enjoy a scenario-decomposable structure, which could be utilized in an efficient progressive hedging procedure. In case that linkage constraints arise in reformulations of the original problem, a Lagrange progressive hedging algorithm could be utilized to solve the reformulated problem. Convergence results of the algorithms are obtained based on the recent development of the Lagrangian form of stochastic variational inequalities. Numerical results are provided to show the effectiveness of the proposed algorithms.

As a classic NP-hard problem in machine learning and computational geometry, the $k$-means problem aims to partition a data point set into $k$ clusters such that the sum of the squared distance from each point to its nearest center is minimized. The $k$-means problem with penalties, denoted by $k$-MPWP, generalizing the $k$-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of $k$-MPWP and propose a parallel seeding algorithm for $k$-MPWP along with the corresponding theoretical analysis.

This paper addresses a class of generalized tensor complementarity problems (GTCPs) over a polyhedral cone. As a new generalization of the well-studied tensor complementarity problems (TCPs) in the literature, we first show the nonemptiness of the solution set of GTCPs when the involved tensor is cone ER. Then, we study bounds of solutions, and in addition to deriving a Hölderian local error bound of the problem under consideration. Finally, we reformulate GTCPs over a polyhedral cone as a system of nonlinear equations, which is helpful to employ the Levenberg–Marquardt algorithm for finding a solution of the problem. Some preliminary numerical results show that such an algorithm is efficient for GTCPs.

H-spectra of adjacency tensor, Laplacian tensor, and signless Laplacian tensor are important tools for revealing good geometric structures of the corresponding hypergraph. It is meaningful to compute H-spectra for some special $k$-uniform hypergraphs. For an odd-uniform loose path of length three, the Laplacian H-spectrum has been studied. In this paper, we compute all signless Laplacian H-eigenvalues for the class of loose paths. We show that the number of H-spectrum of signless Laplacian tensor for an odd(even)-uniform loose path with length three is $7$($13$). Some numerical results are given to show the efficiency of our method. Especially, the numerical results show that the H-spectrum is convergent when $k$ goes to infinity. Finally, we present a conjecture that the signless Laplacian H-spectrum converges to $\{1,1.5,2\}$ ($\{0,1,1.5,2\}$) for odd (even)-uniform loose path of length three.

In this paper, we explore some geometric properties of the cones in terms of extreme rays, exposed rays, the exposed face and the maximal face. To this end, we first show that all copositive tensors orthogonal to the generating tensor of the exposed ray in completely positive tensor cone construct a maximal face of the copositive tensor cone, then give a characterization on the maximal face of the copositive tensor cone. Third, we show that each extreme ray of the completely positive tensor cone is an exposed ray in the even order case. Finally, we give a lower bound and an upper bound for the maximal face of the completely positive tensor cone.

In recent years, several convergent variants of the multi-block alternating direction method of multipliers (ADMM) have been proposed for solving the convex quadratic semidefinite programming via its dual, which is inherently a $3$-block separable convex optimization problem with coupled linear constraints. Among these multi-block ADMM-type algorithms, the modified $3$-block ADMM in [Chang, XK, SY Liu and X Li (2016). Modified alternating direction method of multipliers for convex quadratic semidefinite programming. Neurocomputing, 214, 575–586] bears a peculiar feature that the augmented Lagrangian function is not necessarily to be minimized with respect to the block-variable corresponding to the quadratic term in the objective function. In this paper, we lay the theoretical foundation of this phenomenon by interpreting this modified $3$-block ADMM as a special implementation of the Davis–Yin $3$-operator splitting [Davis, D and WT Yin (2017). A three-operator splitting scheme and its optimization applications. Set-Valued and Variational Analysis, 25, 829–858]. Based on this perspective, we are able to extend this modified $3$-block ADMM to a generalized $3$-block ADMM, in the sense of [Eckstein, J and DP Bertsekas (1992). On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55, 293–318], which not only applies to the more general convex composite quadratic programming problems but also admits the flexibility of achieving even better numerical performance.

In this paper, we apply an inexact dual alternating direction method of multipliers (dADMM) to an image decomposition model. In this model, an image is divided into two meaningful components, i.e., a cartoon part and a texture part. The dADMM presents not only the cartoon part and the texture part of an image but also the restored image (cartoon $\mathrm{\text{part}}+\mathrm{\text{texture}}$ part). We also summarize the global convergence for the algorithm. Numerical experiments demonstrate the efficiency and robustness of the inexact dADMM. Furthermore, we can obtain relatively higher signal-to-noise ratio (SNR) comparing to other algorithms.

In this paper, we introduce second-order composed radial derivatives of set-valued maps and establish some of its properties. By applying this second-order derivative, we obtain second-order sensitivity results for parametric multi-objective optimization problems under the Benson proper efficiency without assumptions of cone-convexity and Lipschitz continuity. Some of our results improve and derive the recent corresponding ones in the literature.

It was proved in Izmailov and Solodov (2014). Newton-Type Methods for Optimization and Variational Problems, Springer] that the existence of a noncritical multiplier for a (smooth) nonlinear programming problem is equivalent to an error bound condition for the Karush–Kuhn–Thcker (KKT) system without any assumptions. This paper investigates whether this result still holds true for a (smooth) nonlinear semidefinite programming (SDP) problem. The answer is negative: the existence of noncritical multiplier does not imply the error bound condition for the KKT system without additional conditions, which is illustrated by an example. In this paper, we obtain characterizations, in terms of the problem data, the critical and noncritical multipliers for a SDP problem. We prove that, for the SDP problem, the noncriticality property can be derived from the error bound condition for the KKT system without any assumptions, and we give an example to show that the noncriticality does not imply the error bound for the KKT system. We propose a set of assumptions under which the error bound condition for the KKT system can be derived from the noncriticality property. Finally, we establish a new error bound for $x$-part, which is expressed by both perturbation and the multiplier estimation.

In this paper, a smoothing partial exact penalty function of biconvex programming is studied. First, concepts of partial KKT point, partial optimum point, partial KKT condition, partial Slater constraint qualification and partial exactness are defined for biconvex programming. It is proved that the partial KKT point is equal to the partial optimum point under the condition of partial Slater constraint qualification and the penalty function of biconvex programming is partially exact if partial KKT condition holds. We prove the error bounds properties between smoothing penalty function and penalty function of biconvex programming when the partial KKT condition holds, as well as the error bounds between objective value of a partial optimum point of smoothing penalty function problem and its $𝜖$-feasible solution. So, a partial optimum point of the smoothing penalty function optimization problem is an approximately partial optimum point of biconvex programming. Second, based on the smoothing penalty function, two algorithms are presented for finding a partial optimum or approximate $𝜖$-feasible solution to an inequality constrained biconvex optimization and their convergence is proved under some conditions. Finally, numerical experiments show that a satisfactory approximate solution can be obtained by the proposed algorithm.

In this paper, we investigate stationary probability vectors of higher-order two-dimensional symmetric transition probability tensors. We show that there are two special symmetric transition probability tensors of order $m$ dimension 2, which have and only have two stationary probability vectors; and any other symmetric transition probability tensor of order $m$ dimension 2 has a unique stationary probability vector. As a byproduct, we obtain that any symmetric transition probability tensor of order $m$ dimension 2 has a unique positive stationary probability vector, and that any symmetric irreducible transition probability tensor of order $m$ dimension 2 has a unique stationary probability vector.