A Globally and Superlinearly Convergent Algorithm for Nonsmooth Convex Minimization
SIAM Journal on OptimizationPublished 1 November 1996
Masao Fukushima, Liqun Qi
Citations94
SJR quartileQ1
SJR score1.39
SNIP1.79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A globally convergent algorithm that is designed to solve a possibly nondifferentiable convex minimization problem that is shown to have a Q-superlinear rate of convergence.
Abstract
It is well known that a possibly nondifferentiable convex minimization problem can be transformed into a differentiable convex minimization problem by way of the Moreau–Yosida regularization. This paper presents a globally convergent algorithm that is designed to solve the latter problem. Under additional semismoothness and regularity assumptions, the proposed algorithm is shown to have a Q-superlinear rate of convergence.
Keywords
Computer ScienceMathematicsEngineering
SIAM Journal on Control and OptimizationMonotone Operators and the Proximal Point Algorithm
3,620 Citations1976R. T. Rockafellar
Mathematical ProgrammingA nonsmooth version of Newton's method
1,480 Citations1993Liqun Qi, Jie Sun
It is shown that the gradient function of the augmented Lagrangian forC2-nonlinear programming is semismooth, and the extended Newton's method can be used in the augmentedlagrangian method for solving nonlinear programs.
Mathematics of Operations ResearchConvergence Analysis of Some Algorithms for Solving Nonsmooth Equations
734 Citations1993Liqun Qi
Convergence analysis of some algorithms for solving systems of nonlinear equations defined by locally Lipschitzian functions and a hybrid method, which is both globally convergent in the sense of finding a stationary point of the norm function of the system and locally quadratically convergent, is presented.
Grundlehren der mathematischen WissenschaftenConvex Analysis and Minimization Algorithms II
422 Citations1993Jean‐Baptiste Hiriart‐Urruty, Claude Lemaréchal
SIAM Journal on OptimizationNonsmooth Equations: Motivation and Algorithms
356 Citations1993Jong‐Shi Pang, Liqun Qi
This paper reports on some recent developments in the area of solving of nonsmooth equations by generalized Newton methods, with the emphasis on three topics: motivation, characterization of superlinings, and motivation and characterization of motivation.
Transactions of the American Mathematical SocietyProx-regular functions in variational analysis
316 Citations1996R. A. Poliquin, R. T. Rockafellar
Mathematical ProgrammingConvergence of some algorithms for convex minimization
245 Citations1993Rafael Corrêa, Claude Lemaréchal
This work presents a simple and unified technique to establish convergence of various minimization methods, as well as implementable forms such as bundle algorithms, including the classical subgradient relaxation algorithm with divergent series.
SIAM Journal on OptimizationPractical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries
239 Citations1997Claude Lemaréchal, Claudia Sagastizábal
The most important part of this study concerns second-order differentiability: existence of a second- order development of f implies that its regularization has a Hessian.
Annales de l Institut Henri Poincaré C Analyse Non LinéaireMaximal monotone relations and the second derivatives of nonsmooth functions
134 Citations1985R. T. Rockafellar
Mathematical programming studiesNumerical methods for nondifferentiable convex optimization
114 Citations1987A. Auslender
Mathematical ProgrammingSuperlinearly convergent approximate Newton methods for LC1 optimization problems
99 Citations1994Liqun Qi
This paper presents approximate Newton or SQP methods for solving nonlinear programming problems whose objective and constraint functions have locally Lipschitzian derivatives, and establishes Q-superlinear convergence of these methods under the assumption that these derivatives are semismooth.
Operations Research LettersMinimization of SC1 functions and the Maratos effect
98 Citations1995Francisco Facchinei
It is shown that, under mild conditions, if the full search direction brings superlinear convergence, then the unit stepsize is eventually accepted so that the Maratos effect does not occur.
Mathematical ProgrammingA descent algorithm for nonsmooth convex optimization
85 Citations1984Masao Fukushima
This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable, and a convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below.
Mathematical ProgrammingA quasi-second-order proximal bundle algorithm
79 Citations1996Robert Mifflin
An algorithm for convex minimization which includes quasi-Newton updates within a proximal point algorithm that depends on a preconditioned bundle subalgorithm that is proved under boundedness assumptions on the preconditionser sequence is introduced.
Journal of Optimization Theory and ApplicationsA globally convergent Newton method for convex SC1 minimization problems
75 Citations1995Jong‐Shi Pang, Liqun Qi
SIAM Journal on OptimizationGeneralized Hessian Properties of Regularized Nonsmooth Functions
70 Citations1996R. A. Poliquin, R. T. Rockafellar
The results establish that generalized second-order expansions of Moreau envelopes, at least, can be counted on in most situations of interest in finite-dimensional optimization.
Mathematical ProgrammingA preconditioning proximal newton method for nondifferentiable convex optimization
36 Citations1997Liqun Qi, Xiaojun Chen
It is shown that a proximal Newton method for solving nondifferentiable convex optimization is possible within some accuracy and the second-order differentiability properties of the Moreau-Yosida regularization are invariant with respect to this preconditioning.
Annals of Operations ResearchAn SQP algorithm for extended linear-quadratic problems in stochastic programming
33 Citations1995Liqun Qi, Robert S. Womersley
This work presents a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming under a condition called B-regularity, which is milder than the fullyquadratic condition.