Current projects

Semidefinte-Copositive and Semi-Infinite Programming: Interactions

No Image Loaded

Funding: Scholarship of Higher Education Commission of Pakistan
Running Period: 2010-2014    
Staff: George Still
Ph.D. student: Faizan Ahmed  

ABSTRACT

A conic program (CON) is a convex optimization problem with cone constraints. It comprises semi-definite- (SDP) as well as copositive-programming (COP). SDP relaxations has been used to solve hard integer programs (IP) approximately. Surprisingly enough a new similar copositive programming formulation has been shown to represent the IP exactly [Burer]. This opens a new way for analyzing and solving hard integer programs by convex continuous optimization.

On the other hand conic programs, in particular SDP and COP, can be seen as special instances of linear semi-infinite problems (SIP). The first (SDP) being tractable the second (COP) not. In this proposal we intend to study conic programming from the viewpoint of SIP. The aim is to analyze the relations between CON and SIP from a structural and algorithmic viewpoint. We wish to examine which structure makes a CON or SIP tractable and to analyze algorithms which can be implemented efficiently. In particular the tractability and efficient solvability of SDP and the intractability of COP will be considered from the angle of semi-infinite optimization.