In all known polynomial time algorithms of nonlinear convex optimization, the computational effort per iteration grows nonlinearly with the design dimension n of the problem (typically, as n3). As a result, in the case of extremely large-scale (tens and hundreds thousands of variables) convex programs, a single iteration of a polynomial time algorithm can become too expensive to be practical. In these cases one is enforced to use
