Objectives & Research

The project develops conic-optimization techniques to solve a particularly hard class of decision problems: nonconvex quadratic optimization with uncertain data. Four research areas are pursued in parallel.

Copositive Benders approach

This aspect of the project applies a copositive Benders approach to two-stage stochastic QCQPs, which naturally decompose into a first-stage problem and a multitude of second-stage problems that can be modeled by the optimal value function in the first-stage variable. Such a structure lets us develop a reformulation based on optimal value functions that can be tackled by a copositive Benders strategy. It will be decisive to devise structure-dependent decomposition strategies in order to enter the domain of tractable and efficient procedures. The validity of these strategies requires deep mathematical results from conic geometry and linear algebra which still need to be developed.

Discrete robustness: efficient algorithms for lower and upper bounds

Here we address robust nonconvex QCQPs under discrete uncertainty, where one seeks tight lower and upper bounds on the worst-case value with minimal computational effort. Lower bounds are obtained via the doubly-non-negative (DNN) relaxation of the copositive cone, which typically yields much tighter bounds than LP-based approaches. Upper bounds are produced by applying an inexpensive local solver to each scenario and iterating — either in a full-table fashion or via a dynamic update scheme — to recover good feasible solutions whose worst-case value certifies an upper bound; both schemes can be rerun from multiple starting points to further tighten the bound. A central task is to isolate the theoretical properties that guide which approach to use, and to exploit structural properties — for example decomposition and matrix-completion results — so that the DNN relaxation remains tractable on larger instances.

Convergence theory and exactness guarantees

We study the convergence of the iterative methods used to solve robust and stochastic nonconvex QCQPs. On the one hand, first-order methods are analysed with the aim of finite or ergodic convergence of upper bounds; adapting Frank/Wolfe variants and subgradient schemes for this setting requires, in particular, a new Jensen-type inequality for non-smooth Shor-convex functions. On the other hand, lifted bundle methods are developed in matrix space, where restoring feasibility is non-trivial and the limiting matrix is typically not of rank one. Extracting a feasible solution in the original variables then relies either on an approximation argument or on separating cuts against the completely-positive cone, which can be re-injected to dampen the step size.

Scaling up: efficient semidefinite programming

This aspect of the project develops customised solvers for the large semidefinite programs (SDPs) that arise from doubly-non-negative relaxations of QCQPs, since off-the-shelf SDP solvers are limited to small instances. Building on augmented-Lagrangian and operator-splitting methods such as ADMM and Peaceman-Rachford splitting, the work tackles the projection onto the intersection of the positive-semidefinite cone, the non-negative orthant, and additional affine constraints (including cutting planes) via Dykstra-type algorithms, with parallelisation guided by graph-colouring heuristics. Facial reduction and the exploitation of symmetries are further investigated to reach problem sizes of practical interest.