Nonlinear and Constrained Optimization

Introduction and context

Many business-analytics decisions are nonlinear. Revenue may depend multiplicatively on price and demand, risk may involve variances and covariances, and resource constraints may interact through capacity, budgets, service levels, and regulatory limits. Linear programming is powerful when relationships and feasible regions are linear, but it cannot represent every realistic decision model. Nonlinear and constrained optimization extends the analyst’s toolkit to these settings.

A general nonlinear program can be written as

Here, x ∈ ℝⁿ is the decision vector, f:ℝⁿ → ℝ is the objective function, g_i are inequality constraints, and h_j are equality constraints. Maximization can be converted to minimization by minimizing −f(x). The feasible set is the collection of points satisfying all constraints.

This chapter develops first- and second-order theory, numerical algorithms, constraint qualifications, Karush–Kuhn–Tucker conditions, and practical implementation issues. The emphasis is not merely on obtaining a numerical answer, but on understanding whether the answer is meaningful, stable, globally defensible, and appropriate for managerial use.

Learning objectives

By the end of this chapter, you should be able to:

1. Distinguish local and global optima in nonlinear models.
2. Apply gradient, Newton, quasi-Newton, and line-search methods.
3. Formulate and interpret Lagrangians and KKT conditions.
4. Explain constraint qualifications and their role in optimality theory.
5. Use penalty, barrier, and sequential quadratic programming methods.
6. Diagnose scaling, nonconvexity, infeasibility, and numerical failure.
7. Interpret multipliers as marginal values where the required regularity conditions hold.
8. Evaluate a nonlinear optimization solution in a business-analytics context.

1. Geometry and basic concepts

A point x^* is a local minimizer if there exists a neighborhood around it in which f(x^*) ≤ f(x) for every feasible x. It is a global minimizer if this inequality holds for every feasible point. A local solution may be useful but need not be globally best.

A differentiable unconstrained stationary point satisfies

where ∇f is the gradient, the column vector of first partial derivatives. A stationary point can be a local minimum, local maximum, or saddle point. The Hessian matrix is

For a twice continuously differentiable function, a sufficient local-minimum condition is that ∇f(x*) = 0 and ∇²f(x*) is positive definite. Positive definiteness means d^T∇²f(x*)d > 0 for every nonzero direction d. A negative-definite Hessian indicates a strict local maximum. An indefinite Hessian indicates a saddle point. A semidefinite Hessian gives an inconclusive second-order test.

Convexity is particularly important. A differentiable function is convex on a convex domain if

If f is convex and the feasible set is convex, every local minimum is global. If f is strictly convex, the minimizer is unique when it exists. For twice differentiable functions on an open convex domain, a positive semidefinite Hessian is sufficient for convexity, and a positive definite Hessian is sufficient for strict convexity. These are sufficient tests; they should not be applied outside their assumptions.

2. Unconstrained numerical search

2.1 Steepest descent

The negative gradient is the direction of greatest instantaneous decrease. Steepest descent uses

where α_k > 0 is a step length selected by an exact or inexact line search. An exact line search minimizes φ(α) = f(x_k − α∇f(x_k)) over positive α. In practice, Armijo or Wolfe conditions are usually preferred because exact one-dimensional minimization is expensive.

The Armijo sufficient-decrease condition is

where p_k is a descent direction, 0 < c₁ < 1, and α is reduced until the condition holds. Wolfe conditions add a curvature requirement and help prevent steps that are too short.

Steepest descent is simple and robust, but it may zig-zag severely on elongated quadratic contours. It is therefore often slow in large or ill-conditioned problems.

2.2 Newton’s method

Newton’s direction solves the local quadratic model

Its stationary equation gives

and the update is x_k+1 = x_k + α_kp_k. With α_k = 1, Newton’s method has quadratic local convergence near a solution when the Hessian is nonsingular and sufficiently smooth. However, far from a solution the Hessian may be indefinite, singular, or poorly conditioned. A line search, trust region, or modified Hessian is then required.

A trust-region method instead restricts the step by solving

where B_k approximates the Hessian and Δ_k is the trust-region radius. The ratio of actual to predicted improvement determines whether the radius is expanded or reduced.

2.3 Quasi-Newton methods

Quasi-Newton methods avoid forming or factoring the exact Hessian at every iteration. They maintain an approximation B_k to the Hessian or H_k ≈ (∇²f(x_k))^-1. The direction may be calculated as

