11:30 AM - 11:55 AM
A fresh CP look at mixed-binary QPs: new formulations and relaxations
Triggered by Burer’s seminal characterization from 2009, many copositive
reformulations of mixed-binary QPs have been discussed by now.Most of them can be
used as proper relaxations, if the intractable co(mpletely)positive cones are replaced
by tractable approximations. While the widely used approximation hierarchies have
the disadvantage to use positive-semidefinite (psd) matrices of orders which rapidly
increase with the level of approximation, alternatives focus on the problem of keeping
psd matrix orders small, with the aim to avoid memory problems in the interior
point algorithms. This work continues this approach, proposing new reformulations
and relaxations. Moreover, we provide a thorough comparison of the respective duals
and establish a monotonicity relation among their duality gaps. We also identify sufficient conditions for strong duality/zero duality gap in some of these formulations and
generalize some of our observations to general conic problems.
11:55 AM - 12:20 PM
Min-Max fractional quadratic over linear problems
Fractional programs are in general non-convex programs and exact methods require the existence of good lower bounds. An important feature of completely positive (CP) formulations is that its relaxations give tight lower bounds. In this talk we present completely positive formulations for min-max fractional quadratic over linear problems, with linear and quadratic constraints and study the properties of the doubly positive (DP) relaxations. The fractional min-max problem occurs, among others, in the study of worst-case analysis when different scenarios are under evaluation. Computational experience compare the lower bound obtained by the DP relaxation with the one provided by Baron, and show that for instances that Baron could not solve, if these lower bounds were initially used optimality could be achieved.
12:20 PM - 12:45 PM
Trust your data or not - Standard remains Standard (QP)
In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this model is quite versatile. Applications are numerous, ranging from the famous Markowitz portfolio problem in Finance, Economics (evolutionary game theory) through Machine Learning (background-foreground clustering in image analysis), biological and social network analysis to other life science applications, e.g. in Population Genetics (selection models) and Ecology (replicator dynamics).
If the problem data (i.e., the form) are uncertain, most of the usual uncertainty sets do not add complexity to the robust counterpart. On the other hand, it is well known that most probably within this problem class, a generic StQP instance is not too hard to solve as the worst cases are hidden in relatively thin manifolds of the class. These hard instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally, which question in turn is closely related to copositive optimization.
In this study, we improve on existing worst-case lower bounds for the number of strict local solutions by a new technique to construct instances with a rich solution structure, studying the influence of perturbations of a matrix on its pattern. The results obtained along this line may be of independent interest and also may serve to construct test instances for nonlinear solvers.
To gain insight on typical hard cases and their distribution, we conducted extensive experimental results on potentially hard instance matrices.