Optimization

Optimization finds the BEST solution according to a defined criterion. Every problem has: an objective function f(x) to minimize or maximize, decision variables x, and constraints g(x)≤0, h(x)=0. When f is convex, any local minimum equals the global minimum — computationally tractable. When non-convex (like neural network losses), algorithms can get trapped. The field splits into: linear programming (simplex method), convex optimization (interior point), nonlinear optimization (gradient descent, Newton, BFGS), and combinatorial optimization (branch-and-bound for discrete variables).

Optimization is the mathematical discipline of finding the BEST solution according to a well-defined criterion. Every optimization problem has three components: an objective function to minimize or maximize, decision variables that you control, and constraints that restrict the acceptable solutions. When the objective function is convex, any local minimum is guaranteed to be the global minimum — this property makes convex optimization computationally tractable and reliable. When the function is non-convex, local minima can trap optimization algorithms, and finding the global optimum becomes much harder.

Gradient descent is the most fundamental optimization algorithm. At each step, compute the gradient of the objective function at the current point, then move in the OPPOSITE direction (downhill), scaled by a small step size called the learning rate alpha. If alpha is too large, the algorithm may overshoot and diverge. If too small, convergence is painfully slow. Stochastic Gradient Descent (SGD) uses random minibatches of data to estimate the gradient, making it efficient for large-scale machine learning. Momentum adds inertia to smooth the trajectory. Adam (Adaptive Moment Estimation) combines momentum with adaptive learning rates per parameter and is the default optimizer for most neural network training.

When decision variables are subject to constraints, additional techniques are needed. Linear Programming (LP) optimizes a linear objective subject to linear constraints — the feasible region is a convex polyhedron, and the optimum always occurs at a vertex. The simplex algorithm efficiently navigates these vertices. Lagrange multipliers handle equality constraints by introducing a new variable lambda for each constraint. The optimal point occurs where the gradient of the objective is parallel to the gradient of the constraint. The Karush-Kuhn-Tucker (KKT) conditions generalize Lagrange multipliers to inequality constraints and form the theoretical foundation of constrained optimization.

Watch gradient descent descend into a valley! The heatmap shows the loss function f(x,y)=x²+0.5y²+0.3sin(3x)cos(2y). Each blue dot is a step. Green=start, Red=current. Try different learning rates: too large diverges, too small is slow, just right converges quickly.