Book contents
- Frontmatter
- Contents
- Preface
- Singularities and computation of minimizers for variational problems
- Adaptive finite element methods for flow problems
- Newton's method and some complexity aspects of the zero-finding problem
- Kronecker's smart, little black boxes
- Numerical analysis in Lie groups
- Feasibility control in nonlinear optimization
- Six lectures on the geometric integration of ODEs
- When are integration and discrepancy tractable?
- Moving frames — in geometry, algebra, computer vision, and numerical analysis
- Harmonic map flows and image processing
- Statistics from computations
- Simulation of stochastic processes and applications
- Real-time numerical solution to Duncan-Mortensen-Zakai equation
Feasibility control in nonlinear optimization
Published online by Cambridge University Press: 05 August 2013
- Frontmatter
- Contents
- Preface
- Singularities and computation of minimizers for variational problems
- Adaptive finite element methods for flow problems
- Newton's method and some complexity aspects of the zero-finding problem
- Kronecker's smart, little black boxes
- Numerical analysis in Lie groups
- Feasibility control in nonlinear optimization
- Six lectures on the geometric integration of ODEs
- When are integration and discrepancy tractable?
- Moving frames — in geometry, algebra, computer vision, and numerical analysis
- Harmonic map flows and image processing
- Statistics from computations
- Simulation of stochastic processes and applications
- Real-time numerical solution to Duncan-Mortensen-Zakai equation
Summary
Abstract
We analyze the properties that optimization algorithms must possess in order to prevent convergence to non-stationary points for the merit function. We show that demanding the exact satisfaction of constraint linearizations results in difficulties in a wide range of optimization algorithms. Feasibility control is a mechanism that prevents convergence to spurious solutions by ensuring that sufficient progress towards feasibility is made, even in the presence of certain rank deficiencies. The concept of feasibility control is studied in this paper in the context of Newton methods for nonlinear systems of equations and equality constrained optimization, as well as in interior methods for nonlinear programming.
Introduction
We survey some recent developments in nonlinear optimization, paying particular attention to global convergence properties. A common thread in our review is the concept of “feasibility control”, which is a name we give to mechanisms that regulate progress toward feasibility.
An example of lack of feasibility control occurs in line search Newton methods for solving systems of nonlinear equations. It has been known since the 1970s (see Powell [24]) that these methods can converge to undesirable points. The difficulties are caused by the requirement that each step satisfy a linearization of the equations, and cannot be overcome simply by performing a line search. The need for more robust algorithms has been one of the main driving forces behind the development of trust region methods. Feasibility control is provided in trust region methods by reformulating the step computation as an optimization problem with a restriction on the length of the step.
- Type
- Chapter
- Information
- Foundations of Computational Mathematics , pp. 125 - 154Publisher: Cambridge University PressPrint publication year: 2001
- 1
- Cited by