## Invited Session Fri.1.H 2038

#### Friday, 10:30 - 12:00 h, Room: H 2038

**Cluster 4: Conic programming** [...]

### Recent developments of theory and applications in conic optimization II

**Chair: Hayato Waki and Masakazu Muramatsu**

**Friday, 10:30 - 10:55 h, Room: H 2038, Talk 1**

**Mirai Tanaka**

Numerical computation of a facial reduction algorithm and an inexact primal-dual path-following method for doubly nonnegative optimization problems

**Coauthors: Kazuhide Nakata, Hayato Waki**

**Abstract:**

In this talk, we introduce an effective approach to solve

doubly nonnegative relaxation (DNR) problems for mixed binary nonconvex quadratic optimization problems.

In our approach, we convert a given DNR problem into another one that is smaller than the original one exploiting degeneracy.

We can expect numerical stability of interior-point methods for the DNR problem to be improved

because this conversion can be regarded as an incomplete facial reduction algorithm.

In a previous approach, we can find degeneracy only relevant to semidefiniteness analytically.

In our approach, to also find degeneracy relevant to nonnegativity,

we compute a dense optimal solution of a linear optimization problem with an interior-point method.

Moreover, we propose an inexact primal-dual path-following method for the reduced DNR problems.

In our algorithm, to compute search directions,

we solve large linear systems via the preconditioned symmetric quasi-minimal residual (PSQMR) method.

To accelerate the convergence of the PSQMR method,

we develop some preconditioners.

Numerical results show that we can solve some instances of DNR problems quickly and accurately.

**Friday, 11:00 - 11:25 h, Room: H 2038, Talk 2**

**Matsukawa Yasuaki**

A primal barrier function phase I algorithm for nonsymmetric conic optimization problems

**Coauthor: Yoshise Akiko**

**Abstract:**

We call the set of positive semidefinite matrices whose elements are nonnegative the doubly nonnegative (DNN) cone. The DNN cone can be represented as a projection of a symmetric cone given by the direct sum of the semidefinite cone and the nonnegative orthant. Using the symmetric cone representation, the authors demonstrated the efficiency of the DNN relaxation and showed that it gives significantly tight bounds for a class of quadratic assignment problems while the computational time is too long. The result suggests a primal barrier function approach for the DNN optimization problem. However, most of existing studies on the approach have assumed the availability of a feasible interior point which is not practical. Motivated by these observations, we propose a primal barrier function Phase I algorithm for solving conic optimization problem over the closed convex cone K such that (a) K is not necessarily symmetric, (b) a self-concordant function is defined over the interior of K, and (c) its dual cone is not explicit or is intractable, all of which are observed when K is the DNN cone. We analyze the algorithm and provide a sufficient condition for finite termination.

**Friday, 11:30 - 11:55 h, Room: H 2038, Talk 3**

**Victor Liev Magron**

Certification of inequalities involving transcendental functions using semi-definite programming.

**Coauthors: Xavier Allamigeon, Stéphane Gaubert, Benjamin Werner**

**Abstract:**

We consider the optimization problem *min*_{x ∈ K} f(x), where *f*

is a multivariate transcendental function and *K* is a compact

semi-algebraic set. Recent efforts have been made to produce

positivity certificates for these problems, and to verify

these certificates with proof assistants such as COQ. Our motivation

is to automatically verify inequalities from the proof of Kepler

conjecture by Thomas Hales.

We will present a certification framework, combining semi-definite

programming with semi-algebraic approximations of transcendental

functions. Our method consists in an iterative decomposition of the

set *K* into subsets in which the inequalities to be certified are

expected to be either tight or coarse. Coarse inequalities are checked

by global optimization methods (solving a hierarchy of relaxed

problems using SOS solvers such as SparsePOP). Then, the feasible

points generated by these methods are used to refine iteratively the

semi-algebraic approximations of transcendental functions until the

needed accuracy is reached. Tight inequalities are certified locally

by Taylor-type models. Experimental results will illustrate numerical and scalability issues.