Convex Relaxation Techniques for Nonlinear Optimization

Optimization is everywhere. In science and engineering, optimization is widely used for various applications, and many of the problems that we would like to solve are nonlinear. In general, we do not have ecient methods for solving nonlinear problems, so we have to rely on local optimization methods that provide a candidate solution to our problem with no guarantee of optimality and no bound on the possible suboptimality.

For some hard problems, we can use convex relaxation techniques to approximate the original (hard) problem in a certain way by one that we can solve eciently. This approximation, which is a convex optimization problem, gives us a bound on the optimal value of the original problem. This bound can be used to gauge the suboptimality of candidate solutions.

Bounds on the optimal value also play an important role in branch-and-bound algorithms for hard combinatorial problems. In some cases, the convex relaxation gives us a solution to the original problem. In this thesis, we are particularly interested in the so-called Shor semidenite relaxation where the convex optimization problem is a semidenite program, i.e., a linear program involving a matrix variable that is constrained to be positive semidenite.

This relaxation has proven to be a good approximation for many interesting problems, including the so-called optimal power ow problem, where the goal is to generate and distribute power in a power network at a minimum cost. The goal of the thesis is to contribute to the understanding of convex relaxation and add to the existing toolbox of techniques.

We present a numerica study that demonstrates that the semidenite relaxation of the optimal power ow problem can be solved reliably for large power networks in a few minutes. We present a new technique for strengthening the semidenite relaxation for an extended trust region subproblem which as an extension of the classical trust region subproblem.

We present a framework for guaranteeing that the semide-nite relaxation of a specic problem class is exact, which means that the problem can be solved eciently by solving the convex relaxation.