After defining s_k = x_k+1 − x_k and y_k = ∇f(x_k+1) − ∇f(x_k), the BFGS inverse-Hessian update is

provided y_k^Ts_k > 0. A Wolfe line search commonly helps ensure this curvature condition. BFGS generally offers a strong balance between speed, memory, and robustness. L-BFGS stores only limited historical vectors and is suitable for very large models.

2.4 A small worked example

Consider f(x) = ½(x₁² + 4x₂²). Its gradient is ∇f(x) = (x₁, 4x₂)^T, and its Hessian is diag(1,4), which is positive definite. Starting at x₀ = (2,1)^T, steepest descent with α = 0.2 gives

∇f(x₀) = (2,4)^T and therefore x₁ = (2,1)^T − 0.2(2,4)^T = (1.6,0.2)^T. The objective decreases from f(x₀)=4 to f(x₁)=½(1.6² + 4×0.2²)=1.36. The origin is the unique global minimizer because the quadratic is strictly convex. The example also illustrates unequal curvature: the second coordinate changes more rapidly, creating the zig-zag behavior associated with steepest descent.

3. Constrained optimization and the Lagrangian

Constraints alter which directions are feasible. At a feasible point, a direction is feasible to first order if it does not increase an active inequality and preserves each equality to first order. An inequality g_i(x) ≤ 0 is active when g_i(x)=0; otherwise it is inactive.

For the standard minimization form, define the Lagrangian

where λ_i are inequality multipliers and μ_j are equality multipliers. The sign convention depends on whether constraints are written as g_i≤0 or g_i≥0; consistency is essential.

3.1 Constraint qualifications

Optimality conditions require a regularity assumption. Common constraint qualifications include:

• Linear independence constraint qualification (LICQ): gradients of all active inequalities and all equality constraints are linearly independent.
• Mangasarian–Fromovitz constraint qualification (MFCQ): equality gradients are linearly independent and there exists a direction satisfying all equality linearizations while strictly decreasing every active inequality.
• Slater’s condition: for a convex problem, there exists a point satisfying all equalities and strictly satisfying all inequalities. For convex programs, it supports strong duality and KKT sufficiency.

Without a suitable qualification, a local optimum may fail to possess conventional KKT multipliers. This is a theoretical issue with practical consequences: a solver’s multiplier output should not be interpreted automatically when constraint gradients are dependent or nearly dependent.

3.2 KKT conditions

Under an appropriate constraint qualification, a local solution x^* has multipliers λ^* and μ^* satisfying:

Complementary slackness states that either a constraint is slack and its multiplier is zero, or the constraint is active and its multiplier may be positive. KKT conditions are necessary under regularity. They are sufficient for global optimality when the objective and inequality functions are convex, equality constraints are affine, and the sign convention above is used.

For a single inequality example, minimize f(x)=x² subject to g(x)=1−x≤0, meaning x≥1. The Lagrangian is L=x²+λ(1−x). Stationarity gives 2x−λ=0. At the solution, feasibility requires x≥1. The unconstrained minimizer x=0 is infeasible, so the boundary solution is x^*=1. Stationarity then gives λ^*=2, and complementary slackness holds because g(1)=0. The multiplier measures the local increase in the optimal objective caused by tightening the lower-bound requirement, subject to regularity and the chosen units.

4. Algorithms for constrained nonlinear programs

4.1 Penalty methods

Penalty methods replace constraints with a cost for violation. A quadratic exterior penalty is

where ρ>0 is increased across a sequence of unconstrained problems. Equality violations are penalized directly; inequality violations are penalized only when positive. For finite ρ, the minimizer generally remains slightly infeasible. Very large penalties improve feasibility but can create ill-conditioning. Exact nonsmooth penalties, such as an L1 penalty, can achieve exact feasibility for sufficiently large finite parameters under suitable conditions, but are less smooth.

Penalty methods are useful for prototyping and when a solver does not support constraints directly. They should not be confused with a principled certificate of constrained optimality: feasibility and KKT residuals must still be checked.

4.2 Barrier methods

An interior-point logarithmic barrier keeps iterates strictly inside inequality constraints:

