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. A reformulation technique is presented which converts the problems in this class into convex and tractable problems. We show that this reformulation technique can be used to develop the dual of robust nonlinear optimization problems that are convex in the optimization variables and concave in the uncertain parameters. To find the dual of such problems we employ the `primal worst equals dual best' technique, where the uncertain parameters become variables in the dual. We show that the `dual best' formulation has the hidden convexity structure studied in this paper, and therefore can be reformulated into a tractable convex optimization problem. Additionally, we show that inverse optimization problems for general linear and nonlinear optimization problems also have the hidden convexity structure, and hence can also be reformulated as convex problems. The value of the reformulation is illustrated by several numerical experiments for the nutritious food supply chain model for the World Food Programme.

Article

Download

View Hidden convexity in a class of optimization problems with bilinear terms