Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.     

Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming

We investigate in this paper global convergence properties of the augmented Lagrangian method for nonlinear semidefinite programming (NLSDP). Four modified augmented Lagrangian methods for solving NLSDP based on different algorithmic strategies are proposed. Possibly infeasible limit points of the proposed methods are characterized. It is proved that feasible limit points that satisfy the Mangasarian-Fromovitz constraint qualification are KKT points of NLSDP without requiring the boundedness condition of the multipliers. Preliminary numerical results are reported to compare the performance of the modified augmented Lagrangian methods.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

非凸半定规划的增广Lagrangian的微分的计算

迄今为止，还未见出版过有关求解非凸半定规划的算法，但在最近，Chen，et.al(2000)和Sun＆Sun(1999)关于非凸半定规划(SDP)的增广Lagrangian的研究是非常有用的，在本文中，我们证明非凸半定规划的增广Lagrangian是可微的，并且给出它的可微表达式．     

On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming

In this paper, we present new convergence properties of the augmented Lagrangian method for nonlinear semidefinite programs (NSDP). Convergence to the approximately global solutions and optimal values of NSDP is first established for a basic augmented Lagrangian scheme under mild conditions, without requiring the boundedness condition of the multipliers. We then propose four modified augmented Lagrangian methods for NSDP based on different algorithmic strategies. We show that the same convergence of the proposed methods can be ensured under weaker conditions.     

Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming

This paper aims at showing that the class of augmented Lagrangian functions for nonlinear semidefinite programming problems can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem. By means of the image space analysis, a global saddle point condition for the augmented Lagrangian function is investigated. It is shown that the existence of a saddle point is equivalent to a regular nonlinear separation of two suitable subsets of the image space. Without requiring the strict complementarity, it is proved that, under second order sufficiency conditions, the augmented Lagrangian function admits a local saddle point. The existence of global saddle points is then obtained under additional assumptions that do not require the compactness of the feasible set. Motivated by the result on global saddle points, we propose two modified primal-dual methods based on the augmented Lagrangian using different strategies and prove their convergence to a global solution and the optimal value of the original problem without requiring the boundedness condition of the multiplier sequence.     

Alternating direction augmented Lagrangian methods for semidefinite programming

We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.     

A primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming

In this paper, we propose a primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming problems, especially for some difficult problems. The basic idea of this method is to apply the majorized semismooth Newton-CG augmented Lagrangian method to the primal convex problem. And we take two special nonlinear semidefinite programming problems as examples to illustrate the algorithm. Furthermore, we establish the global convergence and the iteration complexity of the algorithm. Numerical experiments demonstrate that our method works very well for the testing problems, especially for many ill-conditioned ones.     

Exact augmented Lagrangian functions for nonlinear semidefinite programming

In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems into unconstrained nonlinear programming ones. Here, we first establish a unified framework for constructing these exact functions, generalizing Di Pillo and Lucidi’s work from 1996, that was aimed at solving nonlinear programming problems. Then, through our framework, we propose a practical augmented Lagrangian function for NSDP, proving that it is continuously differentiable and exact under the so-called nondegeneracy condition. We also present some preliminary numerical experiments.     

Proximal Point Methods for Lipschitz Functions on Hadamard Manifolds: Scalar and Vectorial Cases

In the second part of our study, we introduce the concept of global extended exactness of penalty and augmented Lagrangian functions, and derive the localization principle in the extended form. The main idea behind the extended exactness consists in an extension of the original constrained optimization problem by adding some extra variables, and then construction of a penalty/augmented Lagrangian function for the extended problem. This approach allows one to design extended penalty/augmented Lagrangian functions having some useful properties (such as smoothness), which their counterparts for the original problem might not possess. In turn, the global exactness of such extended merit functions can be easily proved with the use of the localization principle presented in this paper, which reduces the study of global exactness to a local analysis of a merit function based on sufficient optimality conditions and constraint qualifications. We utilize the localization principle in order to obtain simple necessary and sufficient conditions for the global exactness of the extended penalty function introduced by Huyer and Neumaier, and in order to construct a globally exact continuously differentiable augmented Lagrangian function for nonlinear semidefinite programming problems.     

Properties of the Augmented Lagrangian in Nonlinear Semidefinite Optimization

We study the properties of the augmented Lagrangian function for nonlinear semidefinite programming. It is shown that, under a set of sufficient conditions, the augmented Lagrangian algorithm is locally convergent when the penalty parameter is larger than a certain threshold. An error estimate of the solution, depending on the penalty parameter, is also established.The first author was partially supported by Singapore-MIT Alliance and by the National University of Singapore under Grants RP314000-028/042/057-112. The second author was partially supported by the Funds of the Ministry of Education of China for PhD Units under Grant 20020141013 and the National Natural Science Foundation of China under Grant 10471015.     

半定优化与半光滑牛顿算法

本文讨论半光滑牛顿算法的基本概念与其在求解半定优化问题中的应用．特别地，该算法可用于求解线性或非线性半定互补问题．本文同时综述最近在矩阵方程，增广拉格朗日公式和半定优化稳定性方面的、源于半光滑牛顿算法的理论成果．     

Preconditioning of GMRES by skew-Hermitian iterations

A class of preconditioners for solving non-Hermitian positive definite systems of linear algebraic equations is proposed and investigated. It is based on Hermitian and skew-Hermitian splitting of the initial matrix. A generalization for saddle point systems having semidefinite or singular (1, 1) blocks is given. Our approach is based on an augmented Lagrangian formulation. It is shown that such preconditioners can be efficiently used for the iterative solution of systems of linear algebraic equations by the GMRES method.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems

In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems given in standard form. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products; dynamic update of the scaled inner product for properly balancing the primal and dual relative residuals; and proper choices of the initial primal and dual iterates, as well as the initial parameter for the scaled inner product. Finally, we present computational results showing that our method outperforms the two most competitive codes for large-scale conic semidefinite programs, namely: the boundary-point method introduced by Povh et al. and the Newton-CG augmented Lagrangian method by Zhao et al.     

A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

 In this paper, we present a nonlinear programming algorithm for solving semidefinite programs (SDPs) in standard form. The algorithm's distinguishing feature is a change of variables that replaces the symmetric, positive semidefinite variable X of the SDP with a rectangular variable R according to the factorization X=RR ^T . The rank of the factorization, i.e., the number of columns of R, is chosen minimally so as to enhance computational speed while maintaining equivalence with the SDP. Fundamental results concerning the convergence of the algorithm are derived, and encouraging computational results on some large-scale test problems are also presented. Received: March 22, 2001 / Accepted: August 30, 2002 Published online: December 9, 2002 Key Words. semidefinite programming – low-rank factorization – nonlinear programming – augmented Lagrangian – limited memory BFGS This research was supported in part by the National Science Foundation under grants CCR-9902010, INT-9910084, CCR-0203426 and CCR-0203113     

QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming

In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier)  https://doi.org/10.5281/zenodo.1206980.     

Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition

We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods. Received: April, 2004 The last author gratefully acknowledges the support from the Austrian Science Foundation FWF Project P12660-MAT.