{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***\n",
"# Problem Sheet 1\n",
"***\n",
"$\\newcommand{\\vct}[1]{\\mathbf{#1}}$\n",
"$\\newcommand{\\mtx}[1]{\\mathbf{#1}}$\n",
"$\\newcommand{\\e}{\\varepsilon}$\n",
"$\\newcommand{\\norm}[1]{\\|#1\\|}$\n",
"$\\newcommand{\\minimize}{\\text{minimize}\\quad}$\n",
"$\\newcommand{\\maximize}{\\text{maximize}\\quad}$\n",
"$\\newcommand{\\subjto}{\\quad\\text{subject to}\\quad}$\n",
"$\\newcommand{\\R}{\\mathbb{R}}$\n",
"$\\newcommand{\\trans}{T}$\n",
"$\\newcommand{\\ip}[2]{\\langle {#1}, {#2} \\rangle}$\n",
"$\\newcommand{\\zerovct}{\\vct{0}}$\n",
"$\\newcommand{\\diff}[1]{\\mathrm{d}{#1}}$\n",
"$\\newcommand{\\dom}{\\mathrm{dom} }$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Part A\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Find examples of\n",
"\n",
"(a) A function $f\\in C^2(\\R)$ with a strict minimizer $x$ such that $f''(x)=0$ (that is, the second derivative is not positive definite).\n",
"\n",
"(b) A function $f\\colon \\R\\to \\R$ with a strict minimizer $x^*$ that is not an isolated local minimizer. **Hint:** Consider a rapidly oscillating function that has minima that are arbitrary close together, but not equal."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For this problem you might want to recall some linear algebra.\n",
"\n",
"(a) Let $\\mtx{A}\\in \\R^{n\\times n}$ by a symmetric matrix, $\\vct{b}\\in \\R^n$ and $c\\in \\R$. Show that the quadratic function\n",
" \n",
" \\begin{equation*}\n",
"f(\\vct{x}) = \\frac{1}{2}\\vct{x}^{\\trans}\\mtx{A}\\vct{x}+\\vct{b}^{\\trans}\\vct{x}+c \n",
" \\end{equation*}\n",
"\n",
"with symmetric $\\mtx{A}$\n",
"is convex if and only if $\\mtx{A}$ is positive semidefinite.\n",
"\n",
"(b) Now let $\\mtx{A}\\in \\R^{m\\times n}$ by an arbitrary matrix. Show that the function\n",
"\n",
"\\begin{equation*}\n",
" f(\\vct{x}) = \\norm{\\mtx{A}\\vct{x}-\\vct{b}}_2^2\n",
"\\end{equation*}\n",
"\n",
"is convex (the $2$-norm is defined as $\\norm{\\vct{x}}_2=\\vct{x}^{\\trans}\\vct{x}$). Moreover, if $m\\geq n$ and the matrix $\\mtx{A}$ has rank $m$, then it is strictly convex and the unique minimizer is\n",
"\n",
"\\begin{equation*}\n",
" \\vct{x}^* = (\\mtx{A}^{\\trans}\\mtx{A})^{-1}\\mtx{A}^{\\trans}\\vct{b}.\n",
"\\end{equation*}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A set $S\\subseteq \\R^n$ is called *convex*, if for any $\\vct{x},\\vct{y}\\in S$ and $\\lambda\\in [0,1]$, \n",
"\n",
"\\begin{equation*}\n",
" \\lambda \\vct{x}+(1-\\lambda)\\vct{y}\\in S.\n",
"\\end{equation*}\n",
"\n",
"In words, for any two points in $S$, the line segment joining them is also in $S$. Which of the following sets are convex?\n",
"\n",
" (a) $S = \\{\\vct{x}\\in \\R^3 \\mid \\norm{\\vct{x}}_2=1\\}$ (the unit sphere);\n",
" \n",
" (b) $S = \\{\\vct{x}\\in \\R^2 \\mid 1\\leq x_1-x_2< 2\\}$;\n",
" \n",
" (c) $S = \\{\\vct{x}\\in \\R^n \\mid |x_1|+\\cdots+|x_n|\\leq 1\\}$;\n",
" \n",
" (d) $S = \\mathcal{S}^n_{+}\\subset \\R^{n\\times n}$, the set of symmetric, positive semidefinite matrices."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For this problem we generalize the notion of convexity to function not necessarily defined on all of $\\R^n$. Denote by $\\dom f$ the *domain* of $f$, i.e., the set of $\\vct{x}$ on which $f(\\vct{x})$ attains a finite value. A function $f$ is called *convex*, if $\\dom f$ is a convex set and for all $\\vct{x},\\vct{y}\\in \\dom f$ and $\\lambda\\in [0,1]$,\n",
"\n",
"\\begin{equation*}\n",
" f(\\lambda \\vct{x}+(1-\\lambda)\\vct{y})\\leq \\lambda f(\\vct{x})+(1-\\lambda)f(\\vct{y}).\n",
"\\end{equation*}\n",
"\n",
"Which of the following functions are convex?\n",
"\n",
"(a) $f(x) = \\log(x)$ on $\\R_{++}$ (the positive real numbers);\n",
" \n",
"(b) $f(x) = x^4$ on $\\R$;\n",
" \n",
"(c) $f(\\vct{x}) = x_1x_2$ on $\\R^2_{++}$;\n",
" \n",
"(d) $f(\\vct{x}) = x_1/x_2$ on $\\R^2_{++}$;\n",
"\n",
"(e) $f(x)=e^x-1$ on $\\R$;\n",
"\n",
"(f) $f(\\vct{x}) = \\max_i x_i$ on $\\R^n$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Part B\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In engineering applications (for example, in the synthesis of linear time-invariant dynamical systems) one sometimes encounters a problem of the form\n",
"\n",
"\\begin{equation*}\n",
" \\minimize \\norm{\\mtx{A}\\vct{x}-\\vct{b}}_\\infty,\n",
"\\end{equation*}\n",
"\n",
"with $\\mtx{A}\\in \\R^{m\\times n}$, $\\vct{b}\\in \\R^m$ and $\\norm{\\vct{x}}_\\infty = \\max_{1\\leq i\\leq n} |x_i|$ is the $\\infty$-norm. \n",
"\n",
"(a) Draw the *unit circle* $\\{\\vct{x}\\in \\R^2 \\mid \\norm{\\vct{x}}_\\infty \\leq 1\\}$.\n",
"\n",
"(b) Formulate a linear programming problem $\\mathcal{P}$ with decision variables $(\\vct{x},t)$, such that if $(\\vct{x}^*,t^*)$ is the unique minimizer of $\\mathcal{P}$, then $\\vct{x}^*$ is the unique minimizer of the above problem. \n",
"\n",
"Even though our problem is not a linear programming problem (the objective is not linear), it is *equivalent* to one, in the sense that a minimizer can be read off the solution of a linear programming problem.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using Python or another computing system, compute and plot the sequence of points $\\vct{x}_k$, starting with $\\vct{x}_0=(0,0)^{\\trans}$, for the gradient descent algorithm for the problem\n",
"\n",
"\\begin{equation*}\n",
" \\minimize \\norm{\\mtx{A}\\vct{x}-\\vct{b}}_2^2\n",
"\\end{equation*}\n",
"\n",
"with data\n",
"\n",
"\\begin{equation*}\n",
" \\mtx{A} = \\begin{pmatrix}\n",
" 1 & 2\\\\\n",
" 2 & 1\\\\\n",
" -1 & 0\n",
" \\end{pmatrix},\n",
"\\quad \\vct{b} = \\begin{pmatrix}\n",
" 10\\\\-1\\\\0\n",
" \\end{pmatrix}.\n",
" \\end{equation*}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Problem 1.7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider the *Rosenbrock function* in $\\R^2$,\n",
"\n",
" \\begin{equation*}\n",
" f(\\vct{x}) = 100(x_2-x_1^2)^2 + (1-x_1)^2.\n",
" \\end{equation*}\n",
"\n",
"Compute the gradient $\\nabla f$ and the Hessian $\\nabla^2 f$. Show that $\\vct{x}^*=(1,1)^{\\trans}$ is the only local minimizer of this function, and that the Hessian at this point is positive definite.\n",
" \n",
" Using Python or another computing system, draw a contour plot of the Rosenbrock function."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python [py27]",
"language": "python",
"name": "Python [py27]"
},
"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.12"
}
},
"nbformat": 4,
"nbformat_minor": 0
}