WF-06: Conic Optimization and related topics
Stream: Conic Optimization and related topics
Room: Moreau
Chair(s): Paula Amaral

Min-max regret for Standard QPs and nonconvex fractional QPs
Immanuel Bomze, Paula Amaral, Patrick Groetzner
Under finitely many uncertain scenarios, min-max regret for (possibly nonconvex) Standard QPs can be reduced to a min-max QCQP. We will follow this route and embed it into the more general framework for nonconvex fractional quadratic optimization with linear denominators, under linear (and/or also quadratic constraints) where copositivity bounds play an essential role to reduce the optimality gap in global optimization procedures.

On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations
E. Alper Yildirim, Yakup Görkem Gökmen
We consider the doubly nonnegative (DN) relaxation of standard quadratic programs. We present a full algebraic characterisation of the set of instances of standard quadratic programs that admit an exact DN relaxation. This characterisation yields an algorithmic recipe for constructing such an instance. In addition, we explicitly identify three families of instances for which the DN relaxation is exact. We also provide an algebraic characterisation of the set of instances for which the DN relaxation has a positive gap and show how to construct such an instance using this characterisation.

Copositive based bounds on the clique number
Paula Amaral, Immanuel Bomze
For a given a graph G, the maximum clique problem consists in determining the size of the maximum complete subgraph, γ(G) in G. It is well known that determining γ(G) is an NP-hard problem. This problem can be formulated as a copositive optimization problem. Copositivity detection is difficult; in particular, to decide if it is not copositive is NP-complete. In this talk we present an algorithm that is based on the decomposition of a matrix in the doubly non-negative cone. The algorithm gives upper and lower bounds on the clique number. We report computational results for a set of graphs.

Optimal parameter tuning for path-following methods in conic optimization
Anastasiia Ivanova
Classical schemes for short-step path-following methods in conic optimization alternate a Newton step towards a target point on the central path and an increase of the parameter of the target point. The quantitative analysis of the performance of these methods relies on a compariso of the Newton decrement before and after the Newton step. We propose a novel scheme which replaces the Newton decrement with respect to a target point by an analog of the decrement with respect to the central path as a whole. Here the direction parallel to the central path is treated differently from the directions