This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alt ernating direction met hods of multipliers(ADMMs)for convex composite optimi...This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alt ernating direction met hods of multipliers(ADMMs)for convex composite optimization problems.The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algor计hms.Specifically,the majorized augmented Lagrangian functions,the indefinite proximal terms,the inexact symmetrie Gauss-Seidel decomposition theorem,the tolerance criteria of approximately solving the subproblems,and the large dual step-lengths,are all incorporated in one algoi?计hmic framework,which we named as sGS-imiPADMM.From the popularity of convergent variants of multi-block ADMMs in recent years,especially for high-dimensional multi-block convex composite conic programming problems,the unification presen ted in this paper,as well as the corresponding convergence results,may have the great potential of facilitating the implemen tation of many multi-block ADMMs in various problem set tings.展开更多
In this paper, we provide a complete characterization of the robust isolated calmness of the Karush-Kuhn-Tucker （KKT） solution mapping for convex constrained optimization problems regularized by the nuclear norm fun...In this paper, we provide a complete characterization of the robust isolated calmness of the Karush-Kuhn-Tucker （KKT） solution mapping for convex constrained optimization problems regularized by the nuclear norm function. This study is motivated by the recent work in [8], where the authors show that under the Robinson constraint qualification at a local optimal solution, the KKT solution mapping for a wide class of conic programming problems is robustly isolated calm if and only if both the second order sufficient condition （SOSC） and the strict Robinson constraint qualification （SRCQ） are satisfied. Based on the variational properties of the nuclear norm function and its conjugate, we establish the equivalence between the primal/dual SOSC and the dual/primal SRCQ. The derived results lead to several equivalent characterizations of the robust isolated calmness of the KKT solution mapping and add insights to the existing literature on the stability of nuclear norm regularized convex optimization problems.展开更多
The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic...The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic equilibrium problems. Two most important research issues are how to identify the solvability and how to solve such a problem via analyzing the structure of the involved tensor. In this paper, based on the concept of monotone mappings, we introduce a new class of structured tensors and the corresponding monotone tensor complementarity problem. We show that the solution set of the monotone tensor complementarity problem is nonempty and compact under the feasibility assumption. Moreover, a necessary and sufficient condition for ensuring the feasibility is given via analyzing the structure of the involved tensor. Based on the Huber function,we propose a regularized smoothing Newton method to solve the monotone tensor complementarity problem and establish its global convergence. Under some mild assumptions, we show that the proposed algorithm is superlinearly convergent. Preliminary numerical results indicate that the proposed algorithm is very promising.展开更多
文摘This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alt ernating direction met hods of multipliers(ADMMs)for convex composite optimization problems.The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algor计hms.Specifically,the majorized augmented Lagrangian functions,the indefinite proximal terms,the inexact symmetrie Gauss-Seidel decomposition theorem,the tolerance criteria of approximately solving the subproblems,and the large dual step-lengths,are all incorporated in one algoi?计hmic framework,which we named as sGS-imiPADMM.From the popularity of convergent variants of multi-block ADMMs in recent years,especially for high-dimensional multi-block convex composite conic programming problems,the unification presen ted in this paper,as well as the corresponding convergence results,may have the great potential of facilitating the implemen tation of many multi-block ADMMs in various problem set tings.
文摘In this paper, we provide a complete characterization of the robust isolated calmness of the Karush-Kuhn-Tucker （KKT） solution mapping for convex constrained optimization problems regularized by the nuclear norm function. This study is motivated by the recent work in [8], where the authors show that under the Robinson constraint qualification at a local optimal solution, the KKT solution mapping for a wide class of conic programming problems is robustly isolated calm if and only if both the second order sufficient condition （SOSC） and the strict Robinson constraint qualification （SRCQ） are satisfied. Based on the variational properties of the nuclear norm function and its conjugate, we establish the equivalence between the primal/dual SOSC and the dual/primal SRCQ. The derived results lead to several equivalent characterizations of the robust isolated calmness of the KKT solution mapping and add insights to the existing literature on the stability of nuclear norm regularized convex optimization problems.
基金supported by National Natural Science Foundation of China(Grant No.12171271)。
文摘The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic equilibrium problems. Two most important research issues are how to identify the solvability and how to solve such a problem via analyzing the structure of the involved tensor. In this paper, based on the concept of monotone mappings, we introduce a new class of structured tensors and the corresponding monotone tensor complementarity problem. We show that the solution set of the monotone tensor complementarity problem is nonempty and compact under the feasibility assumption. Moreover, a necessary and sufficient condition for ensuring the feasibility is given via analyzing the structure of the involved tensor. Based on the Huber function,we propose a regularized smoothing Newton method to solve the monotone tensor complementarity problem and establish its global convergence. Under some mild assumptions, we show that the proposed algorithm is superlinearly convergent. Preliminary numerical results indicate that the proposed algorithm is very promising.
