A Multigrid approach to SDP relaxations of sparse polynomial optimization problems

Add to your list(s) Download to your calendar using vCal

• Panos Parpas, Imperial Colledge, London
• Thursday 08 December 2016, 12:00-13:00
• University House, room 108.

If you have a question about this talk, please contact Sergey Sergeev.

We propose a multigrid approach for the global optimization of a class of polynomial optimization problems with sparse support. The problems we consider arise from the discretization of infinite dimensional optimization problems, such as PDE optimization problems, boundary value problems and some global optimization applications. In many of these applications, the level of discretization can be used to obtain a hierarchy of optimization models that captures the underlying infinite dimensional problem at different degrees of fidelity. This approach, inspired by multigrid methods, has been successfully used for decades to solve large systems of linear equations. However, it has not been adapted to SDP relaxations of polynomial optimization problems. The main difficulty is that the geometric information between grids is lost when the original problem is approximated via an SDP relaxation. Despite the loss of geometric information, we show how a multigrid approach can be applied by developing projection operators to relate the primal and dual variables of the SDP relaxation between lower and higher levels in the hierarchy of discretizations. We develop sufficient conditions for the operators to be useful in applications. Our conditions are easy to verify in practice, and we discuss how they can be used to reduce the complexity of infeasible interior point methods. Our preliminary results highlight two promising advantages of following a multigrid approach in contrast with a pure interior point method: the percentage of problems that can be solved to a high accuracy is much higher, and the time necessary to find a solution can be reduced significantly, especially for large scale problems.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Optimisation and Numerical Analysis Seminars
• School of Mathematics events
• University House, room 108

Note that ex-directory lists are not shown.