Problem 1 [45 points] Geometric programming

The standard form of geometric program (GP) given in Lec. 11, p. 19 is

$$ \underset{x\in\mathbb{R}^{n}_{>0}}{\text{minimize}}\qquad f_{0}(x)\\ \text{subject to}\quad f_{i}(x) \leq 1, \quad i=1,...,m, \\ \qquad\qquad h_{j}(x) = 1, \quad j=1,...,p,$$

where $f_{0}, f_{1}, ..., f_{m}$ are posynomials, and $h_{1}, ..., h_{p}$ are monomials. This standard form is not a convex optimization problem. But we can transform it exactly to a convex optimization problem, by logarithmic change-of-variable $y_{i} = \log x_{i}$ (so $x_{i} = \exp(y_{i})$), followed by applying the monotone function $\log(.)$ to the objective and to the both sides of the constraints:

$$ \underset{y\in\mathbb{R}^{n}}{\text{minimize}}\qquad \log\left(f_{0}(\exp(y))\right)\\ \text{subject to}\quad \log(f_{i}(\exp(y))) \leq 0, \quad i=1,...,m, \\ \qquad\qquad \log(h_{j}(\exp(y))) = 0, \quad j=1,...,p,$$

where $\exp(y)$ denotes elementwise exponential of the vector $y\in\mathbb{R}^{n}$. Clearly, the above optimization problem and the original GP are equivalent.

(a) [10 points] A simple case of the transformed problem

To understand why the transformed problem is convex, consider the simple case: $m=p=1$, and that $$f_{0}(x) = \sum_{k=1}^{K_{0}}\alpha_{k}x_{1}^{\beta_{1,k}}...x_{n}^{\beta_{n,k}}, \qquad f_{1}(x) = \sum_{k=1}^{K_{1}}a_{k}x_{1}^{b_{1,k}}...x_{n}^{b_{n,k}}, \qquad h_{1}(x) = c x_{1}^{d_{1}} x_{2}^{d_{2}} ... x_{n}^{d_{n}}, \qquad \alpha_{k}, a_{k}, c> 0.$$ Prove that the transformed problem has the form $$\underset{y\in\mathbb{R}^{n}}{\text{minimize}}\qquad \log\left(\displaystyle\sum_{k=1}^{K_{0}}\exp(p_{k}^{\top}y + q_{k})\right)\\ \text{subject to} \qquad\log\left(\displaystyle\sum_{k=1}^{K_{1}}\exp(r_{k}^{\top}y + s_{k})\right) \leq 0,\\ \quad u^{\top}y = t.$$

In other words, derive the transformed problem data $p_{k}, q_{k}, r_{k}, s_{k}, u, t$ as function of the original problem data: $\alpha_{k}, \beta_{1,k}, ..., \beta_{n,k}, a_{k}, b_{1,k}, ..., b_{n,k}, c, d_{1}, ..., d_{n}$.

(b) [20 points] Establishing that the transformed problem is convex

Prove that the transformed problem derived in part (a) is indeed a convex optimization problem.

(Hint: First show that log-sum-exp is a convex function using second order condition. Then think operations preserving function convexity.)

(c) [15 points] Buying suitcase for holiday travel

While making air travel plans for the coming holidays, Alice realizes that she needs to buy a new travel suitcase of maximum volume. The decision variables are the height $h$, width $w$, and the depth $d$, which define the shape of a 3D rectangular suitcase.

However, the airlines has put some regulations on the shape of the check in luggage as follows. The airlines website specifies an upper bound $A_{\text{wall}}$ for the total wall area $2(hw + hd)$. It also specifies an upper bound $A_{\text{floor}}$ for the floor area $wd$. Furthermore, it specifies bounds for the aspect ratios $h/w$ and $w/d$ as

$$\alpha \leq h/w \leq \beta, \qquad \gamma \leq w/d \leq \delta.$$

Using the data $A_{\text{wall}}, A_{\text{floor}}, \alpha, \beta, \gamma, \delta$ from the airlines website, Alice needs to find the optimal suitcase, i.e., the tuple $(h,w,d)$ that maximizes the volume while respecting the shape constraints.

Clearly formulate the optimization problem Alice needs to solve in GP standard form given in Lec. 11, p. 19. Explain all the details.

Problem 2 [55 points] Transformation of problems to SDP

The motivation for the following problems comes from the inclusion diagram in Lec. 9, p. 22.

(a) [10 points] LP as SDP

