Polyhedral approximations in p-order cone programming

Abstract

This paper discusses the use of polyhedral approximations in solving p-order cone programming (pOCP) problems, or linear problems with p-order cone constraints, and their mixed-integer extensions. In particular, it is shown that the cutting-plane technique proposed in Krokhmal and Soberanis [Risk optimization with p-order conic constraints: A linear programming approach, Eur. J. Oper. Res. 201 (2010), pp. 653–671, http://dx.doi.org/10.1016/j.ejor.2009.03.053] for a special type of polyhedral approximations of pOCP problems, which allows for generation of cuts in constant time not dependent on the accuracy of approximation, is applicable to a larger family of polyhedral approximations. We also show that it can further be extended to form an exact solution method for pOCP problems with O(ϵ⁻¹) iteration complexity. Moreover, it is demonstrated that an analogous constant-time cut-generating algorithm exists for recursively constructed lifted polyhedral approximations of second-order cones due to Ben-Tal and Nemirovski [On polyhedral approximations of the second-order cone, Math. Oper. Res. 26 (2001), pp. 193–205. Available at http://dx.doi.org/10.1287/moor.26.2.193.10561]. It is also shown that the developed polyhedral approximations and the corresponding cutting-plane solution methods can be efficiently used for obtaining exact solutions of mixed-integer pOCP problems.

Keywords:

• p-order cone programming
• second-order cone programming
• polyhedral approximation
• cutting-plane methods
• mixed-integer p-order cone programming
• stochastic programming
• portfolio optimization