Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
From MaRDI portal
Publication:2806813
Abstract: In view of solving nonsmooth and nonconvex problems involving complex constraints (like standard NLP problems), we study general maximization-minimization procedures produced by families of strongly convex sub-problems. Using techniques from semi-algebraic geometry and variational analysis -in particular Lojasiewicz inequality- we establish the convergence of sequences generated by this type of schemes to critical points. The broad applicability of this process is illustrated in the context of NLP. In that case critical points coincide with KKT points. When the data are semi-algebraic or real analytic our method applies (for instance) to the study of various SQP methods: the moving balls method, Sl1QP, ESQP. Under standard qualification conditions, this provides -to the best of our knowledge- the first general convergence results for general nonlinear programming problems. We emphasize the fact that, unlike most works on this subject, no second-order assumption and/or convexity assumptions whatsoever are made. Rate of convergence are shown to be of the same form as those commonly encountered with first order methods.
Recommendations
- scientific article; zbMATH DE number 48566
- scientific article; zbMATH DE number 123327
- An SQP method for mathematical programs with vanishing constraints with strong convergence properties
- An efficient algorithm for \(\min\)-\(\max\) convex semi-infinite programming problems
- Local Convergence of SQP Methods in Semi-Infinite Programming
- A globally convergent SQP algorithm for mathematical programs with nonlinear complementarity constraints
- A new superlinearly convergent SQP algorithm for nonlinear minimax problems
- A semidefinite programming method for integer convex quadratic minimization
- A superlinearly convergent sequential quadratic programming algorithm for minimax problems
- A superlinearly convergent SQP algorithm for mathematical programs with linear complementarity constraints
Cites work
- scientific article; zbMATH DE number 3567782 (Why is no real title available?)
- scientific article; zbMATH DE number 2155014 (Why is no real title available?)
- A Sequential Quadratically Constrained Quadratic Programming Method for Differentiable Convex Minimization
- A class of globally convergent optimization methods based on conservative convex separable approximations
- A globally convergent method for nonlinear programming
- A majorize-minimize subspace approach for \(\ell_2-\ell_0\) image regularization
- A method for the solution of certain non-linear problems in least squares
- A moving balls approximation method for a class of smooth constrained minimization problems
- A robust sequential quadratic programming method
- Active Sets, Nonsmoothness, and Sensitivity
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- An Invitation to Tame Optimization
- An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming
- Clarke Subgradients of Stratifiable Functions
- Constraint identification and algorithm stabilization for degenerate nonlinear programs
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
- Convergence of the Iterates of Descent Methods for Analytic Cost Functions
- Dual subgradient algorithms for large-scale nonsmooth learning problems
- Ekeland's variational principle and the mountain pass lemma
- Geometric categories and o-minimal structures
- Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming
- Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences
- Gradient-based algorithms with applications to signal-recovery problems
- Introductory lectures on convex optimization. A basic course.
- On gradients of functions definable in o-minimal structures
- On search directions for minimization algorithms
- On the Convergence of Successive Linear-Quadratic Programming Algorithms
- On the Sequential Quadratically Constrained Quadratic Programming Methods
- On the complexity of finding first-order critical points in constrained nonlinear optimization
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
- Sequential quadratic programming methods
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
Cited in
(34)- The proximity operator of the log-sum penalty
- The appeals of quadratic majorization-minimization
- Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
- Qualification Conditions in Semialgebraic Programming
- Composite difference-MAX programs for modern statistical estimation problems
- From error bounds to the complexity of first-order descent methods for convex functions
- Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems
- Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
- Stochastic proximal linear method for structured non-convex problems
- Local convergence of the heavy-ball method and iPiano for non-convex optimization
- Doubly iteratively reweighted algorithm for constrained compressed sensing models
- Harnessing Structure in Composite Nonsmooth Minimization
- Composite optimization by nonconvex majorization-minimization
- A proximal DC approach for quadratic assignment problem
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Variable Metric Forward-Backward Algorithm for Composite Minimization Problems
- Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
- Efficiency of minimizing compositions of convex functions and smooth maps
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- scientific article; zbMATH DE number 7306909 (Why is no real title available?)
- An inexact proximal majorization-minimization algorithm for remote sensing image stripe noise removal
- Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
- Convergence analysis of a proximal point algorithm for minimizing differences of functions
- The value function approach to convergence analysis in composite optimization
- Learning graph Laplacian with MCP
- Feasible methods for nonconvex nonsmooth problems with applications in green communications
- Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
- Retraction-based first-order feasible methods for difference-of-convex programs with smooth inequality and simple geometric constraints
- The multiproximal linearization method for convex composite problems
- Level constrained first order methods for function constrained optimization
- Variance reduced moving balls approximation method for smooth constrained minimization problems
- Analysis and algorithms for some compressed sensing models based on L1/L2 minimization
- SABRINA: a stochastic subspace majorization-minimization algorithm
This page was built for publication: Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806813)
