{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Transforming convex optimization problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [10 points] LP as special case of SDP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given $A\\in\\mathbb{R}^{m\\times n}$, $b\\in\\mathbb{R}^{m}$, $c\\in\\mathbb{R}^{n}$, rewrite the LP\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",
    "that is, write the matrix $F(x)$ appearing in the LMI constraint of the SDP in terms of the data of the LP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [10 points] SOCP as special case of SDP "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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}$, rewrite the SOCP \n",
    "$$\\underset{x\\in\\mathbb{R}^{n}}{\\text{minimize}}\\qquad f^{\\top}x\\\\\n",
    "\\text{subject to}\\quad \\parallel A_{i}x + b_{i}\\parallel_{2}\\;\\leq\\; c_{i}^{\\top}x + d_{i}, \\quad i=1,...,m,$$\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",
    "that is, write the matrix $F(x)$ appearing in the LMI constraint of the SDP in terms of the data of the SOCP.\n",
    "\n",
    "(Hint: Use the Schur Complement Lemma in Lecture 8, p. 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (c) [30 points] GP as convex optimization problem "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The standard form of GP, given by\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",
    "where $f_{0}, f_{1}, ..., f_{m}$ are posynomials, and $h_{1}, ..., h_{p}$ are monomials, does not look like a convex optimization problem. But we can transform it to a convex optimization problem, by logarithmic change-of-variable $y_{i} = \\log x_{i}$ (so $x_{i} = \\exp(y_{i})$), followed by applying $\\log(.)$ to the objective function and to the both sides of the constraints:\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",
    "where $\\exp(y)$ denotes elementwise exponential of the vector $y\\in\\mathbb{R}^{n}$. Clearly, the above and the original problems are equivalent. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c.1) (10 points) 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": [
    "(c.2) (20 points) Prove that the transformed problem derived in part (c.1) 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": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}