A PROJECTION CUTTING PLANE ALGORITHM FOR CONVEX-PROGRAMMING PROBLEMS

The solution of a convex programming problem of the form min{phi(0)(x) /phi(j)(x, y) less than or equal to 0, j = 1,..., k} = min{phi(0)(x)\( x, y) is an element of Omega subset of R(n) X R(m)} is considered. The complexity of cutting plane methods for these problems depends on m n. In this paper, the problem is reformulated as min{phi(o)(x)/x is a n element of omega}, where omega = proj(R)n Omega, and the complexity depends only on n. How the cutting plane is found in the new formulati on is discussed, together with a complexity analysis of this operation . Finally, an example where the projection cutting plane algorithm is more efficient than standard cutting plane methods is presented.