Hidden Convexity in a Class of Optimization Problems with Bilinear Terms

In this paper we identify a new class of nonconvex optimization problems that can be equivalently reformulated to convex ones. These nonconvex problems can be characterized by convex functions with bilinear arguments. We describe several examples of important applications that have this structure. These include the problems with variable coefficients, the dual of robust nonlinear optimization problems that are convex in the optimization variables and concave in the uncertain parameters, and inverse optimization problems for general linear and nonlinear optimization problems. A simple reformulation technique is presented which converts the problems in this class into convex and tractable problems. We prove that under certain conditions these reformulated problems are conic representable and solvable in polynomial time. The value of the reformulation is illustrated by several numerical experiments for the nutritious food supply chain model for the World Food Programme and for large public sets of linear and quadratic optimization problems for inverse optimization and problems with variable coefficients. The numerical results show that exploiting hidden convexity reduces the computation time significantly.