Optimization Algorithms: Finding the Best Solution in a Sea of Possibilities

The Optimization Problem

Every optimization problem consists of three components: decision variables (the values we can control), an objective function (the quantity we want to minimize or maximize), and constraints (rules the solution must satisfy). Finding the lowest point in a landscape is an unconstrained optimization problem. Finding the lowest point within a fenced area is a constrained one. The structure of the objective function and constraints determines which algorithms are applicable and how difficult the problem is to solve.

Convex problems have objective functions and feasible regions shaped so that any local minimum is also the global minimum. These are the "easy" optimization problems, solvable efficiently and reliably. Non-convex problems can have multiple local minima, saddle points, and irregular landscapes, making global optimization much harder. Most real-world problems are non-convex, which is why the field of optimization has developed such a diverse toolkit.

Gradient-Based Methods

Gradient Descent

Gradient descent is the workhorse of continuous optimization. It iteratively moves in the direction of steepest descent (the negative gradient) to find a minimum. Starting from an initial point, each step updates the position by subtracting a fraction of the gradient: x_new = x_old minus learning_rate times gradient. The learning rate controls step size: too large and the algorithm overshoots; too small and convergence is painfully slow.

Gradient descent is the foundation of modern machine learning. Training a neural network means minimizing a loss function over millions or billions of parameters, and gradient descent (via backpropagation) is how it is done. For convex functions, gradient descent converges to the global minimum. For non-convex functions, it converges to a local minimum, which may or may not be good enough.

Stochastic Gradient Descent (SGD)

Computing the exact gradient over a large dataset is expensive. SGD approximates the gradient using a random subset (mini-batch) of the data at each step. This introduces noise but makes each step much faster, and the noise can actually help escape shallow local minima. SGD with momentum, which accumulates gradient history to smooth the trajectory, and Adam, which adapts the learning rate for each parameter individually, are the most widely used optimizers in deep learning.

Newton and Quasi-Newton Methods

Newton method uses second-order derivative information (the Hessian matrix) to take more informed steps, converging much faster than gradient descent near a minimum. However, computing and inverting the Hessian is expensive for high-dimensional problems. Quasi-Newton methods like L-BFGS approximate the Hessian from gradient history, achieving much of Newton method's convergence speed without the full computational cost. These methods are popular for medium-scale optimization problems in scientific computing and traditional machine learning.

Linear Programming

Linear programming (LP) optimizes a linear objective function subject to linear constraints. Despite the restriction to linearity, an enormous range of real-world problems can be formulated as LPs: transportation routing, production planning, resource allocation, diet optimization, and network flow problems.

The simplex method, developed by George Dantzig in 1947, navigates the vertices of the feasible region's polytope, moving from vertex to adjacent vertex in the direction that improves the objective. Despite a theoretical worst-case exponential time, the simplex method is extremely fast in practice, typically solving problems in time proportional to the number of constraints. Interior point methods traverse the interior of the feasible region rather than its surface, offering polynomial worst-case time and better performance on very large problems. Modern LP solvers routinely handle problems with millions of variables and constraints.

Combinatorial Optimization

When decision variables are discrete (integers, binary choices, orderings), the problem is combinatorial. These problems often arise in scheduling, routing, assignment, and design. Many are NP-hard, meaning no known polynomial-time algorithm can solve them exactly.

Branch and bound systematically explores the solution space by dividing it into branches and computing bounds on the best possible solution in each branch. Branches whose bounds are worse than the best known solution are pruned, avoiding unnecessary exploration. This is the foundation of integer programming solvers.

Simulated annealing borrows from metallurgy, where slowly cooling a metal allows atoms to settle into a low-energy crystal structure. The algorithm starts with a random solution and iteratively makes small random changes. Better solutions are always accepted; worse solutions are accepted with a probability that decreases over time (as the "temperature" cools). This probabilistic acceptance of worse solutions allows the algorithm to escape local optima early in the search, while converging toward a good solution as the temperature drops.

Multi-Objective Optimization

Many real problems involve multiple competing objectives. Designing an aircraft engine requires minimizing fuel consumption, maximizing thrust, minimizing weight, and minimizing emissions simultaneously. Improving one objective often worsens another. Pareto optimization identifies the set of solutions where no objective can be improved without worsening another. This set, called the Pareto front, gives decision-makers a clear picture of the trade-offs.

Evolutionary algorithms like NSGA-II (Non-dominated Sorting Genetic Algorithm II) are well-suited for multi-objective optimization because they maintain a population of diverse solutions that can approximate the entire Pareto front in a single run, rather than requiring separate runs with different objective weightings.

Constrained Optimization

Lagrange multipliers convert constrained optimization problems into unconstrained ones by incorporating constraints into the objective function with penalty terms. The KKT (Karush-Kuhn-Tucker) conditions generalize this to inequality constraints and provide necessary conditions for optimality. Penalty methods add a large cost for constraint violations, turning a constrained problem into an unconstrained one that standard methods can solve. Augmented Lagrangian methods combine Lagrange multipliers with penalty terms for robust convergence.