Optimization Theory: Finding Optimal Solutions
Introduction
Optimization is the mathematics of making things better. From a logistics company minimizing delivery routes to a machine learning engineer minimizing prediction error, optimization problems ask the same question: among all possible choices, which one gives the best outcome? The answer drives decisions across engineering, economics, operations research, and data science.
An optimization problem has three components: decision variables represent the choices we can make, an objective function measures how good a choice is, and constraints limit the feasible choices. The goal is to find decision variables that minimize (or maximize) the objective while satisfying the constraints. This simple framework captures an extraordinary range of practical problems.
Unconstrained Optimization
Unconstrained optimization seeks the minimum of a function without any restrictions on the variables. The simplest case — minimizing a function of one variable — uses calculus: set the derivative to zero and check the second derivative to confirm a minimum.
Optimality Conditions
For a differentiable function f(x), a necessary condition for a local minimum is that the gradient ∇f(x*) = 0. Sufficient conditions require the Hessian matrix ∇²f(x*) to be positive definite — all eigenvalues positive. A critical point satisfying these conditions is a strict local minimum.
Convex functions are the ideal case for optimization. A function is convex if the line segment between any two points lies above the graph. Convex functions have a single global minimum, and any local minimum is global. Gradient methods applied to convex functions converge to the global minimum regardless of starting point.
Gradient Descent
Gradient descent is the workhorse optimization algorithm. Starting from an initial guess, it moves in the direction of steepest descent: x_{k+1} = x_k − α∇f(x_k). The step size α controls how far to move each iteration. Too large, and the algorithm diverges. Too small, and convergence is impractically slow.
Line search methods choose the step size optimally at each iteration. Backtracking line search starts with a large step and shrinks it until the function decreases sufficiently. Conjugate gradient methods accelerate convergence by incorporating information from previous steps.
Newton’s Method
Newton’s method uses second-derivative information for faster convergence. The update x_{k+1} = x_k − [∇²f(x_k)]⁻¹∇f(x_k) achieves quadratic convergence near the optimum. Each iteration requires computing and inverting the Hessian, which is expensive for high-dimensional problems.
Quasi-Newton methods like BFGS approximate the Hessian using gradient information from previous iterations, combining the fast convergence of Newton’s method with the modest per-iteration cost of gradient descent.
Constrained Optimization
Most real problems have constraints. A manufacturer cannot use negative quantities of raw materials. A portfolio cannot have negative weights. A structural design must stay within stress limits. Constrained optimization handles these restrictions.
Equality Constraints
Problems with equality constraints minimize f(x) subject to h_i(x) = 0. The method of Lagrange multipliers introduces a Lagrange multiplier λ_i for each constraint. The Lagrangian L(x, λ) = f(x) + Σ λ_i h_i(x) converts the constrained problem to an unconstrained one in the combined variables.
The necessary conditions for optimality require ∇L = 0: the gradient of f is a linear combination of the constraint gradients. Geometrically, at the optimum, moving in any direction tangent to all constraints does not decrease f.
Sensitivity and Shadow Prices
The Lagrange multipliers have a concrete economic interpretation. The optimal value λ_i* measures the sensitivity of the optimal objective to changes in the right-hand side of constraint i: ∂f*/∂b_i = −λ_i*. In constrained optimization, these are shadow prices — the marginal value of relaxing each constraint.
In a production problem where a resource constraint has shadow price $10 per unit, acquiring one additional unit of that resource increases profit by $10. Resources with zero shadow price are abundant and do not constrain the optimum. Sensitivity analysis determines the range over which these shadow prices remain valid before the optimal basis changes.
Problems with equality constraints minimize f(x) subject to h_i(x) = 0. The method of Lagrange multipliers introduces a Lagrange multiplier λ_i for each constraint. The Lagrangian L(x, λ) = f(x) + Σ λ_i h_i(x) converts the constrained problem to an unconstrained one in the combined variables.
The necessary conditions for optimality require ∇L = 0: the gradient of f is a linear combination of the constraint gradients. Geometrically, at the optimum, moving in any direction tangent to all constraints does not decrease f.
Inequality Constraints
Inequality constraints g_i(x) ≤ 0 introduce the Karush-Kuhn-Tucker (KKT) conditions. At the optimum, each inequality is either active (g_i(x*) = 0) or inactive (g_i(x*) < 0). The multiplier for an active constraint is nonnegative, while inactive constraints have zero multiplier.
The KKT conditions generalize Lagrange multipliers to inequality constraints and are the foundation of constrained optimization theory. Interior point methods solve large-scale constrained problems by following the central path through the interior of the feasible region.
Convex Optimization
Convex optimization minimizes a convex function over a convex set. The feasible set is convex if the line segment between any two feasible points lies entirely within the set. Convex problems have the property that any local minimum is global.
Linear Programming
A linear program (LP) minimizes a linear objective subject to linear equality and inequality constraints. The standard form is min cᵀx subject to Ax = b, x ≥ 0. The feasible region is a convex polytope, and the optimum occurs at a vertex.
The simplex method traverses vertices of the feasible polytope, moving to neighboring vertices with better objective values. Interior point methods approach the optimum through the interior of the feasible region. Both methods solve LPs with millions of variables and constraints in practical time. Linear programming finds extensive use in supply chain optimization, portfolio optimization, and resource allocation, as detailed in linear programming.
Duality in Convex Optimization
Every convex optimization problem has a dual problem that provides a lower bound on the optimal value. Weak duality always holds: the dual objective is always less than or equal to the primal objective. Strong duality holds for convex problems under Slater’s condition: there exists a strictly feasible point satisfying all inequality constraints with strict inequality.
The dual problem often has nice properties even when the primal is difficult to solve. The dual of a support vector machine is a quadratic program with box constraints, efficiently solvable by sequential minimal optimization. The dual of an optimal transport problem is a maximization over potential functions, providing insight into the geometry of the problem.
Semidefinite and Second-Order Cone Programming
Semidefinite programming extends linear programming to optimize over the cone of positive semidefinite matrices. It arises in control theory, structural optimization, and quantum information theory. Second-order cone programming handles constraints involving Euclidean norms, appearing in portfolio optimization with risk constraints and robust optimization.
Global Optimization
Convex problems guarantee global optimality, but many practical problems are nonconvex. Neural network training minimizes a highly nonconvex loss function. Molecular conformation problems have multiple local minima. Global optimization seeks the best possible solution rather than a local optimum.
Stochastic Methods
Simulated annealing draws inspiration from thermodynamics, allowing occasional uphill moves to escape local minima. The probability of accepting a worse solution decreases over time according to a cooling schedule. Starting at a high temperature allows exploration; gradually reducing the temperature focuses exploitation near promising regions.
Genetic algorithms maintain a population of candidate solutions, evolving them through selection, crossover, and mutation. Selection favors fitter individuals. Crossover combines features from two parents. Mutation introduces random variations. These methods do not guarantee finding the global optimum but often find good solutions for difficult nonconvex problems with many local minima.
Branch and Bound
Branch and bound systematically explores the feasible region by partitioning it into smaller subproblems and computing bounds on the optimal value. Subproblems whose bound is worse than the current best solution are pruned. This approach solves mixed-integer programming problems exactly, though worst-case runtime grows exponentially.
The efficiency of branch and bound depends on the quality of the bounds. Tighter bounds prune more branches, reducing the search tree. Lagrange relaxation and semidefinite programming relaxations provide high-quality bounds for many combinatorial optimization problems, including the traveling salesman problem and graph partitioning.
Branch and bound systematically explores the feasible region by partitioning it into smaller subproblems and computing bounds on the optimal value. Subproblems whose bound is worse than the current best solution are pruned. This approach solves mixed-integer programming problems exactly, though worst-case runtime grows exponentially.
Applications
Machine learning trains models by minimizing loss functions. Linear regression has a closed-form solution via the normal equations. Logistic regression and neural networks require iterative optimization methods like stochastic gradient descent.
Operations research optimizes logistics, manufacturing, and service systems. Airlines use optimization to schedule crews and aircraft. Warehouses use optimization to locate inventory. Delivery services use optimization to route vehicles.
Engineering design optimizes structures for minimum weight subject to strength constraints. Chemical processes optimize yields subject to safety constraints. Financial portfolios optimize returns subject to risk constraints.
What makes a problem convex? A convex problem has a convex objective function and a convex feasible set. The defining property is that the line segment between any two feasible points lies entirely within the feasible set, and the objective along that segment is at most the linear interpolation.
When should I use gradient descent versus Newton’s method? Use gradient descent for high-dimensional problems where computing the Hessian is impractical. Use Newton’s method when the Hessian is available and the problem dimension is moderate.
What is the difference between a local and global optimum? A local optimum is the best point in its immediate neighborhood. A global optimum is the best point among all feasible points. Convex problems have no distinction — every local optimum is global.
How do Lagrange multipliers work? Lagrange multipliers convert a constrained problem into an unconstrained one by adding penalty terms for constraint violations. The multipliers represent the sensitivity of the optimal objective to constraint relaxation.
Linear Programming — Calculus Basics Guide — Computational Mathematics