# Accepted papers

**Invited plenary speakers: ** *Dan Bienstock* (Columbia University, USA)

Numerically hard polynomial optimization problems*Marco Sciandrone *(Università di Firenze, Italia)

Optimization algorithms for zero-norm minimization

STANDARD PAPERS (Published in the AIRO-Springer volume “Graphs and Combinatorial Optimization: from Theory to Applications. CTW2020 Proceedings”)

EXTENDED ABSTRACTS

Dan Bienstock (Columbia University, USA)*Numerically hard polynomial optimization problems*

It is a simple matter to generate very small instances of QCQPs that prove difficult for numerical solvers. More precisely we are referring to cases where solvers output a solution that is numerically feasible, though slightly infeasible, but is highly superoptimal. This phenomenon can be described with a clichéd phrase, *a little infeasibility buys you a lot of optimality*. The key observation is that this behavior is mild in linear systems, but nontrivial in nonconvex nonlinear settings. We will present several such examples.

A principal challenge that is manifested by such examples is that many of our convex relaxations arise as hierarchies, with higher members of a hierarchy being proved as more accurate, and it may (will) be the case in these difficult instances that a slightly infeasible and superoptimal solution produced by the solver will be cut-off by a higher-order relaxation (produced, even, by the same solver). In other words, a superoptimal upper bound for a minimization problem will be cut-off, by a large amount, by a convex relaxation.

Rather than being an artificial construct, this phenomenon is due to the expressivity of quadratic algebraic inequalities. We will discuss some classical algebraic background addressing these issues, and also present some recent negative results from ongoing work with Alberto del Pia and Robert Hildebrand.

For example, it is strongly NP-hard to test whether a feasible system of quadratic inequalities with integer coefficients has a rational solution. It is also strongly NP-hard to test whether a system of quadratic inequalities with integer coefficients, that has rational solutions, also has a rational solution expressible using a polynomial number of bits.

Marco Sciandrone (Università di Firenze, Italy)*Optimization algorithms for zero-norm minimization*

In this talk we consider sparse optimization problems involving

the so-called zero-norm function that counts the number of non-zero components in a vector. The considered optimization problems are central in important fields like, for instance, machine learning and computer vision. We focus on problems where the zero-norm is a part of objective function or constraints. We present continuous optimization algorithms based on smoothing techniques when the objective function

is the zero-norm, and on penalty decomposition approaches for problems where the zero-norm is a part of constraints. Concerning this latter class of problems, we also describe an algorithm based on mixed integer nonlinear programming. We analyze theoretical issues and we discuss computational results.