Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Early stages: birth of linear algebra

Early Chinese linear algebra text 

The roots of optimization, as a field concerned with algorithms for solving numerical problems, can perhaps be traced back to the earliest known appearance of a system of linear equations in ancient China. Indeed, the art termed fangcheng (often translated as ‘‘rectangular arrays’’) was used as early as 300 BC to solve puzzles which amounted to linear systems. Records of algorithms identical to Gauss elimination for solving such systems appear in the treatise Nine Chapters of Mathematical Methods, around 100 BC. The picture on the left pictures a 9 times 9 matrix found in the treatise (with a reversed convention for the column's order).

It is believed that many of the early Chinese results in linear algebra found gradually their way to Europe.

Optimization as a theoretical tool

Gauss (c. 1800) built on early results (and his own contributions) in linear algebra to develop amethod for solving least-squares problems, which relied on solving an associated linear system (the famous normal equations). But this early algorithmic result remained an exception in the optimization landscape in 18th century Europe, as most of the development of the field remained at a theoretical level.

The notion of optimization problem was crucial to the development of theoretical mechanics and physics between the 17th and 19th century. Around 1750, Maupertuis introduced and later Euler formalized the principle of least action, according to which the motion of natural systems could be described as an minimization problem involving a certain cost function called ‘‘energy’’. This optimization-based (or, variational) approach is the foundation of classical mechanics. The Italian mathematician Giuseppe Lodovico (Luigi) Lagrangia (1736–1813), also known as Lagrange, was a key player in this development and his name is associated with a central notion in optimization, duality.

While optimization theory played a central role in physics, it is only with the advent of computers that it could start making its mark in practical applications, and venture in fields other than physics.

Advent of linear programming

Dantzig (1914-2005), working in the 40s on Pentagon-related logistical problems, started investigating the numerical solution to linear inequalities. Extending the scope of linear algebra (linear equalities) to inequalities seemed useful, and his efforts led to the famous simplex algorithm for solving such systems. Another important early contributor to the field of linear programming is the Soviet/Russian mathematician Leonid Kantorovich.

In the 60s-70s, a lot of attention was devoted to non-linear optimization problems. Methods to find local minima were found. In the meantime, researchers recognized that these methods could fail to find global minima, or even converge. Hence the notion that, while linear optimization was numerically tractable, non-linear optimization was not in general. This had concrete practical consequences: linear programming solvers could be reliably used for day-to-day operations (for example, for airline crew management); but non-linear solvers needed an expert to baby-sit them.

In the field of mathematics, the 60s saw the development of convex analysis, which would later serve as an important theoretical basis for progress in optimization.

Advent of convex programming

Most of the research in optimization in the United States in the 60s-80s focussed on nonlinear optimization algorithms, and contextual applications. The availability of large computers made that research possible and practical.

In the Soviet Union at that time, the focus was more towards optimization theory, perhaps due to more restricted access to computing resources. Since non-linear problems are hard, Soviet researchers went back to the linear programming model, and asked the following (at that point theoretical) question: what makes linear programs easy? Is it really linearity of the objective and constraint functions, or some other more general structure? Are there classes of problems out there that are non-linear but still easy to solve?

Nesterov and Nemirovski discovered in the late 80s that the key property that makes an optimization problem easy is convexity. Their result is not only theoretical but also algorithmic, as they discovered so-called interior-point methods for solving convex problems. Since their result, convex optimization has emerged as a powerful tool that generalizes linear algebra and linear programming: it has similar characteristics of reliability (it always converges to the global minimum) and tractability (it does so in reasonable time).

Present

In present times there is a very strong interest in optimization in applications, ranging from engineering design, statistics and machine learning, finance, etc.