|M.Sc Student||Cabelev Dmitry|
|Subject||Polynomial Time Cutting Plane Algorithms Associated with|
|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 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.