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


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


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


We consider the optimization problem minx ∈ 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.


  signature loans . If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.