where τ>0. As τ→0^+, solutions of the barrier subproblem approach the constrained solution under appropriate regularity. The barrier is undefined at or outside the boundary, so an initially strictly feasible point is normally needed, or a feasibility-restoration phase must be used. Barrier methods are especially effective for large sparse convex programs and are central to modern interior-point algorithms.

4.3 Sequential quadratic programming

Sequential quadratic programming (SQP) solves a quadratic programming approximation at each iteration. Given x_k, a typical subproblem is

The QP supplies a step p_k and an estimate of the multipliers. A merit function, filter method, or trust region balances objective reduction and constraint satisfaction. Near a regular solution, accurate Hessian information and a suitable line search can give rapid convergence. SQP is often the method of choice for medium-scale smooth nonlinear programs with significant constraints.

4.4 Choosing a method

The method should be selected after examining differentiability, sparsity, convexity, scaling, and the reliability of function and derivative evaluations.

5. A complete illustrative case: promotional allocation

Background

A retailer allocates a continuous promotional budget between two campaigns. Let x₁ and x₂ denote spending in thousands of currency units. The estimated incremental contribution is

The square-root terms represent diminishing returns, while the linear terms represent spending cost. The retailer has a total budget of 10 and requires at least 1 unit in each channel.

Problem formulation

Maximize R(x), equivalently minimize f(x)=−R(x), subject to

For x_i>0, the contribution function is concave because its Hessian is diagonal with entries −2x₁^−3/2 and −1.5x₂^−3/2, both negative. Maximizing a concave function over a convex feasible set is a convex optimization problem in the maximization convention; therefore any KKT solution is globally optimal.

Analysis

The unconstrained first-order conditions are

4/√x₁ − 0.5 = 0 and 3/√x₂ − 0.4 = 0. Hence √x₁=8, so x₁=64, and √x₂=7.5, so x₂=56.25. These values violate the budget, so the budget constraint binds. The lower bounds do not bind at the optimum because the marginal returns near 1 are high.

Using a multiplier λ≥0 for x₁+x₂−10≤0, the maximization stationarity equations can be written as

4/√x₁ − 0.5 − λ = 0 and 3/√x₂ − 0.4 − λ = 0, together with x₁+x₂=10. Solving these equations numerically gives approximately λ≈0.91, x₁≈5.58, and x₂≈4.42. Substitution verifies the budget total to rounding. The marginal contributions net of direct spending cost are approximately equal across the two active allocation choices, as required by optimality.

Interpretation and governance

The allocation is a model-based recommendation, not an automatic managerial decision. The multiplier indicates the approximate improvement in optimal contribution per additional thousand currency units of budget, locally and within the model. It is not a causal estimate unless the response model was identified causally. Analysts should test sensitivity to response parameters, include uncertainty intervals, and avoid reallocating budgets solely because an optimizer produces many decimal places.

A robust implementation would:

1. Validate the response model on holdout campaigns.
2. Check whether square-root behavior remains plausible outside observed data.
3. Run scenario and sensitivity analyses.
4. Record constraints, parameter versions, solver tolerances, and approval decisions.
5. Monitor realized returns and recalibrate rather than treating the solution as permanent.

6. Practical implementation and diagnostics

Derivatives and automatic differentiation

Analytic derivatives are usually most accurate. Automatic differentiation can compute exact derivatives of implemented computational graphs, often improving reliability over finite differences. Finite differences remain useful for checking derivatives, but step-size choice is delicate: steps that are too small suffer cancellation, while steps that are too large incur truncation error.

Scaling

If one variable is measured in millions and another in fractions, the Hessian and constraint Jacobian may become ill-conditioned. Rescaling variables, objectives, and constraints to comparable magnitudes often improves convergence. Scaling must be reversed carefully when interpreting multipliers.

Stopping criteria

A credible stopping rule examines more than the change in objective. Typical diagnostics include:

• stationarity residual: norm of the Lagrangian gradient;
• primal feasibility residual: constraint violation;
• complementarity residual: magnitude of λ_i g_i(x);
• step norm and objective change;
• dual feasibility, including nonnegative inequality multipliers.

A solver’s status message is evidence, not proof. Independent evaluation of objective, constraints, gradients, and KKT residuals is good practice.

Nonconvexity and global search

