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)- SABRINA: a stochastic subspace majorization-minimization algorithm
- Efficiency of minimizing compositions of convex functions and smooth maps
- Local convergence of the heavy-ball method and iPiano for non-convex optimization
- scientific article; zbMATH DE number 7306909 (Why is no real title available?)
- Composite difference-MAX programs for modern statistical estimation problems
- An inexact proximal majorization-minimization algorithm for remote sensing image stripe noise removal
- Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
- 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
- The multiproximal linearization method for convex composite problems
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- Analysis and algorithms for some compressed sensing models based on L1/L2 minimization
- Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- A proximal DC approach for quadratic assignment problem
- Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
- Qualification Conditions in Semialgebraic Programming
- Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
- Variance reduced moving balls approximation method for smooth constrained minimization problems
- Learning graph Laplacian with MCP
- The proximity operator of the log-sum penalty
- Convergence analysis of a proximal point algorithm for minimizing differences of functions
- The appeals of quadratic majorization-minimization
- Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
- Doubly iteratively reweighted algorithm for constrained compressed sensing models
- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Retraction-based first-order feasible methods for difference-of-convex programs with smooth inequality and simple geometric constraints
- Composite optimization by nonconvex majorization-minimization
- Stochastic proximal linear method for structured non-convex problems
- Harnessing Structure in Composite Nonsmooth Minimization
- The value function approach to convergence analysis in composite optimization
- Level constrained first order methods for function constrained optimization
- Variable Metric Forward-Backward Algorithm for Composite Minimization Problems
- Feasible methods for nonconvex nonsmooth problems with applications in green communications
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)