Given $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, $c\in\mathbb{R}^{n}$, rewrite the LP (Lec. 10, p. 1) $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad c^{\top}x\\ \text{subject to}\quad Ax \preceq b,$$ as the SDP $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad c^{\top}x\\ \text{subject to}\quad F(x) \succeq 0,$$

that is, write the matrix $F(x)$ appearing in the linear matrix inequality (LMI) constraint of the SDP (see Lec. 10, p. 7) in terms of the data of the LP.

(b) [10 points] QP as SDP

Given $A \in \mathbb{S}^{n}_{+}$, $b\in\mathbb{R}^{n}$, $c\in\mathbb{R}$, $P\in\mathbb{R}^{m\times n}$, $q\in\mathbb{R}^{m}$, rewrite the QP (Lec. 10, p. 2) $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad \frac{1}{2}x^{\top}Ax + b^{\top}x + c\\ \text{subject to}\quad Px \preceq q,$$ as the SDP $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad f^{\top}x\\ \text{subject to}\quad F(x) \succeq 0,$$

that is, write the vector $f$ and the matrix $F(x)$ appearing in the linear matrix inequality (LMI) constraint of the SDP (see Lec. 10, p. 7) in terms of the data of the QP.

(c) [10 points] QCQP as SDP

Given $A \in \mathbb{S}^{n}_{+}$, $b\in\mathbb{R}^{n}$, $c\in\mathbb{R}$, $P\in\mathbb{R}^{p\times n}$, $q\in\mathbb{R}^{p}$, and $\left(M_{i},n_{i},r_{i}\right)\in\mathbb{S}^{n}_{++}\times\mathbb{R}^{n}\times\mathbb{R}$ for all $i=1,...,m$, rewrite the QCQP (Lec. 10, p. 3) $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad \frac{1}{2}x^{\top}Ax + b^{\top}x + c\\ \qquad\qquad\qquad\qquad\qquad\quad\text{subject to}\quad \frac{1}{2}x^{\top}M_{i}x + n_{i}^{\top}x + r_{i} \leq 0, \quad\text{for all}\;i=1,...,m,\\ \qquad\quad Px \preceq q,$$ as the SDP $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad f^{\top}x\\ \text{subject to}\quad F(x) \succeq 0,$$

that is, write the vector $f$ and the matrix $F(x)$ appearing in the linear matrix inequality (LMI) constraint of the SDP (see Lec. 10, p. 7) in terms of the data of the QP.

(d) [10 points] SOCP as SDP

Given $f\in\mathbb{R}^{n}$, $A_{i}\in\mathbb{R}^{(n_{i}-1)\times n}$, $b_{i}\in\mathbb{R}^{n_{i}-1}$, $c_{i}\in\mathbb{R}^{n}$, $d_{i}\in\mathbb{R}$, $P\in\mathbb{R}^{p\times n}$, $q\in\mathbb{R}^{p}$, rewrite the SOCP (Lec. 10, p. 5)

$$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\qquad f^{\top}x\\ \qquad\qquad\qquad\qquad\text{subject to}\quad \parallel A_{i}x + b_{i}\parallel_{2}\;\leq\; c_{i}^{\top}x + d_{i}, \quad i=1,...,m,\\ \qquad\qquad\qquad\qquad Px \preceq q,$$

as the SDP $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad f^{\top}x\\ \text{subject to}\quad F(x) \succeq 0,$$

that is, write the matrix $F(x)$ appearing in the LMI constraint of the SDP in terms of the data of the SOCP.

(e) [15 points] A nonlinear optimization problem as SDP

Given $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, and symmetric matrices $P_{0},P_{1}, ..., P_{n}\in\mathbb{S}^{m}$, define

$$P(x) := P_{0} + x_{1}P_{1} + ... + x_{n}P_{n}, \qquad x\in\mathbb{R}^{n}.$$

Rewrite the nonlinear optimization problem

$$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad (Ax + b)^{\top}\left(P(x)\right)^{-1}(Ax + b)\\ \text{subject to}\quad P(x) \succ 0,$$

as the SDP $$\underset{x\in\mathbb{R}^{n}}{\text{minimize}}\quad f^{\top}x\\ \text{subject to}\quad F(x) \succeq 0,$$

that is, write the vector $f$ and the matrix $F(x)$ appearing in the SDP in terms of the data of the nonlinear problem.

Hint: Think epigraph form Lec. 11, p. 2.