Nonlinear Programming
- Introduced by
- Jorge Nocedal & Stephen Wright
- Year
- 2006
- Type
- Continuous mathematical optimization
- Family
- Mathematical programming
What does it do?
Nonlinear programming (NLP) is a branch of mathematical optimization concerned with problems in which the objective function or at least one constraint is nonlinear.
Formalized comprehensively by Jorge Nocedal and Stephen Wright in their seminal 2006 text, NLP encompasses gradient-based algorithms — including sequential quadratic programming (SQP), interior-point methods, and quasi-Newton approaches — for finding locally or globally optimal solutions to continuous decision problems arising across engineering, economics, and the physical sciences.
The intuition behind the method
Imagine descending a hilly, fog-covered landscape while staying inside a fenced region. You cannot see the entire terrain, so you feel the slope beneath your feet (gradient), adjust your step direction to go downhill, and check at each move that you have not crossed the fence (constraints). If the fence bends or the hills overlap, simple straight-line paths will not work — you must curve your path. Nonlinear programming formalizes exactly this process, replacing intuitive hill-walking with mathematically rigorous step-size and direction rules.
History
The theoretical foundations of nonlinear programming trace to the KKT conditions derived by Karush (1939) and Kuhn and Tucker (1951). Practical algorithms accelerated during the 1960s–1980s with the development of SQP methods, augmented Lagrangian approaches, and quasi-Newton updates including BFGS (1970). Nocedal and Wright's 2006 second edition of Numerical Optimization became a definitive reference, synthesizing convergence theory, line-search and trust-region frameworks, and interior-point methods into a coherent modern treatment.
When to use it
Use nonlinear programming when the objective or constraints cannot be linearized without material loss of accuracy and the decision variables are continuous. Typical settings include engineering design with physical law constraints, portfolio optimization with nonlinear risk measures, and regression with nonlinear model forms. Key assumptions are that f and c are at least twice continuously differentiable (for gradient-based solvers) and that constraint qualifications hold. When variables are integer-valued, mixed-integer nonlinear programming (MINLP) extensions apply. For convex problems, interior-point methods guarantee global optimality; for non-convex problems, only local guarantees exist.
Limitations and considerations
- Non-convex problems offer only local optimality guarantees; global solutions require additional global search strategies.
- Requires objective and constraints to be smooth (at least differentiable); non-smooth problems need specialized subdifferential methods.
- Computational cost grows substantially with problem size when exact Hessian evaluation is required.
- Constraint qualifications may fail (e.g., at degenerate feasible points), causing KKT conditions to lose their theoretical grounding.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Handles a wide class of real-world problems where linear or quadratic approximations are insufficient.
- Mature algorithmic theory with well-studied convergence guarantees for convex instances.
- Efficient gradient-based solvers (SQP, interior-point) scale to thousands of variables in practice.
- Unified Lagrangian framework accommodates mixed equality and inequality constraints naturally.
Applications
- Structural and aerospace engineering: minimizing weight subject to stress and deflection constraints.
- Portfolio management: maximizing expected return subject to a nonlinear variance (risk) budget.
- Chemical process design: optimizing reactor yield subject to thermodynamic and safety constraints.
- Machine learning: training neural networks and kernel models via unconstrained or constrained NLP solvers.
- Energy systems: optimal power flow problems in electricity grid dispatch with nonlinear physical constraints.
How it works
How it works
The analyst defines a scalar objective f(x) to minimize or maximize over decision variables x in R^n, together with equality constraints c_i(x) = 0 and inequality constraints c_j(x) >= 0. Identifying which constraints are active at a candidate solution and whether regularity conditions (constraint qualifications) hold is critical at this stage and determines what optimality theory applies.
Formula
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}The Karush-Kuhn-Tucker (KKT) conditions provide first-order necessary conditions for a local optimum. They require stationarity of the Lagrangian, complementary slackness for inequality multipliers (lambda_j c_j = 0), dual feasibility (lambda_j >= 0), and primal feasibility. Algorithms iteratively construct iterates that satisfy these conditions progressively more tightly, with second-order sufficiency conditions confirming that a stationary point is indeed a local minimum.
Formula
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}At each iteration k an algorithm computes a search direction p_k — typically via a quasi-Newton approximation B_k of the Hessian (e.g., BFGS) or an exact second-derivative system — and a step length alpha_k satisfying Wolfe or Armijo conditions. SQP methods solve a quadratic subproblem for p_k, while interior-point methods add barrier terms to handle inequality constraints and drive iterates toward the feasible interior.
Formula
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)Termination occurs when both the gradient norm of the Lagrangian and the maximum constraint violation fall below prescribed tolerances (epsilon and delta). Because NLP is generally non-convex, algorithms may converge to local optima; multiple restarts from different starting points or global search strategies (branch-and-bound, multistart) are recommended when global optimality is required.
Formula
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaCommon pitfalls
- Ignoring constraint qualifications and blindly applying KKT conditions at degenerate or infeasible points leads to spurious solutions.
- Using poorly scaled variables causes ill-conditioned Hessian approximations and slow or failed convergence.
- Accepting the first local minimum found without multiple restarts in non-convex settings may miss the global optimum significantly.
- Finite-difference gradient approximations introduce numerical error; analytic or automatic differentiation is strongly preferred.
Frequently asked questions
Is every linear program also a nonlinear program?
Yes. Linear programming is a special case of NLP where both the objective and all constraints are affine. However, LP admits the simplex and interior-point algorithms that exploit linearity and are far more efficient than general NLP solvers; using a general NLP solver for an LP is wasteful but mathematically valid.
When can I trust that a KKT point is a global minimum?
When the NLP is convex — meaning f is convex and the feasible set is a convex set — any KKT point is a global minimum. For non-convex problems this guarantee does not hold, and a KKT point is only a local minimum (under second-order sufficiency conditions). Global optimization methods such as branch-and-bound or convex relaxations are needed otherwise.
What is the difference between SQP and interior-point methods?
SQP iteratively solves quadratic programming subproblems that approximate the NLP locally and is often preferred for small-to-medium problems with many active constraints. Interior-point (barrier) methods stay strictly inside the feasible region and tend to scale better for large sparse problems. Both converge superlinearly under appropriate regularity conditions.
Related methods
Sources
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Copied.