Convex Optimization · Problem 4.56

Duality — Boyd & Vandenberghe

Mathematics — Optimization · minimization-over-convex-hull-union

Problem

[P. Parrilo] We consider the problem of minimizing the convex function f0:Rn→Rf_0 : \mathbf{R}^n \to \mathbf{R} over the convex hull of the union of some convex sets, conv(⋃i=1qCi)\mathbf{conv}\left(\bigcup_{i=1}^q C_i\right). These sets are described via convex inequalities, Ci={x∣fij(x)≤0, j=1,…,ki},C_i = \{x \mid f_{ij}(x) \leq 0, \, j = 1, \ldots, k_i\}, where fij:Rn→Rf_{ij} : \mathbf{R}^n \to \mathbf{R} are convex. Our goal is to formulate this problem as a convex optimization problem. The obvious approach is to introduce variables x1,…,xq∈Rnx_1, \ldots, x_q \in \mathbf{R}^n, with xi∈Cix_i \in C_i, θ∈Rq\theta \in \mathbf{R}^q with θ⪰0\theta \succeq 0, 1Tθ=1\mathbf{1}^T \theta = 1, and a variable x∈Rnx \in \mathbf{R}^n, with x=θ1x1+⋯+θqxqx = \theta_1 x_1 + \cdots + \theta_q x_q. This equality constraint is not affine in the variables, so this approach does not yield a convex problem. A more sophisticated formulation is given by minimizef0(x)subject tosifij(zi/si)≤0,i=1,…,q,j=1,…,ki1Ts=1,s⪰0x=z1+⋯+zq,\begin{aligned} \text{minimize} & \quad f_0(x) \\ \text{subject to} & \quad s_i f_{ij}(z_i/s_i) \leq 0, \quad i = 1, \ldots, q, \quad j = 1, \ldots, k_i \\ & \quad \mathbf{1}^T s = 1, \quad s \succeq 0 \\ & \quad x = z_1 + \cdots + z_q, \end{aligned} with variables z1,…,zq∈Rnz_1, \ldots, z_q \in \mathbf{R}^n, x∈Rnx \in \mathbf{R}^n, and s1,…,sq∈Rs_1, \ldots, s_q \in \mathbf{R}. (When si=0s_i = 0, we take sifij(zi/si)s_i f_{ij}(z_i/s_i) to be 00 if zi=0z_i = 0 and ∞\infty if zi≠0z_i \neq 0.) Explain why this problem is convex, and equivalent to the original problem.

Related theory

Browse the problem library