Nonconvex models may contain multiple local minima, disconnected feasible regions, or saddle points. Multi-start local optimization, continuation, interval methods, branch-and-bound for suitable structures, and evolutionary or Bayesian global methods can be combined. Heuristics may discover good candidates but normally do not establish global optimality. A defensible report should state whether the result is locally certified, globally certified, or merely the best solution found under a search budget.

Noisy objectives and machine learning

When the objective comes from simulation, experimentation, or a predictive model, function values may be noisy and gradients may be biased. Smooth deterministic algorithms can then overreact to estimation noise. Sample-average approximation, stochastic approximation, robust optimization, distributionally robust optimization, and derivative-free trust-region methods are relevant alternatives. In machine-learning applications, constrained optimization may enforce fairness, safety, calibration, or resource limits; constraints must be defined carefully because proxy metrics can conceal disparate impacts.

7. Limitations, ethics, and contemporary practice

Optimization formalizes a decision criterion; it does not decide which criterion is socially legitimate. A mathematically optimal workforce schedule may create unacceptable fatigue, a pricing model may disadvantage protected groups, and a risk model may optimize a poorly measured proxy. Governance should therefore include stakeholder review, impact assessment, explainability proportional to risk, audit trails, privacy protection, and human override procedures.

Important limitations include model misspecification, uncertain parameters, infeasible requirements, hidden integer decisions, and sensitivity to outliers. If decisions are discrete, rounding a continuous solution can violate constraints or destroy optimality; mixed-integer nonlinear programming may be required. If data are changing, solutions should be stress-tested under plausible distribution shifts.

Contemporary solvers increasingly combine sparse automatic differentiation, parallel linear algebra, interior-point methods, SQP, and differentiable optimization layers. Differentiable optimization can embed a solver inside a predictive pipeline, but it introduces concerns about solver convergence, discontinuities, and the validity of gradients through approximate solutions. Reproducibility requires recording data, code, solver version, tolerances, initialization, random seeds, and stopping status.

Best-practice workflow

1. Define decisions, units, objective, and constraints in plain language.
2. Convert the model to a consistent mathematical sign convention.
3. Examine feasibility before optimizing.
4. Assess smoothness, convexity, sparsity, and conditioning.
5. Derive or automatically compute gradients and, where useful, Hessians.
6. Scale variables and constraints.
7. Select a solver aligned with model structure.
8. Use multiple starts or global methods when nonconvexity is material.
9. Verify feasibility, stationarity, complementarity, and sensitivity independently.
10. Communicate uncertainty, assumptions, active constraints, and managerial implications.
11. Monitor outcomes and update the model as evidence changes.

Chapter Summary

Nonlinear optimization extends decision analysis beyond linear relationships and enables realistic treatment of diminishing returns, interaction effects, risk, and nonlinear resource constraints. Gradients identify first-order change; Hessians describe curvature. Steepest descent is simple but can be slow, Newton’s method is locally fast but demands reliable curvature, and quasi-Newton methods provide a practical compromise.

Constrained problems require attention to feasible directions, active constraints, constraint qualifications, and the Lagrangian. KKT conditions combine stationarity, primal feasibility, dual feasibility, and complementary slackness. Under convexity and suitable regularity, they provide a global optimality certificate. Penalty methods trade feasibility against conditioning, barrier methods remain interior, and SQP solves successive quadratic approximations.

A professional solution is not defined by a solver’s output alone. It requires correctly scaled models, validated derivatives, feasibility and KKT diagnostics, sensitivity analysis, awareness of nonconvexity, and governance of data, assumptions, fairness, and implementation.

Key Terms

Gradient: Vector of first partial derivatives of a scalar function.

Hessian: Matrix of second partial derivatives.

Stationary point: Point at which the gradient is zero in an unconstrained problem.

Local minimum: Feasible point minimizing the objective in a neighborhood.

Global minimum: Feasible point minimizing the objective over the entire feasible set.

Convex function: Function satisfying the convex-combination inequality.

Feasible set: All points satisfying the constraints.

Active constraint: Inequality holding with equality at a point.

Lagrangian: Objective augmented by weighted constraints.

Lagrange multiplier: Variable associated with a constraint, often interpreted as a local shadow value.

Constraint qualification: Regularity condition supporting optimality theory.

LICQ: Linear independence constraint qualification.

KKT conditions: First-order conditions involving stationarity, feasibility, duality, and complementarity.

Complementary slackness: Requirement that each inequality multiplier times its slack is zero.

