by
ogrisel
This book is about convex optimization, a special class of mathematical optimization
problems, which includes least-squares and linear programming problems. It
is well known that least-squares and linear programming problems have a fairly
complete theory, arise in a variety of applications, and can be solved numerically
very efficiently. The basic point of this book is that the same can be said for the
larger class of convex optimization problems.
While the mathematics of convex optimization has been studied for about a
century, several related recent developments have stimulated new interest in the
topic. The first is the recognition that interior-point methods, developed in the
1980s to solve linear programming problems, can be used to solve convex optimization
problems as well. These new methods allow us to solve certain new classes
of convex optimization problems, such as semidefinite programs and second-order
cone programs, almost as easily as linear programs.
The second development is the discovery that convex optimization problems
(beyond least-squares and linear programs) are more prevalent in practice than
was previously thought. Since 1990 many applications have been discovered in
areas such as automatic control systems, estimation and signal processing, communications
and networks, electronic circuit design, data analysis and modeling,
statistics, and finance. Convex optimization has also found wide application in combinatorial
optimization and global optimization, where it is used to fond bounds on
the optimal value, as well as approximate solutions. We believe that many other
applications of convex optimization are still waiting to be discovered.
There are great advantages to recognizing or formulating a problem as a convex
optimization problem. The most basic advantage is that the problem can then be
solved, very reliably and efficiently, using interior-point methods or other special
methods for convex optimization. These solution methods are reliable enough to be
embedded in a computer-aided design or analysis tool, or even a real-time reactive
or automatic control system. There are also theoretical or conceptual advantages
of formulating a problem as a convex optimization problem. The associated dual
problem, for example, often has an interesting interpretation in terms of the original
problem, and sometimes leads to an efficient or distributed method for solving it.
We think that convex optimization is an important enough topic that everyone
who uses computational mathematics should know at least a little bit about it.
In our opinion, convex optimization is a natural next topic after advanced linear
algebra (topics like least-squares, singular values), and linear programming.
interior point
quadratic programming
linear programming
optimization
convex
dual problem
]]>
