M.Sc Student | Cabelev Dmitry |
---|---|

Subject | Polynomial Time Cutting Plane Algorithms Associated with Symmetric Cones |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Nemirovski Arkadi |

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

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.