An augmented Lagrangian method for optimization problems with structured geometric constraints

DOI10.1007/S10107-022-01870-ZzbMATH Open1518.90060arXiv2105.08317OpenAlexW3161794388MaRDI QIDQ6038673FDOQ6038673

Authors: Xiaoxi Jia, Christian Kanzow, P. Mehlitz, Gerd Wachsmuth 

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2105.08317

Recommendations

• Inexact penalty decomposition methods for optimization problems with geometric constraints
• An augmented Lagrangian method for cardinality-constrained optimization problems
• Constrained composite optimization and augmented Lagrangian methods
• Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints
• A sharp augmented Lagrangian-based method in constrained non-convex optimization

zbMATH Keywords

complementarity constraintsaugmented Lagrangian methodcardinality constraintsasymptotic regularitynonmonotone projected gradient methodMordukhovich-stationarityMAXCUT problem

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Semidefinite programming (90C22) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

• Practical augmented Lagrangian methods for constrained optimization
• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
• Two-Point Step Size Gradient Methods
• Exact matrix completion via convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Title not available (Why is that?)
• Sparse Reconstruction by Separable Approximation
• Nonsmooth approach to optimization problems with equilibrium constraints. Theory, applications and numerical results
• Convergence properties of a regularization scheme for mathematical programs with complementarity constraints
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• On Augmented Lagrangian Methods with General Lower-Level Constraints
• Some continuity properties of polyhedral multifunctions
• A Nonmonotone Line Search Technique for Newton’s Method
• On the Calmness of a Class of Multifunctions
• Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints
• A relaxed constant positive linear dependence constraint qualification and applications
• Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints
• Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints
• SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
• Restricted normal cones and sparsity optimization with affine constraints
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
• A Cone-Continuity Constraint Qualification and Algorithmic Consequences
• The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited
• Prox-regularity of rank constraint sets and implications for algorithms
• Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
• Notes on some constraint qualifications for mathematical programs with equilibrium constraints
• A relaxed constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints
• Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs
• An Augmented Lagrangian Method for Non-Lipschitz Nonconvex Programming
• The limiting normal cone of a complementarity set in Sobolev spaces
• Penalty Methods for a Class of Non-Lipschitz Optimization Problems
• On Optimality Conditions for Nonlinear Conic Programming
• An example comparing the standard and safeguarded augmented Lagrangian methods
• Optimality conditions and global convergence for nonlinear semidefinite programming
• Convergence Properties of a Second Order Augmented Lagrangian Method for Mathematical Programs with Complementarity Constraints
• Variational Analysis and Applications
• Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization
• SOC functions and their applications
• Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences
• Stationarity conditions and constraint qualifications for mathematical programs with switching constraints. With applications to either-or-constrained programming
• New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints
• Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs
• A comparison of solution approaches for the numerical treatment of or-constrained optimization problems
• On the linear independence constraint qualification in disjunctive programming
• Relaxation schemes for mathematical programmes with switching constraints
• New Sequential Optimality Conditions for Mathematical Programs with Complementarity Constraints and Algorithmic Consequences
• Sequential optimality conditions for cardinality-constrained optimization problems with applications
• An augmented Lagrangian method for cardinality-constrained optimization problems
• Optimality conditions and exact penalty for mathematical programs with switching constraints
• Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs
• A New Augmented Lagrangian Method for MPCCs—Theoretical and Numerical Comparison with Existing Augmented Lagrangian Methods
• Reformulation of the M-Stationarity Conditions as a System of Discontinuous Equations and Its Solution by a Semismooth Newton Method
• The limiting normal cone to pointwise defined sets in Lebesgue spaces
• Tangent and normal cones for low-rank matrices
• New Constraint Qualifications for Optimization Problems in Banach Spaces Based on Asymptotic KKT Conditions

Cited In (15)

• Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka–Łojasiewicz Property Without Global Lipschitz Assumptions
• A Global Optimization Approach for Multimarginal Optimal Transport Problems with Coulomb Cost
• Proximal gradient methods beyond monotony
• Local properties and augmented Lagrangians in fully nonconvex composite optimization
• Inexact penalty decomposition methods for optimization problems with geometric constraints
• An Augmented Lagrangian Trust Region Method with a Bi-object Strategy
• Augmented Lagrangian active set methods for obstacle problems
• An Augmented Lagrangian‐Based Approach to the Oseen Problem
• COAP 2021 best paper prize
• Sequential M-stationarity conditions for general optimization problems
• An augmented Lagrangian optimization method for inflatable structures analysis problems
• A modified augmented Lagrangian method for a class of constrained problems
• A matrix-free augmented Lagrangian algorithm with application to large-scale structural design optimization
• Constrained composite optimization and augmented Lagrangian methods
• Convergence properties of monotone and nonmonotone proximal gradient methods revisited

This page was built for publication: An augmented Lagrangian method for optimization problems with structured geometric constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038673)