Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs

DOI10.1287/MOOR.2015.0735zbMATH Open1338.65156arXiv1409.8147OpenAlexW1855462127MaRDI QIDQ2806813FDOQ2806813

Authors: Jérôme Bolte, Edouard Pauwels 

Publication date: 19 May 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

nonlinear programmingmajorization-minimizationKKT pointsSQP methodsKL inequalitytame optimizationconverging methodsextended sequential quadratic methodmoving balls methodS\(\ell^1\)QP

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Methods of successive quadratic programming type (90C55) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37)

Cites Work

• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• A method for the solution of certain non-linear problems in least squares
• A majorize-minimize subspace approach for \(\ell_2-\ell_0\) image regularization
• 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
• Geometric categories and o-minimal structures
• Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
• Clarke Subgradients of Stratifiable Functions
• Convergence of the Iterates of Descent Methods for Analytic Cost Functions
• Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences
• A globally convergent method for nonlinear programming
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming
• Dual subgradient algorithms for large-scale nonsmooth learning problems
• On gradients of functions definable in o-minimal structures
• SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Gradient-based algorithms with applications to signal-recovery problems
• On search directions for minimization algorithms
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• An Invitation to Tame Optimization
• Sequential quadratic programming methods
• Title not available (Why is that?)
• Active Sets, Nonsmoothness, and Sensitivity
• On the Convergence of Successive Linear-Quadratic Programming Algorithms
• A moving balls approximation method for a class of smooth constrained minimization problems
• A class of globally convergent optimization methods based on conservative convex separable approximations
• Ekeland's variational principle and the mountain pass lemma
• A robust sequential quadratic programming method
• Constraint identification and algorithm stabilization for degenerate nonlinear programs
• On the complexity of finding first-order critical points in constrained nonlinear optimization
• On the Sequential Quadratically Constrained Quadratic Programming Methods
• A Sequential Quadratically Constrained Quadratic Programming Method for Differentiable Convex Minimization
• An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming

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
• Doubly iteratively reweighted algorithm for constrained compressed sensing models
• Harnessing Structure in Composite Nonsmooth Minimization
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• 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
• Title not available (Why is that?)
• 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
• Learning graph Laplacian with MCP
• The value function approach to convergence analysis in composite optimization
• Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
• Feasible methods for nonconvex nonsmooth problems with applications in green communications
• Retraction-based first-order feasible methods for difference-of-convex programs with smooth inequality and simple geometric constraints
• Level constrained first order methods for function constrained optimization
• The multiproximal linearization method for convex composite problems
• 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

Uses Software

• SNOPT
• PLCP
• UNLocBoX

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)