Inexact penalty decomposition methods for optimization problems with geometric constraints

DOI10.1007/S10589-023-00475-2zbMATH Open1522.90079arXiv2210.05379MaRDI QIDQ6133301FDOQ6133301

Christian Kanzow, Matteo Lapucci

Publication date: 24 July 2023

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: This paper provides a theoretical and numerical investigation of a penalty decomposition scheme for the solution of optimization problems with geometric constraints. In particular, we consider some situations where parts of the constraints are nonconvex and complicated, like cardinality constraints, disjunctive programs, or matrix problems involving rank constraints. By a variable duplication and decomposition strategy, the method presented here explicitly handles these difficult constraints, thus generating iterates which are feasible with respect to them, while the remaining (standard and supposingly simple) constraints are tackled by sequential penalization. Inexact optimization steps are proven sufficient for the esulting algorithm to work, so that it is employable even with difficult objective functions. The current work is therefore a significant generalization of existing papers on penalty decomposition methods. On the other hand, it is related to some recent publications which use an augmented Lagrangian idea to solve optimization problems with geometric constraints. Compared to these methods, the decomposition idea is shown to be numerically superior since it allows much more freedom in the choice of the subproblem solver, and since the number of certain (possibly expensive) projection steps is significantly less. Extensive numerical results on several highly complicated classes of optimization problems in vector and matrix paces indicate that the current method is indeed very efficient to solve these problems.

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

zbMATH Keywords

augmented Lagrangiancardinality constraintsdisjunctive programmingasymptotic regularitylow-rank optimizationasymptotic stationaritypenalty decompositionMordukhovich-stationarity

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) Set-valued and variational analysis (49J53)

Cites Work

• Title not available (Why is that?)
• Maximum stable set formulations and heuristics based on continuous optimization
• Convex analysis and monotone operator theory in Hilbert spaces
• Benchmarking optimization software with performance profiles.
• On the limited memory BFGS method for large scale optimization
• Exact matrix completion via convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Literature survey on low rank approximation of matrices
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints
• Sparse Approximation via Penalty Decomposition Methods
• Inexact block coordinate descent methods with application to non-negative matrix factorization
• Globally convergent block-coordinate techniques for unconstrained optimization
• Low rank approximation. Algorithms, implementation, applications
• Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications
• Lagrangean decomposition: A model yielding stronger lagrangean bounds
• A Cone-Continuity Constraint Qualification and Algorithmic Consequences
• On sequential optimality conditions for smooth constrained optimization
• Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
• Optimality Conditions for Optimization Problems with Complementarity Constraints
• An Alternating Augmented Lagrangian method for constrained nonconvex optimization
• An augmented Lagrangian method for optimization problems with structured geometric constraints
• An example comparing the standard and safeguarded augmented Lagrangian methods
• Variational Analysis and Applications
• Nonlinear programming
• A Scalable Algorithm for Sparse Portfolio Selection
• Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization
• 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
• On the linear independence constraint qualification in disjunctive programming
• Local and Global Analysis of Multiplier Methods for Constrained Optimization in Banach Spaces
• Convergent inexact penalty decomposition methods for cardinality-constrained problems
• A penalty decomposition approach for multi-objective cardinality-constrained optimization problems
• Sufficient conditions for metric subregularity of constraint systems with applications to disjunctive and ortho-disjunctive programs
• On nondegenerate M-stationary points for sparsity constrained nonlinear optimization
• A concave optimization-based approach for sparse multiobjective programming
• Tangent and normal cones for low-rank matrices

Cited In (6)

• Geometrical interpretation of the predictor-corrector type algorithms in structured optimization problems
• Convergent inexact penalty decomposition methods for cardinality-constrained problems
• An augmented Lagrangian method for optimization problems with structured geometric constraints
• Geometric approach to Fletcher's ideal penalty function
• Cardinality-Constrained Multi-objective Optimization: Novel Optimality Conditions and Algorithms
• Title not available (Why is that?)

   Recommendations

• Convergent inexact penalty decomposition methods for cardinality-constrained problems 👍 👎
• An augmented Lagrangian method for optimization problems with structured geometric constraints 👍 👎
• Penalty decomposition methods for rank minimization 👍 👎
• Exact penalty functions and convex extensions of functions in schemes of decomposition in variables 👍 👎
• A variable-penalty alternating directions method for convex optimization 👍 👎

This page was built for publication: Inexact penalty decomposition methods for optimization problems with geometric constraints

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