{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1 [45 points] Geometric programming\n",
    "\n",
    "The standard form of geometric program (GP) given in Lec. 11, p. 19 is\n",
    "\n",
    "$$ \\underset{x\\in\\mathbb{R}^{n}_{>0}}{\\text{minimize}}\\qquad f_{0}(x)\\\\\n",
    "\\text{subject to}\\quad f_{i}(x) \\leq 1, \\quad i=1,...,m, \\\\\n",
    "\\qquad\\qquad h_{j}(x) = 1, \\quad j=1,...,p,$$\n",
    "\n",
    "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:\n",
    "\n",
    "$$ \\underset{y\\in\\mathbb{R}^{n}}{\\text{minimize}}\\qquad \\log\\left(f_{0}(\\exp(y))\\right)\\\\\n",
    "\\text{subject to}\\quad \\log(f_{i}(\\exp(y))) \\leq 0, \\quad i=1,...,m, \\\\\n",
    "\\qquad\\qquad \\log(h_{j}(\\exp(y))) = 0, \\quad j=1,...,p,$$\n",
    "\n",
    "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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [10 points] A simple case of the transformed problem\n",
    "\n",
    "To understand why the transformed problem is convex, consider the simple case: $m=p=1$, and that\n",
    "$$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.$$\n",
    "**Prove that** the transformed problem has the form \n",
    "$$\\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)\\\\\n",
    "\\text{subject to} \\qquad\\log\\left(\\displaystyle\\sum_{k=1}^{K_{1}}\\exp(r_{k}^{\\top}y + s_{k})\\right) \\leq 0,\\\\\n",
    "\\quad u^{\\top}y = t.$$\n",
    "\n",
    "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}$**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 1(a):\n",
    "\n",
    "Rewriting the GP problem in the given transformed form yields\n",
    "$$p_{k} = \\begin{pmatrix} \\beta_{1,k}\\\\\n",
    "\\vdots\\\\\n",
    "\\beta_{n,k}\\end{pmatrix}, \\quad q_{k} = \\log\\alpha_{k}, \\quad r_{k} = \\begin{pmatrix}b_{1,k}\\\\\n",
    "\\vdots\\\\\n",
    "b_{n,k}\n",
    "\\end{pmatrix}, \\quad s_{k} = \\log a_{k}, \\quad u = \\begin{pmatrix}d_{1}\\\\\n",
    "\\vdots\\\\\n",
    "d_{n}\\end{pmatrix}, \\quad t = -\\log c.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [20 points] Establishing that the transformed problem is convex\n",
    "\n",
    "**Prove that** the transformed problem derived in part (a) is indeed a convex optimization problem.\n",
    "\n",
    "(Hint: First show that log-sum-exp is a convex function using second order condition. Then think operations preserving function convexity.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 1(b):\n",
    "\n",
    "That log-sum-exp is convex follows from showing the Hessian is positive semidefinite (see p. 74 in textbook). Since convex composed with affine is convex, therefore the objective function appearing in the tranformed form given in (c.1) is a convex function.\n",
    "\n",
    "The inequality constraints appearing in the tranformed form given in (c.1) is zero sub-level set of a convex function, therefore it is a convex set. The equality constraint appearing in the tranformed form given in (c.1) is a hyperplane (which is a convex set). Since intersection of convex sets is convex, hence the constraint set in the tranformed form given in (c.1) is convex.\n",
    "\n",
    "Thus, the tranformed form given in (c.1) is minimization of a convex function over a convex set, which is a convex optimization problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (c) [15 points] Buying suitcase for holiday travel\n",
    "\n",
    "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.\n",
    "\n",
    "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\n",
    "\n",
    "$$\\alpha \\leq h/w \\leq \\beta, \\qquad \\gamma \\leq w/d \\leq \\delta.$$\n",
    "\n",
    "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.\n",
    "\n",
    "**Clearly formulate** the optimization problem Alice needs to solve in **GP standard form given in Lec. 11, p. 19**. **Explain all the details.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 1(c):\n",
    "\n",
    "Since volume equals to $hwd$, the optimization problem under consideration is\n",
    "\n",
    "\\begin{align*}\n",
    "&\\underset{(h,w,d)\\in\\mathbb{R}^{3}_{>0}}{\\text{maximize}} \\quad hwd\\\\\n",
    "& \\text{s.t.} \\qquad\\quad 2(hw + hd) \\leq A_{\\text{wall}},\\quad wd \\leq A_{\\text{floor}},\\\\\n",
    "& \\qquad\\qquad\\alpha \\leq h/w \\leq \\beta, \\qquad\\qquad \\gamma \\leq w/d \\leq \\delta.\n",
    "\\end{align*}\n",
    "\n",
    "However, the above is **not in GP standard form given in Lec. 11, p. 19**. We now transcribe it to the standard form as:\n",
    "\n",
    "\\begin{align*}\n",
    "&\\underset{(h,w,d)\\in\\mathbb{R}^{3}_{>0}}{\\text{minimize}} \\quad h^{-1}w^{-1}d^{-1}\\\\\n",
    "& \\text{s.t.} \\qquad\\quad \\frac{2}{A_{\\text{wall}}}hw + \\frac{2}{A_{\\text{wall}}}hd \\leq 1,\\quad \\frac{1}{A_{\\text{floor}}}wd \\leq 1,\\\\\n",
    "& \\qquad\\qquad\\alpha h^{-1}w \\leq 1, \\qquad \\frac{1}{\\beta}hw^{-1}\\leq 1, \\qquad \\gamma d w^{-1} \\leq 1, \\qquad \\frac{1}{\\delta}wd^{-1} \\leq 1.\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2 [55 points] Transformation of problems to SDP\n",
    "\n",
    "The motivation for the following problems comes from the inclusion diagram in Lec. 9, p. 22."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [10 points] LP as SDP\n",
    "\n",
    "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)\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad c^{\\top}x\\\\\n",
    "\\text{subject to}\\quad Ax \\preceq b,$$\n",
    "as the SDP\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad c^{\\top}x\\\\\n",
    "\\text{subject to}\\quad F(x) \\succeq 0,$$\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 2(a):\n",
    "\n",
    "We write the elementwise vector inequality $Ax \\preceq b$ as the LMI $F(x) \\succeq 0$, with the $m\\times m$ matrix\n",
    "\n",
    "$$F(x) = {\\rm{diag}}\\left(b - Ax\\right) = {\\rm{diag}}\\left(b_{1} - (Ax)_{1}, ..., b_{m} - (Ax)_{m}\\right).$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [10 points] QP as SDP\n",
    "\n",
    "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)\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad \\frac{1}{2}x^{\\top}Ax + b^{\\top}x + c\\\\\n",
    "\\text{subject to}\\quad Px \\preceq q,$$\n",
    "as the SDP\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad f^{\\top}x\\\\\n",
    "\\text{subject to}\\quad F(x) \\succeq 0,$$\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 2(b):\n",
    "\n",
    "Similar to part 2(a), we have $Px \\preceq q \\:\\Leftrightarrow {\\rm{diag}}\\left(q-Px\\right)\\succeq 0$. Now express $A\\in\\mathbb{S}^{n}_{+}$ as $A = WW^{\\top}$ where $W\\in\\mathbb{R}^{n\\times k}$ ([from linear algebra, we know this is always possible](https://en.wikipedia.org/wiki/Definite_symmetric_matrix#Decomposition)). \n",
    "\n",
    "To make the objective linear in $x$, apply the epigraph form (Lec. 11, p. 2) by letting $\\frac{1}{2}x^{\\top}A x \\leq t$. Then the objective becomes\n",
    "$$\\underset{(x,t)\\in\\mathbb{R}^{n}\\times\\mathbb{R}}{\\text{minimize}}\\quad t + b^{\\top}x + c.$$\n",
    "The constraint $\\frac{1}{2}x^{\\top}A x = \\frac{1}{2} \\parallel W^{\\top}x \\parallel_{2}^{2} \\leq t$, by Schur Complement Lemma (Lec. 8, p. 6), becomes\n",
    "\n",
    "$$G(x,t) := \\begin{pmatrix}\n",
    "I & W^{\\top}x\\\\\n",
    "x^{\\top}W & 2tI\n",
    "\\end{pmatrix} \\succeq 0.$$\n",
    "\n",
    "Let $z := \\begin{pmatrix}x\\\\ t\\end{pmatrix}$ be the new decision vector (that is, $z$ becomes the new $x$). Then the new objective is to minimize $f^{\\top}z$ with $f = \\begin{pmatrix}b\\\\ 1\\end{pmatrix}$. Notice that the constant $c$ doesn't matter since it will not change the argmin, but will only shift the minimum value. Finally, collecting the LMIs together:\n",
    "\n",
    "$$F(z) \\equiv F(x,t) = {\\rm{diag}}\\left(G(x,t), {\\rm{diag}}\\left(q-Px\\right)\\right) \\succeq 0.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (c) [10 points] QCQP as SDP\n",
    "\n",
    "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)\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad \\frac{1}{2}x^{\\top}Ax + b^{\\top}x + c\\\\\n",
    "\\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,\\\\\n",
    "\\qquad\\quad Px \\preceq q,$$\n",
    "as the SDP\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad f^{\\top}x\\\\\n",
    "\\text{subject to}\\quad F(x) \\succeq 0,$$\n",
    "\n",
    "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 QCQP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 2(c):\n",
    "\n",
    "As in part 2(b), let $A = W_{0}W_{0}^{\\top}$ and $M_{i}=W_{i}W_{i}^{\\top}$ for all $i=1,...,m$. \n",
    "\n",
    "Also let $t:=(t_{0},t_{1},...,t_{m})^{\\top} \\in\\mathbb{R}^{m+1}$, and $\\frac{1}{2}x^{\\top}A x = \\frac{1}{2} \\parallel W_{0}^{\\top}x \\parallel_{2}^{2} \\leq t_{0}$, $\\frac{1}{2}x^{\\top}M_{i} x = \\frac{1}{2} \\parallel W_{0}^{\\top}x \\parallel_{2}^{2} \\leq t_{i}$ for $i=1,...,m$. \n",
    "\n",
    "Define $z := (x,t)^{\\top} \\in \\mathbb{R}^{n+m+1}$. Following the same procedure as in part 2(b), we then get\n",
    "\n",
    "$$G_{i}(z) \\equiv G_{i}(x,t) := \\begin{pmatrix}\n",
    "I & W_{i}^{\\top}x\\\\\n",
    "x^{\\top}W_{i} & 2t_{i}I\n",
    "\\end{pmatrix} \\succeq 0 \\quad\\forall\\;i=0,...,m, \\qquad G(z) := {\\rm{diag}}\\left(G_{0}(z), G_{1}(z), ..., G_{m}(z)\\right)\\succeq 0.$$\n",
    "\n",
    "We also have the constraints $t_{i} + n_{i}^{\\top}x + r_{i} \\leq 0 \\:\\Leftrightarrow\\: \\begin{pmatrix}n_{i}\\\\ 0_{1\\times 1}\\\\ e_{i}^{m}\\end{pmatrix}^{\\top} \\begin{pmatrix}x\\\\ t\\end{pmatrix}\\leq -r_{i}$, where $e_{i}^{m}$ is the $i$th standard basis vector in $m$ dimensions. Letting $r:=(r_1, ..., r_{m})^{\\top}$, and $H$ to be the matrix with rows $\\begin{pmatrix}n_{i}\\\\ 0_{1\\times 1}\\\\ e_{i}^{m}\\end{pmatrix}^{\\top}$, we can write these constraints as a single inequality:\n",
    "\n",
    "$$H \\begin{pmatrix}x\\\\ t\\end{pmatrix} \\preceq -r \\quad\\Leftrightarrow\\quad {\\rm{diag}}\\left(-r - Hz\\right) \\succeq 0.$$\n",
    "Collecting the LMIs together, \n",
    "\n",
    "$$F(z) \\equiv F(x,t) := {\\rm{diag}}\\left(G(z), {\\rm{diag}}\\left(-r - Hz\\right), {\\rm{diag}}\\left(q-Px\\right)\\right) \\succeq 0.$$\n",
    "\n",
    "The objective of our SDP is $f^{\\top}z$ where\n",
    "$$f := \\begin{pmatrix}b\\\\e_{1}^{m+1}\\end{pmatrix}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (d) [10 points] SOCP as SDP\n",
    "\n",
    "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)\n",
    "\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\qquad f^{\\top}x\\\\\n",
    "\\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,\\\\\n",
    "\\qquad\\qquad\\qquad\\qquad Px \\preceq q,$$\n",
    "\n",
    "as the SDP\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad f^{\\top}x\\\\\n",
    "\\text{subject to}\\quad F(x) \\succeq 0,$$\n",
    "\n",
    "that is, write the matrix $F(x)$ appearing in the LMI constraint of the SDP in terms of the data of the SOCP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 2(d):\n",
    "\n",
    "For any vector $u$, from the Schur Complement Lemma, we know that \n",
    "$$\\parallel u \\parallel \\leq t \\quad \\Leftrightarrow \\quad \\begin{bmatrix} tI & u\\\\u^{\\top} & t\\end{bmatrix} \\succeq 0.$$\n",
    "Applying this to the given SOCP constraints result in the LMIs:\n",
    "$$G_{i}(x) := \\begin{bmatrix} \\left(c_{i}^{\\top}x + d_{i}\\right)I & A_{i}x + b_{i}\\\\\\left(A_{i}x + b_{i}\\right)^{\\top} & c_{i}^{\\top}x + d_{i}\\end{bmatrix} \\succeq 0, \\quad i=1, ..., m,$$\n",
    "which are equivalent to the single LMI:\n",
    "$$G(x) = {\\rm{diag}}\\left(G_{1}(x), ..., G_{m}(x)\\right) \\succeq 0,$$\n",
    "since a block diagonal matrix is positive semidefinite if and only if each of the diagonal block is positive semidefinite.\n",
    "\n",
    "Therefore, $F(x) = {\\rm{diag}}\\left({\\rm{diag}}\\left(q-Px\\right), G(x)\\right)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (e) [15 points] A nonlinear optimization problem as SDP\n",
    "\n",
    "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\n",
    "\n",
    "$$P(x) := P_{0} + x_{1}P_{1} + ... + x_{n}P_{n}, \\qquad x\\in\\mathbb{R}^{n}.$$\n",
    "\n",
    "Rewrite the nonlinear optimization problem\n",
    "\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad (Ax + b)^{\\top}\\left(P(x)\\right)^{-1}(Ax + b)\\\\\n",
    "\\text{subject to}\\quad P(x) \\succ 0,$$\n",
    "\n",
    "as the SDP\n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\quad f^{\\top}x\\\\\n",
    "\\text{subject to}\\quad F(x) \\succeq 0,$$\n",
    "\n",
    "that is, write the vector $f$ and the matrix $F(x)$ appearing in the SDP in terms of the data of the nonlinear problem.\n",
    "\n",
    "**Hint:** Think epigraph form Lec. 11, p. 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution for part 2(e):\n",
    "\n",
    "Following the hint, the epigraph form results in constraint $(Ax + b)^{\\top}\\left(P(x)\\right)^{-1}(Ax + b) \\leq t$, which by Schur Complement Lemma (Lec. 8, p. 6, last line), is equivalent to the LMI\n",
    "$$F(x,t) := \\begin{pmatrix}\n",
    "P(x) & (Ax+b)\\\\\n",
    "(Ax+b)^{\\top} & t\n",
    "\\end{pmatrix} \\succeq 0.$$\n",
    "\n",
    "Therefore, we get a standard form SDP in variable $z:=(x,t)^{\\top}$ with $f:=\\begin{pmatrix}0_{n\\times 1}\\\\ 1\\end{pmatrix}$ and $F(z)\\equiv F(x,t)$ given above."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}