Projects per year
Abstract
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 branchandbound 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 socalled 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 socalled 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 semidenite relaxation of a specic problem class is exact, which means that the problem can be solved eciently by solving the convex relaxation.
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 branchandbound 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 socalled 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 socalled 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 semidenite relaxation of a specic problem class is exact, which means that the problem can be solved eciently by solving the convex relaxation.
Original language  English 

Publisher  Technical University of Denmark 

Number of pages  201 
Publication status  Published  2021 
Fingerprint
Dive into the research topics of 'Convex Relaxation Techniques for Nonlinear Optimization'. Together they form a unique fingerprint.Projects
 1 Finished

Convex Relaxation Techniques for Nonlinear Optimization
Eltved, A., Andersen, M. S., Chatzivasileiadis, S., Stolpe, M., Anjos, M. F. & Bienstock, D.
Technical University of Denmark
01/01/2018 → 14/04/2021
Project: PhD