{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Problem 1 [20 points] A set of matrices\n", "\n", "Consider the following set of matrices:\n", "\n", "$$\\mathcal{X} := \\bigg\\{X\\in\\mathbb{R}^{n\\times n} \\mid X_{ij}\\geq 0, \\quad \\displaystyle\\sum_{i=1}^{n}X_{ij} = \\displaystyle\\sum_{j=1}^{n}X_{ij} = 1, \\quad \\text{for all}\\quad i,j=1, ...,n\\bigg\\}.$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (a) [10 points] Convexity\n", "\n", "Prove that $\\mathcal{X}$ is a convex set." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (b) [(1+4) + (1+4) = 10 points] What kind of convex set\n", "\n", "(i) Is $\\mathcal{X}$ a cone? Why/why not?\n", "\n", "(ii) Is $\\mathcal{X}$ a polyhedron? Why/why not?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "# Problem 2 [50 points] Hulls" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (a) [1+4 = 5 points] Affine hull\n", "\n", "What is ${\\rm{aff}}\\left(\\mathbb{S}^{n}_{+}\\right)$, the affine hull of the set of $n\\times n$ positive semidefinite matrices? Give reasons to support your answer." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (b) [10 + 10 + 10 = 30 points] Properties of convex hull\n", "\n", "Consider nonempty sets $\\mathcal{A},\\mathcal{B},\\mathcal{X},\\mathcal{Y} \\subseteq \\mathbb{R}^{n}$.\n", "\n", "(i) Prove that if $\\mathcal{X}\\subseteq \\mathcal{Y}$, then ${\\rm{conv}}\\left(\\mathcal{X}\\right) \\subseteq {\\rm{conv}}\\left(\\mathcal{Y}\\right)$.\n", "\n", "(ii) Use (i) to prove that ${\\rm{conv}}\\left(\\mathcal{A}\\cap\\mathcal{B}\\right) \\subseteq {\\rm{conv}}\\left(\\mathcal{A}\\right) \\cap {\\rm{conv}}\\left(\\mathcal{B}\\right)$.\n", "\n", "(iii) Use (i) to prove that ${\\rm{conv}}\\left(\\mathcal{A}\\cup\\mathcal{B}\\right) = {\\rm{conv}}\\left({\\rm{conv}}\\left(\\mathcal{A}\\right) \\cup {\\rm{conv}}\\left(\\mathcal{B}\\right)\\right)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (c) [12 + (1+2) = 15 points] Convex hull of roots\n", "\n", "Consider a nonconstant univariate polynomial $p\\in\\mathbb{R}[x]$ (this notation means that the polynomial $p$ is in variable $x$, and it has real coefficients). \n", "\n", "Suppose $\\mathcal{R}=\\{r_1,r_2,...\\}$ is the set of all roots of the polynomial $p$. In general, some roots are real, and some complex conjugates.\n", "\n", "(i) **Prove that** all critical points (roots of the derivative) of $p$ must lie in ${\\rm{conv}}(\\mathcal{R})$, the convex hull of $\\mathcal{R}$.\n", "\n", "(To help you visualize the statement above, in the following figure, we plotted the roots (blue dots) of a randomly generated 10th degree polynomial, and its critical points (red dots) in the complex plane. In this plot, ${\\rm{conv}}(\\mathcal{R})$ is the polygon with sides depicted as the blue solid lines.) \n", "\n", "\n", "(ii) **Will the statement in (c)(i) change** if $p\\in\\mathbb{C}[x]$, that is, if the polynomial has complex coefficients? **Why/why not?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Problem 3 [30 points] Vector unit norm balls revisited" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this exercise, we take a closer look at the vector unit norm balls encountered in HW1, Prob. 2. \n", "\n", "For $i=1,...,n$, we use the symbol $e_{i}$ to denote the $i$th [standard basis vector](https://en.wikipedia.org/wiki/Standard_basis) in $\\mathbb{R}^{n}$. You can simply think of $e_{i}$ as the $i$th column of the $n\\times n$ identity matrix." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (a) [10 points] $p$ norm ball is a convex set for any $p\\geq 1$ \n", "\n", "From the plots in HW1, Prob. 2, we intuitively expect the unit $p$ norm balls to be convex sets for $p\\geq 1$, and nonconvex sets for $0\\leq p<1.$ This is indeed true.\n", "\n", "Use the Minkowski inequality (which can be thought of as the triangle inequality for $p$-norms whenever $p\\geq 1$): \n", "\n", "$$\\|u+v\\|_{p} \\leq \\|u\\|_{p} + \\|v\\|_{p}, \\quad \\forall u,v\\in\\mathbb{R}^{n}, \\quad p\\geq 1,$$\n", "\n", "to **prove that** the vector unit norm balls are convex sets for any $p\\geq 1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (b) [5 + 5 = 10 points] $1$ norm ball is a polyhedron\n", "\n", "Let us establish in **two different ways** that the $1$ norm ball $\\{x\\in\\mathbb{R}^{n}\\mid \\|x\\|_{1} \\leq 1\\}$ is a polyhedron.\n", "\n", "(i) Write the $1$ norm ball as the **intersection of $2n+1$ halfspaces in $\\mathbb{R}^{2n}$**. Hint: introduce $n$ additional variables.\n", "\n", "(From Lec. 5, p. 13-14, this allows us to conclude that the $1$ norm ball is a polyhedron.)\n", "\n", "(ii) Write the $1$ norm ball as the **convex hull of $2n$ points** in $\\mathbb{R}^{n}$ in terms of the vectors $e_i$.\n", "\n", "(From Lec. 6, p. 1, this allows us to conclude that the $1$ norm ball is a polyhedron.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (c) [5 + 5 = 10 points] $\\infty$ norm ball is a polyhedron\n", "\n", "Let us establish in **two different ways** that the $\\infty$ norm ball $\\{x\\in\\mathbb{R}^{n}\\mid \\|x\\|_{\\infty} \\leq 1\\}$ is a polyhedron.\n", "\n", "(i) Write the $\\infty$ norm ball as the **intersection of $2n$ halfspaces in $\\mathbb{R}^{n}$** in terms of the vectors $e_{i}$.\n", "\n", "(From Lec. 5, p. 13-14, this allows us to conclude that the $\\infty$ norm ball is a polyhedron.)\n", "\n", "(ii) Write the $\\infty$ norm ball as the **convex hull of $2^{n}$ points** in $\\mathbb{R}^{n}$.\n", "\n", "(From Lec. 6, p. 1, this allows us to conclude that the $\\infty$ norm ball is a polyhedron.)" ] } ], "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 }