Optimization - Theory of Optimality

Theoretical Foundations of Optimization Introduction Optimization problems require us to find the best solution from a set of feasible choices. This unit covers the mathematical framework that guarantees optima exist, identifies where they must occur, and verifies when we've found them. Understanding these theoretical foundations is essential because they guide both how we formulate optimization problems and how we solve them numerically. Existence of Optima Before searching for a solution, we need to know that a solution actually exists. The extreme value theorem of Karl Weierstrass provides this guarantee: A continuous real-valued function on a compact set attains its maximum and minimum. What does this mean in practical terms? A compact set is a feasible region that is both closed (includes its boundaries) and bounded (doesn't extend to infinity). A continuous function is one without jumps or breaks. When both conditions hold, we're guaranteed that optimal solutions exist somewhere in our feasible region. This theorem motivates why we often constrain our optimization problems to bounded regions—it assures us we're not chasing an optimum that perpetually escapes us. Necessary Conditions for Optimality Once we know optima exist, the next question is: where can they be? We use conditions that any optimum must satisfy. Unconstrained Optimization: Fermat's Theorem For unconstrained problems (no restrictions on feasible choices), Fermat's theorem tells us where to look: An interior optimum of a differentiable function occurs where the gradient equals zero. The gradient is the vector of all first partial derivatives. At an optimum in the interior of the feasible region, the function is neither increasing nor decreasing in any direction—hence the gradient is zero. This creates a stationary point. For example, if $f(x, y) = x^2 + y^2 + 2xy + 5$, then: $$\nabla f = \left(\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right) = (2x + 2y, 2x + 2y)$$ Setting $\nabla f = 0$ gives us $x + y = 0$, pinpointing where optima can occur. Critical Points and the Feasible Region Optima don't occur only where the gradient is zero. Critical points include: Interior points where $\nabla f = 0$ Boundary points (the edges of the feasible region) Points where the gradient is undefined (in non-smooth functions) This is crucial: don't forget to check the boundaries! A function might have no interior optimum while achieving its best value on the boundary. Constrained Optimization: Lagrange Multipliers When we have equality constraints (requirements that certain equations must be satisfied), we can't simply set $\nabla f = 0$. Instead, we use Lagrange multipliers. For a problem: $$\text{minimize } f(x) \text{ subject to } g(x) = 0$$ we form the Lagrangian: $$L(x, \lambda) = f(x) - \lambda g(x)$$ where $\lambda$ is the Lagrange multiplier. At an optimum, the first-order conditions require: $$\nabla f(x^) = \lambda^ \nabla g(x^) \quad \text{and} \quad g(x^) = 0$$ The geometric intuition: at an optimum, the gradient of the objective function must be proportional to the gradient of the constraint. They're "aligned" in a specific way that respects the constraint surface. Karush–Kuhn–Tucker (KKT) Conditions Real-world problems often include inequality constraints (like $x \geq 0$ or $h(x) \leq b$). The Karush–Kuhn–Tucker (KKT) conditions extend Lagrange multipliers to handle these: $$\nabla f(x^) + \sumi \mui^ \nabla gi(x^) + \sumj \lambdaj^ \nabla hj(x^) = 0$$ where: $gi$ are equality constraints $hj$ are inequality constraints $\mui$ and $\lambdaj$ are corresponding multipliers Additional complementarity conditions require $\lambdaj^ hj(x^) = 0$ (each inequality multiplier is zero unless that constraint is active/binding) The KKT conditions are necessary for optimality in most practical problems—they tell us what an optimum must look like. Sufficient Conditions for Optimality Finding a point that satisfies first-order conditions doesn't guarantee it's actually an optimum. We need sufficient conditions—tests that confirm a point is truly optimal. The Hessian Matrix and Second-Order Conditions The Hessian matrix contains all second partial derivatives: $$H = \begin{pmatrix} \frac{\partial^2 f}{\partial x1^2} & \frac{\partial^2 f}{\partial x1 \partial x2} & \cdots \\ \frac{\partial^2 f}{\partial x2 \partial x1} & \frac{\partial^2 f}{\partial x2^2} & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}$$ The Hessian reveals the local curvature of the function: Positive-definite Hessian (all eigenvalues positive) ⇒ local minimum Negative-definite Hessian (all eigenvalues negative) ⇒ local maximum Indefinite Hessian (mixed signs) ⇒ saddle point (not an optimum) For constrained problems, we examine the bordered Hessian, which modifies the Hessian to account for constraint structure. Applying Second-Order Conditions If a candidate point $x^$ satisfies: First-order conditions (gradient is zero, or KKT conditions hold) Appropriate second-order conditions (Hessian has the right sign) then $x^$ is a locally optimal solution. The word "local" is important—it's optimal in a neighborhood around $x^$, but might not be globally best. Convexity and Global Optimality A remarkable simplification occurs with convex functions: for a convex objective function, any local minimum is automatically a global minimum. Why? Because the function has a "bowl shape"—it curves upward everywhere. Once you find the lowest point in a neighborhood, you've found the lowest point overall. This transforms local search into global optimization, which is computationally powerful. Non-convex functions lack this property. Multiple local minima can exist, and finding the global best requires more sophisticated techniques. Sensitivity and the Envelope Theorem After solving an optimization problem, we often ask: how does the optimal value change if parameters shift? The envelope theorem answers this. <extrainfo> The envelope theorem states that, under appropriate smoothness conditions, the rate of change of the optimal value with respect to a parameter equals the partial derivative of the Lagrangian with respect to that parameter, evaluated at the optimum. This process is called comparative statics in economics. </extrainfo> Solution Methods: Connecting Theory to Algorithms The theoretical conditions guide practical algorithms. Two major approaches for iterative solution are: Line-Search Methods Line-search methods optimize the objective along a single direction at each iteration. The algorithm: Chooses a search direction (often negative gradient) Finds the best step size along that direction Moves to the new point Repeats This is intuitive: you repeatedly ask "which direction should I move?" and "how far should I go?" Trust-Region Methods Trust-region methods take a different approach: instead of choosing a direction first, they: Build a simple model (usually quadratic) of the objective near the current point Assume this model is trustworthy within a limited region (the "trust region") Optimize the model within that region If the model was accurate, expand the trust region; if inaccurate, shrink it Trust-region methods are particularly robust when near difficult regions like saddle points. Practical Considerations for Global Optimization <extrainfo> Global optimizers (methods guaranteed to find the true global optimum) are typically much slower than sophisticated local methods like the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm, which efficiently exploits second-order information to navigate toward nearby optima. A practical strategy: run a local optimizer from multiple random starting points, then compare the best solutions found. This combines the speed of local methods with increased confidence in finding the global optimum. </extrainfo> Summary The complete optimization workflow rests on these theoretical pillars: Existence: Extreme value theorem guarantees optima exist on compact feasible regions Location: First-order conditions (gradient zero, Lagrange multipliers, KKT conditions) narrow where optima can be Verification: Second-order conditions (Hessian definiteness) confirm a point is truly optimal Global guarantees: Convexity simplifies the problem—local optima become global Practical solving: Algorithms like line search and trust region methods operationalize these concepts Understanding these foundations ensures you can formulate problems correctly, apply the right solution methods, and interpret results with confidence.