Computational Optimization Methods

Computational Optimization Techniques Overview: Three Approaches to Solving Optimization Problems When solving optimization problems computationally, three fundamentally different strategies exist: Exact algorithms solve problems completely and precisely in a finite number of steps Iterative methods start from an initial guess and progressively improve the solution, converging toward an optimum Heuristic and metaheuristic algorithms trade guaranteed optimality for computational speed and simplicity, often working well in practice even without convergence guarantees The choice among these depends on your problem structure, required accuracy, and computational budget. Exact Algorithms Exact algorithms guarantee finding the true optimal solution. They work best for problems with special structure—particularly linear and combinatorial problems—where that structure can be exploited. The Simplex Algorithm for Linear Programming The Simplex algorithm is the workhorse for linear programming problems of the form: $$\text{minimize} \quad \mathbf{c}^T \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$$ The algorithm works by moving from one vertex (corner point) of the feasible region to an adjacent vertex with a better objective value. Because the feasible region is a convex polyhedron with finitely many vertices, the algorithm terminates in a finite number of steps. In practice, it solves problems with thousands of variables efficiently. Key understanding: The Simplex method exploits linearity—the optimal solution always lies at a vertex, so you only need to check vertices, not the entire region. Extensions and Variants The Simplex framework extends to related problem classes: Quadratic programming problems (with quadratic objectives) can be solved using extensions like Sequential Quadratic Programming, which applies Newton-type steps to handle the curvature. Network-flow Simplex variants specialize in transportation and network problems by exploiting their structure, producing specialized Simplex implementations that are even faster. Combinatorial algorithms (shortest path, minimum spanning tree, maximum matching) solve discrete optimization using problem-specific techniques rather than general-purpose Simplex. Iterative Methods Unlike exact algorithms, iterative methods don't guarantee finding the exact solution in finite time. Instead, they generate a sequence of improving approximations. You stop when the solution is "close enough" for your purposes. All iterative methods follow a basic pattern: start with an initial guess $\mathbf{x}0$, then repeatedly compute $\mathbf{x}{k+1}$ using information from $\mathbf{x}k$ (and possibly earlier iterates). The quality of an iterative method is measured by its convergence rate—how quickly the error shrinks. Methods Using Second Derivative Information (Hessians) Newton's Method Newton's method uses the Hessian matrix (matrix of second partial derivatives) to achieve quadratic convergence—meaning the number of accurate digits roughly doubles with each iteration. This is exceptionally fast. The Newton step at iteration $k$ is: $$\mathbf{x}{k+1} = \mathbf{x}k - H(\mathbf{x}k)^{-1} \nabla f(\mathbf{x}k)$$ where $H(\mathbf{x}k)$ is the Hessian and $\nabla f(\mathbf{x}k)$ is the gradient. Why it's fast: Newton's method uses the curvature (Hessian) to predict where the optimum actually is, not just the steepness (gradient). For smooth problems near a minimum, this prediction is very accurate, especially as you approach the solution. When to use it: When you have a smooth, twice-differentiable objective and you're willing to compute or estimate Hessians. Interior-Point Methods for Constrained Problems Interior-point methods solve large constrained optimization problems by converting constraints into penalty terms and applying Newton-like steps. Intuitively, they keep the solution in the interior of the feasible region while gradually enforcing constraints—hence the name. Key advantage: They handle large, structured problems much better than Simplex for nonlinear constraints. Some variants require only gradient information (reducing computational cost), while others need full Hessians (for faster convergence). Sequential Quadratic Programming (SQP) SQP extends Newton's method to handle constraints by repeatedly solving quadratic programming subproblems. It combines the fast convergence of Newton's method with the ability to handle constraints, making it effective for moderate-sized constrained problems. Important caveat: SQP requires second derivatives, which can be computationally expensive or unavailable in practice. Gradient-Based Methods (First-Derivative Only) These methods use only first derivatives (gradients), avoiding the computational cost of computing Hessians. The tradeoff is slower convergence—typically linear rather than quadratic. Gradient Descent (Steepest Descent) Gradient descent is the simplest iterative method: at each step, move a small distance in the direction opposite the gradient: $$\mathbf{x}{k+1} = \mathbf{x}k - \alphak \nabla f(\mathbf{x}k)$$ where $\alphak$ is a small step size. Why it works: The negative gradient points in the direction of steepest decrease, so taking steps downhill eventually reaches a local minimum. Limitation: Gradient descent converges slowly, especially when the problem is "ill-conditioned"—when the landscape has narrow valleys. The algorithm zigzags down the valley rather than cutting across it. Conjugate Gradient Methods Conjugate gradient methods solve unconstrained problems much faster than gradient descent by choosing search directions that are mutually "conjugate" (orthogonal with respect to the Hessian). The method solves quadratic problems exactly in $n$ iterations for an $n$-dimensional problem, and works well as an iterative method for non-quadratic smooth problems. Why it matters: Conjugate gradient requires only gradients (like steepest descent) but converges much faster. It's invaluable for large, sparse, well-conditioned problems. Quasi-Newton Methods Quasi-Newton methods (including BFGS and L-BFGS) approximate the Hessian rather than computing it exactly. They build up an estimate of the Hessian from gradients at successive points, achieving superlinear convergence (faster than linear, though not quite quadratic) without the cost of computing second derivatives. Why they're popular: They offer a practical middle ground—much faster than gradient descent, with quadratic-like speed in practice, but requiring only gradients. Coordinate Descent Coordinate descent updates one variable at a time while keeping others fixed. At iteration $k$, it solves: $$xj = \arg\min{xj} f(x1, \ldots, x{j-1}, xj, x{j+1}, \ldots, xn)$$ for some chosen index $j$ (usually cycled through all indices). Advantage: Each update is often simple and fast, especially when single-variable subproblems are easy to solve. This makes coordinate descent popular in machine learning and statistics. Tradeoff: Convergence can be slow if variables are highly interdependent. Conditional Gradient Method (Frank–Wolfe) The Frank–Wolfe method exploits problems with special structure—specifically, problems with linear constraints. Rather than moving anywhere in the feasible region, it: Finds the linear constraint that creates the steepest descent (a simple linear programming problem) Takes a step toward that constraint Advantage: Each iteration is cheap (solving a linear program), useful when the constraint set has special structure. Subgradient Methods Most methods assume the function is differentiable. Subgradient methods generalize gradient descent to handle non-smooth (non-differentiable) convex functions by using subgradients—generalized notions of slopes. Tradeoff: They converge more slowly and require special step-size selection, but they handle problems that smooth methods cannot. <extrainfo> Ellipsoid Method The ellipsoid method provides polynomial-time convergence guarantees for convex problems. While rarely used in practice (gradient methods are faster empirically), it was historically important in proving that linear programming is polynomial-time solvable—a major theoretical result. Simultaneous Perturbation Stochastic Approximation (SPSA) SPSA estimates gradients by perturbing the input slightly and measuring how the function changes. This is useful when exact gradients are unavailable or expensive to compute (e.g., in simulation-based optimization), though it requires more function evaluations. </extrainfo> Derivative-Free Methods When analytic derivatives are unavailable or prohibitively expensive, finite-difference approximation estimates gradients by evaluating the function at nearby points: $$\frac{\partial f}{\partial xj} \approx \frac{f(\mathbf{x} + h \mathbf{e}j) - f(\mathbf{x})}{h}$$ where $\mathbf{e}j$ is the $j$-th unit vector and $h$ is a small step size. Tradeoff: This converts a derivative-free problem into a gradient-based one, but requires $n$ extra function evaluations per gradient estimate in dimension $n$. More sophisticated derivative-free methods exist (like the Nelder–Mead simplex heuristic), but all derivative-free optimization is generally slower than using true derivatives. Heuristic and Metaheuristic Algorithms When the optimization landscape is rough with many local minima, when you lack derivative information, or when you only need a good (not optimal) solution quickly, heuristic and metaheuristic algorithms become attractive. These methods don't guarantee finding the optimal solution but are often effective in practice. Core idea: Explore the search space intelligently by balancing exploration (trying new regions) and exploitation (refining promising areas). <extrainfo> Population-Based Methods Evolutionary algorithms maintain a population of candidate solutions that "evolve" over generations through: Selection: Better solutions survive with higher probability Crossover: Combining pieces of good solutions Mutation: Randomly modifying solutions Differential evolution is a variant that evolves solutions by adding weighted differences between random population members to create mutations. Particle swarm optimization models the search process as particles moving through space, influenced by their personal best position and the global best position found so far. Local Search with Memory Simulated annealing probabilistically accepts worse solutions with decreasing probability as iterations progress. Early on, it escapes local minima by accepting bad moves; later, it exploits the region like local search. Tabu search maintains a "tabu list" of recently visited solutions, forbidding moves that return to them. This prevents cycling and encourages the search to explore new regions. Specialized Heuristics The Nelder–Mead simplex heuristic optimizes without using derivatives by maintaining a simplex (set of $n+1$ points in $n$-dimensional space) and iteratively: Reflecting the worst point through the centroid of others Expanding or contracting the simplex based on whether that improves the solution This reflects intuition: shrink the search region where it seems promising, expand where it's poor. </extrainfo> Choosing an Algorithm: Key Decision Factors To select the right method: Problem structure: Exploit it. Linear problems → Simplex. Convex problems → Interior-point or gradient methods. Discrete problems → Combinatorial algorithms. Derivative availability: Second derivatives cheap to compute? → Newton's method or SQP Only gradients? → Conjugate gradient or quasi-Newton No derivatives? → Derivative-free or heuristic methods Speed vs. certainty: Must find proven optimal? → Exact algorithm "Good enough quickly" acceptable? → Heuristic Middle ground? → Iterative methods Problem size and structure: Large sparse problems → Conjugate gradient, L-BFGS Structured constraints → Frank–Wolfe, coordinate descent Tiny problems → Newton's method (fast convergence wins) Rough landscapes with many local minima → Simulated annealing, evolutionary algorithms The most practical optimization workflows often combine methods: use a global heuristic to find a good initial region, then refine with a fast local method like L-BFGS.