An augmented Lagrangian method for optimization problems with structured geometric constraints
From MaRDI portal
Publication:6038673
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.
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
Cites work
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 852532 (Why is no real title available?)
- A Nonmonotone Line Search Technique for Newton’s Method
- A comparison of solution approaches for the numerical treatment of or-constrained optimization problems
- A cone-continuity constraint qualification and algorithmic consequences
- A new augmented Lagrangian method for MPCCs -- theoretical and numerical comparison with existing augmented Lagrangian methods
- A relaxed constant positive linear dependence constraint qualification and applications
- A relaxed constant positive linear dependence constraint qualification for mathematical programs with equilibrium constraints
- An augmented Lagrangian method for cardinality-constrained optimization problems
- An augmented Lagrangian method for non-Lipschitz nonconvex programming
- An example comparing the standard and safeguarded augmented Lagrangian methods
- Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
- Convergence properties of a regularization scheme for mathematical programs with complementarity constraints
- Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints
- Convex analysis and monotone operator theory in Hilbert spaces
- Exact matrix completion via convex optimization
- Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method
- Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences
- Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications
- Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs
- New Constraint Qualifications for Optimization Problems in Banach Spaces Based on Asymptotic KKT Conditions
- New sequential optimality conditions for mathematical programs with complementarity constraints and algorithmic consequences
- New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints
- Nonmonotone Spectral Projected Gradient Methods on Convex Sets
- Nonsmooth approach to optimization problems with equilibrium constraints. Theory, applications and numerical results
- Notes on some constraint qualifications for mathematical programs with equilibrium constraints
- On Augmented Lagrangian Methods with General Lower-Level Constraints
- On optimality conditions for nonlinear conic programming
- On the Calmness of a Class of Multifunctions
- On the linear independence constraint qualification in disjunctive programming
- Optimality conditions and exact penalty for mathematical programs with switching constraints
- Optimality conditions and global convergence for nonlinear semidefinite programming
- Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints
- Penalty methods for a class of non-Lipschitz optimization problems
- Practical augmented Lagrangian methods for constrained optimization
- Prox-regularity of rank constraint sets and implications for algorithms
- Reformulation of the M-stationarity conditions as a system of discontinuous equations and its solution by a semismooth Newton method
- Relaxation schemes for mathematical programmes with switching constraints
- Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs
- Restricted normal cones and sparsity optimization with affine constraints
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- SOC functions and their applications
- Sequential optimality conditions for cardinality-constrained optimization problems with applications
- Some continuity properties of polyhedral multifunctions
- Sparse Reconstruction by Separable Approximation
- Sparsity constrained nonlinear optimization: optimality conditions and algorithms
- Stationarity conditions and constraint qualifications for mathematical programs with switching constraints. With applications to either-or-constrained programming
- Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization
- Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs
- Tangent and normal cones for low-rank matrices
- The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
- The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited
- The limiting normal cone of a complementarity set in Sobolev spaces
- The limiting normal cone to pointwise defined sets in Lebesgue spaces
- Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints
- Two-Point Step Size Gradient Methods
- Variational Analysis
- Variational analysis and applications
Cited in
(16)- Convergence properties of monotone and nonmonotone proximal gradient methods revisited
- Constrained composite optimization and augmented Lagrangian methods
- COAP 2021 best paper prize
- Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables
- Convergence Analysis of the Proximal Gradient Method in the Presence of the Kurdyka–Łojasiewicz Property Without Global Lipschitz Assumptions
- Augmented Lagrangian active set methods for obstacle problems
- An Augmented Lagrangian‐Based Approach to the Oseen Problem
- An augmented Lagrangian optimization method for inflatable structures analysis problems
- Proximal gradient methods beyond monotony
- Local properties and augmented Lagrangians in fully nonconvex composite optimization
- A Global Optimization Approach for Multimarginal Optimal Transport Problems with Coulomb Cost
- Inexact penalty decomposition methods for optimization problems with geometric constraints
- Sequential M-stationarity conditions for general optimization 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
- An Augmented Lagrangian Trust Region Method with a Bi-object Strategy
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)
