April 10, 2014 Andreas Lundell PhD theses

My thesis gives a broad introduction to nonconvex mathematical programming and the use of convex underestimators. Complexity theory provides valuable perspectives on the hardness of optimization. I review basic concepts from complexity theory in one chapter, especially ideas pertaining to optimization and approximation. Many problem formulations appearing in application fields are partly nonconvex or unstructured and accordingly hard to optimize. If a global optimum or verified bounds on the optimum are desirable, one may opt for the global optimization approach; to strive for the best solution although success cannot be guaranteed beforehand.

To solve unstructured problems one will normally utilize branch-and-bound methods. I outline the steps of a generic branch-and-bound algorithm in nonlinear programming. The lower bounding step, where a problem is approximated with a more tractable problem, is currently the most prominent application for convex underestimators. My own contributions to the field are included in the form of five peer-reviewed articles. My research has focused on extending αBB convexification methods to include nondiagonal perturbations. The term nondiagonal comes from the inclusion of nondiagonal elements in the Hessian matrix of the perturbation. These constant elements correspond to bilinear terms. A piecewise linear term is added to improve the tightness of the underestimation, it does not affect the convexity.

The thesis can be downloaded here.