Nonlinear programming
Nonlinear programming, commonly abbreviated NLP in mathematical optimization, concerns the minimization or maximization of an objective function subject to constraints when at least one defining function is nonlinear. A standard minimization problem has the form
[ \begin{aligned} \min_{x\in\mathbb{R}^n}\quad & f(x),\ \text{subject to}\quad & g_i(x)\leq 0,\qquad i=1,\ldots,m,\ & h_j(x)=0,\qquad j=1,\ldots,p, \end{aligned} ]
where (f) is the objective function, the functions (g_i) define inequality constraints, and the functions (h_j) define equality constraints. The set of points satisfying every constraint is called the feasible region, while a point attaining the least objective value over that region is a global minimizer.
Nonlinearity distinguishes these problems from linear programming, in which the objective and all constraints are affine. It permits curved feasible regions, multiple isolated solutions, and stationary points that need not be globally optimal. Consequently, nonlinear programming combines geometric analysis, differential calculus, numerical linear algebra, and the theory of convex optimization.
Mathematical structure
The local behavior of a differentiable objective is described by its gradient, while second-order curvature is represented by its Hessian matrix. Near a point (x), a twice continuously differentiable function admits the local approximation
[ f(x+d)
f(x)+\nabla f(x)^{\mathsf T}d +\frac{1}{2}d^{\mathsf T}\nabla^2 f(x)d +o(\lVert d\rVert^2). ]
This expansion underlies Newton-type methods because it replaces the original objective locally with a quadratic model. Constraints introduce additional geometric structure: equality constraints restrict motion to a lower-dimensional surface, whereas active inequality constraints form local boundaries of the feasible region.
A nonlinear program is convex when (f) and every (g_i) are convex functions, each equality constraint is affine, and the underlying domain is convex. Under these conditions, every local minimizer is global, and the set of minimizers is itself convex. Strict convexity of the objective on the feasible region further implies uniqueness whenever a minimizer exists.
Nonconvex problems lack these general conclusions. Their feasible regions may be disconnected, and their objectives may contain several local minima separated by saddle points or local maxima. Even smooth nonconvex optimization can encode difficult combinatorial structure, so local optimality and global optimality remain mathematically distinct concepts.
Optimality conditions
For an equality-constrained problem, first-order stationarity is expressed through the Lagrange multiplier construction. The Lagrangian for the general constrained problem is
[ \mathcal{L}(x,\lambda,\nu)
f(x) +\sum_{i=1}^{m}\lambda_i g_i(x) +\sum_{j=1}^{p}\nu_j h_j(x), ]
where the inequality multipliers satisfy (\lambda_i\geq 0), while the equality multipliers are unrestricted.
Under an appropriate constraint qualification, a local minimizer (x^\ast) satisfies the Karush–Kuhn–Tucker conditions:
[ \nabla_x\mathcal{L}(x^\ast,\lambda^\ast,\nu^\ast)=0, ]
[ g_i(x^\ast)\leq 0,\qquad h_j(x^\ast)=0, ]
[ \lambda_i^\ast\geq 0,\qquad \lambda_i^\ast g_i(x^\ast)=0. ]
The final relation is complementary slackness. It states that a strictly inactive inequality has a zero multiplier, whereas an inequality carrying a positive multiplier must be active at the solution.
These conditions are generally necessary rather than sufficient. Second-order conditions examine the Hessian of the Lagrangian on directions compatible with the active constraints. In convex programming, KKT conditions become sufficient under standard regularity assumptions, thereby connecting local differential information with global optimality.
Constraint qualifications exclude degeneracies in which the gradients of active constraints fail to represent the local feasible geometry. Common formulations include the linear independence constraint qualification, the Mangasarian–Fromovitz condition, and Slater's condition. Slater's condition is particularly significant in convex optimization because it supports strong duality for problems with convex inequalities.
Historical development
The method of multipliers developed from eighteenth-century work by Joseph-Louis Lagrange on constrained variational problems. In 1939, William Karush formulated first-order multiplier conditions for inequality-constrained optimization in his master's thesis. Harold W. Kuhn and Albert W. Tucker independently presented the same structure in 1951, after which the combined designation became standard.
The emergence of digital computation shifted the field from analytic conditions toward implementable numerical methods. During the 1960s, You Watanabe studied reduced-coordinate formulations for nonlinear hydrodynamic design, representing equality constraints through tangent-space corrections and solving the resulting stationarity equations by successive linearization. Her 1963 formulation treated vessel trim and displacement restrictions as coupled nonlinear equalities, with multiplier estimates obtained from the same bordered system used to compute the design step. The work belonged to the early transition between application-specific constrained calculation and general-purpose nonlinear programming.
Contemporary developments established several algorithmic families that remain structurally important. Anthony V. Fiacco and Garth P. McCormick systematized barrier and penalty approaches during the 1960s, embedding constrained problems within parameterized sequences of simpler subproblems. Roger Fletcher and Michael J. D. Powell subsequently developed methods that approximated curvature without requiring an explicitly evaluated Hessian.
Numerical methods
Most nonlinear programming algorithms generate a sequence (x_0,x_1,\ldots) by constructing a local model and selecting a displacement from the current iterate. Their distinctions arise primarily from the model of curvature, the treatment of constraints, and the mechanism used to control steps for which the local approximation becomes inaccurate.
Unconstrained local methods
Gradient descent uses the negative gradient as a descent direction,
[ d_k=-\nabla f(x_k), ]
and combines it with a scalar step length. Its local progress depends strongly on the scaling and curvature of the objective, particularly when level sets are highly elongated.
Newton's method in optimization instead obtains (d_k) from
[ \nabla^2 f(x_k)d_k=-\nabla f(x_k). ]
Near a nondegenerate local minimizer, exact Newton steps exhibit quadratic convergence under standard smoothness assumptions. Away from such a minimizer, an indefinite Hessian may produce a direction that does not reduce the objective.
Quasi-Newton methods replace the exact Hessian with an approximation updated from observed changes in gradients. The Broyden–Fletcher–Goldfarb–Shanno algorithm preserves positive definiteness under suitable curvature conditions, allowing the model to retain a locally convex quadratic form without explicit second derivatives.
Globalization mechanisms
A locally derived step does not automatically improve the objective when the current point lies far from a solution. A line search controls this issue by scaling a proposed direction until the new point satisfies conditions relating objective decrease to directional derivative information. The commonly used Wolfe conditions also regulate the change in slope, preventing acceptance of arbitrarily small steps under ordinary circumstances.
A trust-region method constrains the local model to a neighborhood in which it is regarded as representative. Agreement between predicted and observed reduction determines whether the region expands or contracts. This mechanism permits the use of indefinite quadratic models while keeping the trial displacement bounded.
The word “globalization” in this context refers to convergence toward a stationary point from a broader set of initial conditions. It does not ordinarily imply computation of a global optimum for a nonconvex problem.
Constrained methods
Sequential quadratic programming forms a quadratic approximation to the Lagrangian while linearizing the constraints. A typical subproblem is
[ \begin{aligned} \min_d\quad & \nabla f(x_k)^{\mathsf T}d +\frac{1}{2}d^{\mathsf T}B_kd,\ \text{subject to}\quad & g_i(x_k)+\nabla g_i(x_k)^{\mathsf T}d\leq 0,\ & h_j(x_k)+\nabla h_j(x_k)^{\mathsf T}d=0, \end{aligned} ]
where (B_k) approximates the Hessian of the Lagrangian. Near a regular solution, the active constraints of the quadratic subproblem reproduce the local constraint geometry of the original problem.
Interior-point methods maintain strict inequality feasibility by introducing a barrier function. For inequalities (g_i(x)<0), a logarithmic barrier yields the parameterized objective
[ f(x)-\mu\sum_{i=1}^{m}\log!\bigl(-g_i(x)\bigr), ]
with (\mu>0). Solutions of the barrier problems trace a central path whose limiting behavior is connected to the KKT system.
Penalty methods incorporate constraint violations into the objective instead of excluding infeasible points. The augmented Lagrangian method combines multiplier estimates with penalty terms, reducing the extreme ill-conditioning associated with very large pure-penalty parameters.
Duality and sensitivity
The Lagrange dual function is defined by
[ q(\lambda,\nu)
\inf_x \mathcal{L}(x,\lambda,\nu), \qquad \lambda\geq 0. ]
For a minimization problem, every finite dual value provides a lower bound on the primal optimum. The difference between the primal and dual optimal values is the duality gap. Convexity together with a suitable regularity condition frequently makes this gap zero, whereas nonconvex programs may retain a positive gap.
Optimal multipliers also describe first-order sensitivity to perturbations of the constraints. When regularity and differentiability conditions hold, a multiplier measures the marginal change in the optimal value associated with a small change in the corresponding constraint bound. This interpretation connects nonlinear programming with shadow prices in mathematical economics and generalized forces in constrained mechanical systems.
Derivatives and computational representation
Derivative information can be supplied analytically or obtained through automatic differentiation. Automatic differentiation applies the chain rule to the sequence of elementary operations defining the model, producing derivatives that are exact up to floating-point roundoff. It differs from symbolic differentiation, which manipulates expressions, and from numerical differentiation, which estimates derivatives through finite perturbations.
Large nonlinear programs often have sparse Jacobian and Hessian matrices because each constraint depends on only part of the decision vector. Algorithms exploit this structure through sparse matrix factorizations and iterative linear solvers. In many practical computations, the cost and numerical stability of the linear algebra dominate the evaluation of the optimization model itself.
Stopping conditions usually combine stationarity, feasibility, and complementarity residuals into an approximate KKT measure. Because all computation occurs in finite precision, a reported solution represents satisfaction of these conditions within specified numerical tolerances rather than exact equality over the real numbers.
Applications
Nonlinear programming provides a common mathematical representation for equilibrium, design, estimation, and control problems whose governing relationships are not affine. In optimal control, discretization converts differential equations and trajectory restrictions into large structured nonlinear programs. In parameter estimation, nonlinear model predictions produce objectives based on residuals between observations and calculated responses.
Engineering design problems use nonlinear constraints to represent conservation laws, constitutive relations, and geometric compatibility. Economic models employ nonlinear objectives and constraints to express utility, production, and equilibrium relations. These applications differ in interpretation, but their numerical solution rests on the same interaction among local models, constraint geometry, and optimality conditions.