5. Convex Optimization

Our aim so far has been to formulate a real-life decision problem as a (mixed-integer) linear optimization problem. The reason was clear: linear functions are simple, so problems formulated with them should also be simple to solve. However, the world of linear problems is sometimes not flexible enough to model well all real-life problems. In fact, numerous optimization problems come naturally in nonlinear form and that this might lead to situations in which determining the optimal solution is difficult.

Luckily, it will turn out that the real separation between simple and difficult problems is not whether they are linear vs. nonlinear, but instead, whether they are convex or not. Convexity is a very desirable property of an optimization problem that makes the optimization problem solvable to optimality in a reasonable time. For that reason, it plays a central role in mathematical optimization.

In this chapter, there is a number of examples with companion AMPL implementation that explore various modeling and implementation aspects of convex optimization:

• Milk pooling and blending

• Ordinary Least Squares (OLS) regression

• Markowitz portfolio optimization problem

• Support Vector Machines for binary classification

• Extra material: Refinery production

• Extra material: Cutting stock

Go to the next chapter about conic optimization.