Chapter 7 Approximation via Relaxation

approximate nonconvex problems with convex relaxations

Relaxations are superior to general approximations because they provide bounds on true optima. (Taylor 2015)

Relaxation techniques complement or supplement branch and bound algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.

Why then is an infeasible relaxed solution better than a locally optimal but feasible solution? The answer is heavily context dependent. (Taylor 2015)

They are reliable because they are consistent: whereas locally optimal solutions of nonconvex formulations may depend on an algorithm’s starting point, convex relaxations only have global optima. (Taylor 2015)

References

Taylor, Joshua Adam. 2015. Convex Optimization of Power Systems. Cambridge University Press.