{
 "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": [
    "## (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": [
    "## (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": [
    "# 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": [
    "## (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": [
    "## (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 QP."
   ]
  },
  {
   "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": [
    "## (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."
   ]
  }
 ],
 "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
}