Algebraic and Geometric aspects of Optimization

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

The following three topics are discussed in the project: computable self-concordant barrier functions, Jordan-algebraic aspects of optimization, and multi-dimensional trigonometric programming. The overall goal of the project is to develop new computational and theoretical tools to address complicated nonconvex optimization problems including NP-hard problems of combinatorial optimization. In particular, computable self-concordant barriers for the cone of so-called copositive matrices and more general polynomial cones are discussed. Development of interior-point algorithms based on such barriers would open a totally new venue for the numerical analysis of various complex practical optimization problems, where the (approximate) knowledge of a global optimum is desirable. Concrete approaches are proposed to the use of Jordan-algebraic techniques for constructing treatable convex relaxations for a very general class of nonconvex optimization problems and to robust optimization. Proposed ideas for the transformation of polynomial programming problems into trigonometric counterparts may lead to significantly improved numerical stability of existing algorithms based on semi-definite programming approximations. Optimization problems play a very important role in a wide spectrum of applications. But existing algorithms and software allow one to reliably analyze only a very limited class of structured convex optimization problems, if the goal is to find a global optimum. The present project aims to contribute to the problem of finding global optimal solutions (or their reasonable estimates) for a much broader and more difficult class of optimization problems which includes (but is not limited to) various types of NP-hard problems of combinatorial optimization.