Abstracts
Prof Christoph Helmberg (Chemnitz University of Technology, Germany)
Lecture: An Introduction to Semidefinite Programming and its ApplicationsAbstract: The feasible set of a linear program (LP) arises as the intersection of an affine subspace with the nonnegative orthant, i.e., the convex cone of nonnegative vectors. Semidefinite programming (SDP) refers to optimising a linear cost function over the intersection of an affine subspace with the convex cone of positive semidefinite matrices. Due to the nonpolyhedral structure of this cone the duality results are more involved, but the rich spectrum of SDP applications ranging from graph partitioning and robust control over statistical design to global optimisation makes up for this easily. After giving some geometric intuition on the structure of the feasible set compared to LP, we will present some of the more direct applications, highlight some duality and complexity aspects and sketch solution methods.
Prof Christoph Helmberg (Chemnitz University of Technology, Germany)
Talk title: Large Scale Semidefinite Programming in ConicBundleAbstract: The callable library ConicBundle implements a general bundle method for convex optimisation with special support for max functions over the semidefinite cone or the second order cone. Bundle methods find the next candidate point by minimising a cutting plane model together with a proximal term that keeps the point close to a current centre of stability. Building on joint work with Overton and Rendl, we explain and discuss a coordinated choice of cutting model and proximal term for the semidefinite case that is designed to mimic the second order method of Overton for minimising the maximum eigenvalue of an affine matrix function. We also present some numerical evidence that this significantly improves convergence properties and allows to achieve higher accuracy.
Prof Stefania Bellavia (University of Florence, Italy)
Talk title: A New Interior Point Approach for Low-rank Semidefinite Programming.Abstract: In this talk we are concerned with the solution of large semidefinite programming problems in which the primal variable X is expected to be low-rank at optimality. Such situations are common in relaxations of combinatorial optimization problems for example in maximum cut problems as well as in matrix completion problems.
Semidefinite programs can be solved efficiently using interior-point algorithms. However, such algorithms typically converge to a maximum-rank solution. Here we propose a new interior point approach that gradually drives the primal iterate to have a low rank structure at optimality. The method uses alternating directions to improve the efficiency of the linear algebra. Preliminary numerical results are shown.
Joint work with Jacek Gondzio and Margherita Porcelli
Prof Emre Alper Yildirim (Koc University, Turkey)
Talk title: On Doubly Nonnegative Relaxations of Standard Quadratic ProgramsAbstract: A standard quadratic program is an optimization problem in which a (nonconvex) quadratic form is minimized over the unit simplex. We focus on doubly nonnegative relaxations obtained from copositive programming formulations of standard quadratic programs. We shed light on instances of standard quadratic programs for which the doubly nonnegative relaxation is in fact exact.
This is joint work with Yakup Gorkem Gokmen
Prof Michal Kočvara (University of Birmingham, UK)
Talk title: Solving Large Scale Semidefinite Problems by DecompositionAbstract: Standard semidefinite optimization solvers exercise high computational complexity when applied to problems with many variables and a large semidefinite constraint. To avoid this unfavourable situation, we use results from the graph theory that allow us to equivalently replace the original large-scale matrix constraint by several smaller constraints associated with the subdomains. This leads to a significant improvement in efficiency. We will further strengthen the standard approach for a special class of arrow matrices. We will demonstrate that these reformulations are particularly suitable for problems of topology optimization with vibration or global buckling constraints.
Dr Alemseged Weldeyesus (University of Edinburgh, UK)
Talk title: Optimization of Truss Structures by Semidefinite ProgrammingAbstract: We are concerned with optimization of truss structures with global stability constraints modelled by semidefinite programming. These optimization problems are in general nonlinear and nonconvex hence challenging to solution methods particularly when the size of the problem increases. In this talk, we focus on a linear relaxation to these formulations for which we describe an efficient primal-dual interior point method and its implementation. The method exploits the sparse structure and low-rank property of the data matrices to avoid the bottleneck extensive computational effort of determining the linear systems originating in the algorithm. Moreover, we extend the member adding procedure that has been previously used in problems formulated as linear programming to solve a sequence of smaller subproblems that ultimately approximate the original large-scale problem. Finally, the method employs a warm-start strategy to use an initial point to solve some of the subsequent problem instances and improve the convergence. We present several numerical experiments to show the capability of the interior point method to solve the relaxed formulations of the truss structure optimization.
Joint work with Jacek Gondzio