Convex Optimization

Reference in Convex optimization

• Stephen Boyd and Lieven Vandenberghe, Convex optimization (book in pdf)
• EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
• 6.253: Convex Analysis and Optimization, an MIT OCW course homepage
• Brian Borchers, An overview of software for convex optimization

Examples

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

• Least squares
• Linear programming
• Convex quadratic minimization with linear constraints
• Quadratically constrained Convex-quadratic minimization with convex quadratic constraints
• Conic optimization
• Geometric programming
• Second order cone programming
• Semidefinite programming
• Entropy maximization with appropriate constraints

Methods

Convex minimization problems can be solved by the following contemporary methods:^[4]

• "Bundle methods" (Wolfe, Lemaréchal, Kiwiel), and
• Subgradient projection methods (Polyak),
• Interior-point methods (Nemirovskii and Nesterov).

Other methods of interest:

• Cutting-plane methods
• Ellipsoid method
• Subgradient method
• Dual subgradients and the drift-plus-penalty method

Subgradient methods can be implemented simply and so are widely used.^[5] Dual subgradient methods are subgradient methods applied to a dual problem. The drift-plus-penalty method is similar to the dual subgradient method, but takes a time average of the primal variables.