Projects / Programmes
New methods development and application of existing mathematical programming methods in combinatorial optimization and real algebra
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P160 |
Natural sciences and mathematics |
Statistics, operations research, programming, actuarial mathematics |
semidefinite programming, copositive programming, combinatorial optimization, sum of squares, positivity of polinomials
Researchers (1)
| no. |
Code |
Name and surname |
Research area |
Role |
Period |
No. of publicationsNo. of publications |
| 1. |
22649 |
PhD Janez Povh |
Computer intensive methods and applications |
Head |
2008 - 2010 |
341 |
Organisations (1)
Abstract
The project is divided into two parts.
In the 1st part we will try to find out how to rewrite hard combinatorial problems as linear programs over the cone of copositive or completely positive matrices and how to develop new and more efficient approximations of hard optimization problems. We will focus on the properties of copositive matrices and on the hierarchies of semidefinite approximations of polynomial optimization problems.
In the 2nd part we will investigate how to apply semidefinite programming in order to write a polynomial in non-commutative variables as a sum of hermitian squares. Theoretical study will be followed by a matlab software package, which will find such sum of squares if there exist any.
Significance for science
The goals that we reached with this project are bridge between researchers from real algebraic geometry and mathematical programming. They are also an important application of mathematical programming in the real algebraic geometry.
The special structure of the resulting problems is a motivation for mathematical programming society to develop special optimization methods for such problems.
The projects aims, i.e. making tighter connections between mathematical programming society and real algebraic society, were completely achieved.
Slovenian group working in this area has grown and now there are 4 mathematicians active in this research, including one PhD student. This is already comparable with other research groups working on these problems.
Realization of the objectives 3 and 4 help significantly the mathematicians which study non-commutative polynomials and optimization above them, because they have a tool to handle the NC polynomials as well to provide fast and accurate answer on the question if given polynomial is SOHS (modulo cyc. equivalence), how to obtain rational SOHS decomposition of a rational NC polynomial, how to extract the minimum of a trace of NC polynomial etc.
Software package NCsostools is becoming a package of choice for NC polynomials and is therefore a non-commutative equivalent of commutative packages SOStools and GloptyPoly.
Main results: several version of Newton chip method, semidefinite formulations for NC polynomial convexity properties, practically and theoretically efficient methods to find rational SOHS factorizations, closing some open problems about particular BMV polynomials, NCsostools,...
Successful realization of objective 1 and 2 is important since this gives rise to a general framework for further copositive and semidefinite relaxations of many NP-hard combinatorial problems.
Main results: reformulations of hard non-convex problems as a copositive linear problems, tractable relaxations of hard problems by semidefinite programming, establishing relations between several copositive representations.
Significance for the country
In Slovenia the project has very positive effect: it strengthens the operations research society. This society is actually very small and many researchers do not follow recent developments in the sub-area of mathematical programming.
During the two-year period of the project a new group of 4 Slovenian researchers has been formed and has achieved very good international recognition. It has established strong international relations with several eminent researchers:
University in Konstanz, Germany:
prof. Marcus Schweighofer, PhD,
- Sabine Burgdorf, PhD candidate
University of Erlangen-Nürnberg, Germany:
- prof. Gabrielle Eichfelder, PhD
University of Groningen, The Nederlands:
- prof. Miriam Duer, PhD
University of California at San Diego:
prof. Bill Helton, PhD
University of Vienna, Austrija:
- prof. Immanuel Bomze, PhD
The group is recognized within the theoretical and applied mathematicians and generates stronger interest for this research topics, resulting also in a new Slovene PhD student working in this area.
Most important scientific results
Annual report
2008,
final report,
complete report on dLib.si
Most important socioeconomically and culturally relevant results
Annual report
2008,
final report,
complete report on dLib.si
