Nonlinear Programming

Nonlinear programming optimizes a smooth nonlinear objective subject to nonlinear constraints, covering both the theory of optimality and the algorithms that compute solutions.

Definition

A nonlinear program minimizes a possibly nonlinear objective over a feasible set defined by nonlinear equality and inequality constraints; unlike convex problems it may possess multiple local optima, so most methods seek points satisfying necessary optimality conditions.

Scope

This topic covers unconstrained minimization, line-search and trust-region strategies, gradient, Newton, and quasi-Newton methods, first- and second-order optimality conditions, the Karush-Kuhn-Tucker conditions and constraint qualifications, and constrained methods such as penalty, augmented Lagrangian, and sequential quadratic programming.

Core questions

• What conditions characterize a local optimum of a constrained nonlinear problem?
• How do descent methods find a stationary point of an unconstrained problem?
• How are constraints incorporated into iterative algorithms?
• When can a computed local optimum be trusted as global?

Key theories

Optimality conditions

First-order Karush-Kuhn-Tucker conditions and second-order curvature conditions characterize local optima of constrained problems under suitable constraint qualifications.

Descent and Newton-type methods

Gradient, Newton, and quasi-Newton methods generate descent directions and use line searches or trust regions to converge to stationary points, with quasi-Newton updates approximating curvature cheaply.

Constrained optimization algorithms

Penalty, augmented Lagrangian, and sequential quadratic programming methods convert constrained problems into sequences of simpler ones, handling equality and inequality constraints systematically.

Clinical relevance

Nonlinear programming is used wherever objectives or constraints are not linear, including model fitting and training of statistical and machine-learning models, engineering design, optimal control, and parameter estimation across the sciences.

History

The Karush-Kuhn-Tucker conditions, established in 1951 and anticipated by Karush in 1939, generalized Lagrange multipliers to inequality constraints and founded constrained nonlinear theory. Quasi-Newton methods, augmented Lagrangians, and sequential quadratic programming developed through the latter twentieth century into the standard computational toolkit.

Key figures

• Harold Kuhn
• Albert Tucker
• Isaac Newton
• Magnus Hestenes

Seminal works

• nocedal2006
• bertsekas1999

Frequently asked questions

Why is nonlinear programming harder than linear programming?

Nonlinear problems can have curved feasible regions and multiple local optima, so there is generally no guarantee that a computed solution is globally best, and optima need not lie at vertices. Algorithms must rely on local information such as gradients and curvature.

What is a quasi-Newton method?

It is an iterative method that approximates the Newton step without computing the full second-derivative matrix, building up curvature information from successive gradients. Methods such as BFGS achieve fast convergence at much lower cost than exact Newton steps.