Penalty method: Method that incorporates constraint violation into an augmented objective.

Barrier method: Method that prevents violation by adding a boundary barrier.

SQP: Sequential quadratic programming, which solves local quadratic approximations.

Line search: Procedure selecting a step length along a search direction.

Trust region: Neighborhood restricting the step of a local model.

Conditioning: Sensitivity of a numerical problem to perturbations in data or computation.

Review Questions

Short Answer Questions

1. What distinguishes a local minimum from a global minimum?
2. Why can steepest descent be slow on elongated quadratic contours?
3. State the four groups of KKT conditions.
4. What is the purpose of a constraint qualification?
5. How do penalty and barrier methods treat constraint violations differently?

Long Answer Questions

1. Derive the Newton direction from a second-order Taylor approximation and explain why a line search may still be necessary.
2. Explain convexity, positive semidefinite Hessians, and the relationship between local and global optima.
3. Compare BFGS, interior-point, penalty, and SQP methods in terms of assumptions, strengths, and limitations.
4. Explain the economic interpretation of an inequality-constraint multiplier and identify conditions under which that interpretation can fail.
5. Discuss how scaling, derivative accuracy, and stopping criteria affect the reliability of nonlinear optimization results.

Analytical / Application Questions

1. Formulate a nonlinear product-mix model with diminishing returns, a labor constraint, and minimum production requirements. Identify its variables, objective, constraints, and likely active constraints.
2. For minimizing f(x)=½(x₁²+2x₂²) subject to x₁+x₂≥3, derive the KKT conditions and solve for the optimum.
3. A predictive model recommends a budget allocation but violates a regulatory constraint by a small amount. Analyze whether a penalty method, barrier method, or SQP approach is most appropriate, and specify the diagnostics you would report.

Multiple Choice Questions with Answers

Question 1

Which condition is sufficient for a differentiable unconstrained stationary point to be a strict local minimum?

A. The Hessian is negative definite

B. The Hessian is positive definite

C. The gradient is nonzero

D. The objective is discontinuous

Correct Answer: B. The Hessian is positive definite

Question 2

In the standard minimization convention with constraints g_i(x)≤0, which KKT condition applies to inequality multipliers?

A. λ_i≤0

B. λ_i=1 for every active constraint

C. λ_i≥0

D. λ_i can have any sign only when constraints are active

Correct Answer: C. λ_i≥0

Question 3

What does complementary slackness require?

A. Every constraint must be active

B. Every multiplier must be positive

C. The product of each inequality multiplier and its constraint value is zero

D. The objective gradient must be zero without multipliers

Correct Answer: C. The product of each inequality multiplier and its constraint value is zero

Question 4

For f(x)=x² subject to x≥1, what is the optimal solution?

A. x=−1

B. x=0

C. x=1

D. The problem is infeasible

Correct Answer: C. x=1

Question 5

Which method maintains strict interiority by using logarithmic terms such as −τlog(−g_i(x))?

A. Exterior penalty

B. Barrier method

C. Steepest descent

D. BFGS

Correct Answer: B. Barrier method

Question 6

What is the principal advantage of a quasi-Newton method such as BFGS?

A. It guarantees global optimality for nonconvex problems

B. It avoids all derivative information

C. It approximates curvature without recomputing the exact Hessian at every iteration

D. It permits infeasible equality constraints at the final solution

Correct Answer: C. It approximates curvature without recomputing the exact Hessian at every iteration

Question 7

In SQP, the subproblem is typically what type of optimization problem?

A. A quadratic program based on local approximations

B. A linear regression problem

C. An unconstrained integer program only

D. A differential-equation solver

Correct Answer: A. A quadratic program based on local approximations

Question 8

Under convexity, what is the significance of a KKT point when the relevant regularity conditions hold?

A. It is necessarily a global optimum

B. It is necessarily infeasible

C. It is necessarily a saddle point

D. It proves the model has no uncertainty

Correct Answer: A. It is necessarily a global optimum

Question 9

For f(x)=½(x₁²+4x₂²), what is f(2,1)?

A. 2

B. 4

C. 6

D. 8

Correct Answer: B. 4

Question 10

Which diagnostic directly measures whether inequality constraints are respected?

A. Primal feasibility residual

B. Hessian determinant only

C. Number of variables

D. Initial objective value only

Correct Answer: A. Primal feasibility residual