Anders Eltved: Mathematical optimization is widely used in science and engineering; examples include optimization of mechanical systems, structural design, and power systems operations.
An optimization problem consists of some measure of cost/performance
to be minimized/maximized and some constraints to be upheld. Some optimization
problems can be solved by global optimization methods, but many problems arising
in engineering are too expensive (have too many variables or constraints, or are too
complicated) to be solved using these methods due to the computational complexity
of the algorithms and limitations of the current hardware. For such problems, we
are restricted to local optimization methods that are only guaranteed to find a local
extremum, that is, a set of variables where a small change does not improve the
cost/performance, and the methods provide no way of assessing the quality. An example of a nonlinear optimization problem (that is usually solved by local methods)
is the so-called optimal power flow problem, where the goal is to minimize the cost
of electrical power production while satisfying the demand, the physical laws, and
the limitations of the system (transmission line capacity, generator capacity, etc.).
In this particular application, the difference in cost between a local minimum and a
solution might be millions of dollars.
In this project we consider convex relaxation techniques, where a problem that is
hard to solve is reformulated (relaxed) to a convex optimization problem (for example by expanding the feasible set or using a convex approximation to the objective
function). Convex optimization problems are a special class of problems with the
property that any local minimum is guaranteed to be a solution, and efficient algorithms exist for solving a large class of convex optimization problems. Solving the
relaxation (the convex problem) provides a bound on the solution of the original
problem, yielding a way to assess the quality of a local minimum, and in some cases
a solution to the original problem can be recovered.
Convex relaxation has been applied with great success in many areas, but the computational complexity of the relaxation is sometimes a bottleneck for applying the
technique for large-scale problems. Furthermore, improving the tightness of relaxations (the link between the relaxed problem and the original problem) is of interest,
as this would provide a better bound on the solution of the original problem. We
will study relaxation strategies to tackle some of the challenges that currently limit
the use of convex relaxation, for example using adaptive strategies that explore the
trade-off between computational complexity and tightness of the relaxation, and
apply these to the optimal power flow problem to demonstrate the practical applicability.
PhD project title: Convex Relaxation Techniques for Nonlinear Optimization
Effective start/end date 01/01/2018 → 31/12/2020
Supervisors: Martin S. Andersen from the section for Scientific Computing.