טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentCabelev Dmitry
SubjectPolynomial Time Cutting Plane Algorithms Associated with
Symmetric Cones
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Arkadi Nemirovski


Abstract

In this Thesis, we develop new polynomial-time methods for black-box-represented Convex Programming problems of the form  where X is a solid (convex set with a nonempty interior) in  and f is a convex continuous function on X. A ``black-box'' representation of such a problem is given by a pair of ``black box'' subroutines (``oracles''); specifically, X is given by a Separation oracle which, given on input a point  reports whether  and if its is not the case, returns a linear form which separates x from  while f is represented by a First Order oracle which, given on input  returns  and . Besides, we assume that we are given in advance reals  such that X is contained in the centered at the origin Euclidean ball of radius R and contains a ball of radius r. A method B for solving problems of this type is called polynomial, if, for every  and every problem  from the outlined family, B generates an -solution to the problem (i.e., a point  such that  in a polynomial in n,  and  number of calls to the Separation and the First Order oracles, with every call accompanied by a polynomial in the same parameters number of arithmetic operations.

The discovery of polynomial time methods for black-box-represented convex problems (1976) had fundamental theoretical consequences: these methods underlie general results on polynomial time solvability of generic convex optimization programs, e.g., the famous result (Khachiyan, 1978) on polynomial time solvability of Linear Programming. Aside of their theoretical importance, methods of this group yield fast and reliable tools for solving general-type convex optimization programs of low dimension (up to30-50 variables) and can be used to solve auxiliary problems when implementing numerous algorithms (e.g., restricted memory bundle methods) for large-scale convex optimization.