Optimization is a method for systematically improving system performance or resource allocation to achieve desired outcomes.An alpinist sees three ridges ahead, but he needs not the highest, but the lowest pass. Optimization mathematically seeks the minimum (or maximum) of an objective function — a numerical measure of solution quality. Constraints define the feasible region: you can't walk on air or steeper than 45 degrees. Linear programming deals with straight slopes, where the answer lies at a vertex. For smooth hills, gradient descent is used. If the terrain is cut by ravines and cliffs, evolutionary algorithms come into play — they launch a whole crowd of virtual alpinists, and the most successful routes are crossed and mutated. Thus, a path is found in multidimensional spaces where no map can be drawn. When the step becomes smaller than a millimeter, the search stops — the pass is conquered.
Roots go back to the calculus of variations of the 17th–18th centuries, but the modern era began in the 1940s with the development of linear programming and the simplex method. The advancement of nonlinear optimization in the 1960s brought penalty methods and conjugate gradients. In the 1980s, interior-point algorithms emerged, revolutionizing the solution of large-scale problems. Today, optimization is the foundation of all machine learning technologies.
Most algorithms construct a sequence of points converging to the minimum. Gradient descent moves against the gradient. In machine learning, the gradient of the loss function is computed on a random subset of data (batch), enabling optimization of billions of parameters. Regularization adds penalties for complexity to avoid overfitting. For constrained problems, methods like the reduced gradient method or sequential quadratic programming are used. Global optimization employs Bayesian methods and search with decision trees.
GPS navigators plot routes, airlines schedule flights, and engineers calculate streamlined shapes — all this is the work of optimization algorithms.
The traveling salesman problem — visiting 100 cities by the shortest route — has more possible routes than there are atoms in the universe. Yet smart optimizers find a solution in seconds.
| x | variable | Input sequence — sequence |
| n | variable | Index of output element — index |
| i | variable | Left endpoint of interval — index |
| j | variable | Right endpoint of interval — index |
| k | variable | Summation index — index |
| \sup | operator | Takes the least upper bound of a set — supremum |
| \sum_{k=i}^j | operator | Adds terms from index i to j — finite summation |
| f | variable | objective function value — objective function value |
| g | variable | primary objective function — primary objective function |
| h | variable | penalty function — penalty function |
| λ | variable | penalty weight — penalty weight |
| \theta_k | variable | Parameter vector at iteration k — parameter vector |
| \theta_{k+1} | variable | Updated parameter vector at iteration k+1 — parameter vector |
| \alpha_k | variable | Learning rate (step size) at iteration k — learning rate |
| f(\theta_k) | variable | Objective function evaluated at \theta_k — objective function |
| \nabla_\theta | operator | Computes the vector of partial derivatives with respect to each parameter — gradient operator |
| Ψ | variable | Wave function — wave function |
| t | variable | Time — time second |
| τ | variable | Time step — time step second |
| e^{τW} | operator | Applies the evolution operator for the W part — exponential operator |
| e^{τT} | operator | Applies the evolution operator for the T part — exponential operator |
| g | variable | function whose growth is being bounded |
| n | variable | input size parameter |
| O | operator | asymptotic upper bound up to constant factor — big o notation |
