{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***\n",
"# Problem Sheet 1 Part A - Solutions\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}}$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solution to Problem 1.1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(a) The function $f(x)=x^4$ has a strict minimum at $x=0$, but the second derivative satisfies $f''(0)=0$. \n",
" \n",
"(b) We construct a function that has a strict minimizer $x^*$, but such that every open neighourhood $U$ of $x^*$ contains other local minimizers. One such function is\n",
"\n",
"\\begin{equation*}\n",
" f(x) = \\begin{cases} x^4 (\\cos(1/x)+2) & \\text{ for } x\\neq 0\\\\\n",
" 0 & \\text{ for } x=0.\n",
" \\end{cases}\n",
" \\end{equation*}"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAEGCAYAAACNaZVuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+UHGWZL/Dvk2QymUlISGANSPgNRolCRA2/pZUjJLiC\nKCuJgII/yEU4y1nhArJqElBX5awLCIK5YlZcULguIEoCCKFh4UKIITFEkgAxkB+SSQgJCTOTSSbz\n3D/e7nT121Xd1d314+3u7+ecOVNVXV1VU1P19NNPvfWWqCqIiKi1DEp7A4iIKHkM/kRELYjBn4io\nBTH4ExG1IAZ/IqIWxOBPRNSCEg/+InKniHSJyNKIlvcjEVkmIn8VkZuiWCYRUbNLI/OfA+CMKBYk\nIicAOFFVPwjggwAmicjHo1g2EVEzSzz4q+ozALZ4p4nIYSIyT0QWishTIvK+sIsDMExEhgHoADAE\nQFe0W0xE1HyGpL0BObMBTFfVVSIyCcDtAE6r9CZVfV5EsgDezE26VVVXxreZRETNIfXgLyLDAZwI\n4P+KiOQmt+VeOwfA9TAZ/p63AFinqlNE5HAA7wfw3tz0x0XkEVV9NrE/gIioAaUe/GFKT1tU9Vj7\nBVV9AMADZd57DoDnVbUXAERkHoATADD4ExGVUbHmLyLtIrJARBaLyEsiMiNgvltE5FURWSIiEyst\nNvcDVd0OYLWInOtZ1tEht38NgFNFZLCItAE4FcDykO8lImpZFYO/qvYB+ISqfhjARABTcnX5PURk\nCoDDVfVIANMB3BG0PBG5B8D/A/A+EVkjIhcDOB/AV3MfHMsAnBVy+38H4G8AXgKwGMBiVX045HuJ\niFpWqLKPqvbkBttz77H7gT4bwF25eReIyCgRGauqJS1vVPWLAauZEm6Ti5Y1AOB/Vfs+IqJWF6qp\np4gMEpHFADYA+JOqLrRmOQDAWs/4+tw0IiJyUKjgr6oDubLPOADHichR8W4WERHFqarWPqq6TUSe\nBDAZwMuel9YDONAzPi43rYiI8LFhREQ1UFWpPFd4YVr77Csio3LDHQA+BWCFNdtDAL6Um+d4AFv9\n6v0AoKr8UcWMGTNS3wZXfrgvuC+4L8r/xCFM2Wd/AE+KyBIACwA8qqpzRWS6iFySC+hzYZprvgbg\n5wC+EbSwOwLbARERAY8/DkybBqxalfaWNLeKZR9VfQmA3w1YP7fGLw+zwksvBU46CfjQh0JvIxG1\niP5+E/jfegvo6ADmzAGGuHArahNKpT//u+5KY61uyWQyaW+CM7gvClp9X6xYYQI/APT2ZrB6dbrb\n08xSCf4S6WWLxtTqJ7kX90VBq++LN97wjmVY+olRKsF/+/Y01kpErtu6tfw4RSeV4M9/KBH5sWPD\nO++ksx2tgMGfiJzB4J+cVII//6FE5MeODUwU45NK8N+xI421EpHr7NjARDE+qQT/3t401kpErvMG\n/8mTgW8E3i5K9WLmT0TO8CaG06YBEyakty3NjsGfiJzhjQ3DhqW3Ha2AwZ+InOGNDR0d6W1HK2Dw\nJyJnMPNPTmrBP6ZeSomogTH4JyeV4A8AfX1prZmIXMXgn5zUgj9LP0Rk87b2Yc0/Xgz+ROQMZv7J\nSS3480YvIrIx+CeHmT8ROYPBPzkM/kTkDAb/5DD4E5ETVIvLwQz+8WLNn4ic0N8PDAyY4SFD+OD2\nuDHzJyInsOSTLN7kRURO8MaE9vb0tqNVpBb8d+1Ka81E5CJvTGhrS287WgWDPxE5wRsTWO+PX2rB\nf+fOtNZMRC5i5p8sZv5E5IT+/sIwg3/8GPyJyAnM/JNVMfiLyDgRmS8ifxWRl0Tkn33mOVVEtorI\ni7mfb1daLoM/EXkx+CcrzGWVfgDfVNUlIjICwCIReUxVV1jzPa2qZ4VdMYM/EXkx+CerYuavqhtU\ndUlu+F0AywEc4DOrVLNiBn8i8mLwT1ZVNX8ROQTARAALfF4+QUSWiMjDInJUpWUx+BORF5t6Jiv0\nLs6VfH4H4IrcNwCvRQAOUtUeEZkC4EEA7yu3PAZ/IvJi5p+sUMFfRIbABP5fq+rv7de9HwaqOk9E\nfiYiY1T17dKlzQQAPPkkkM1mkMlkatpwImoubOpZkM1mkc1mY11H2Mz/lwBeVtWb/V4UkbGq2pUb\nngRA/AM/kA/+kyYBjPtElMfMvyCTKU6MZ82aFfk6KgZ/ETkJwPkAXhKRxQAUwHUADgagqjobwLki\ncimAXQB6AZxXabks+xCRF4N/sioGf1V9FsDgCvPcBuC2albM4E9EXgz+yeIdvkTkBLb2SRaDPxE5\ngZl/shj8icgJDP7JYpfOROQEBv9kMfMnIiewnX+yGPyJyAnM/JPF4E9ETmDwTxaDPxE5gU09k+VM\n8N+xw/T3092dzvYQUTJUgWefBbq6iqcz80+WM8H/H/8R+OQngZNP5rcComZ22WXmPJ8wAdi+vTCd\nwT9ZTjT17O0FnnjCDC9ZAjzzTDrbRETx6u0Fbr/dDG/eDDz/fOE1Bv9kOZH5r19f/Jo9TkTNwS71\neM91NvVMlhPB/+9/L35t06Zkt4WIkvHWW8Xj3nOfmX+ynAj+77xT/BqDP1FzsoO/99xn8E+WE8Hf\ne9EHAN61HxJJRE3BTvS2bSsMs6lnspwM/j09yW4LESXDbsrN1j7pcTL49/Ymuy1ElAwGf3c40dST\nwZ+oNTD4u8OJzN8O9gz+RM3JDv7eEi+beiYrteDf329u8wZK+/Zn8CdqTnbw7+srDDPzT1biwX+w\n51Hw+U96O/jzgi9Rc7ITux07CsNs7ZOsxIO/9xM9/8/2fvoDzPyJmpVfh45+rzHzj58TwZ9lH6LW\nYJ/rDP7pYfAnosTY5zpr/ulJNfjnDwSWfYhaA8s+7nAy8+cFX6Lm5Ff2ybf6Y1PPZKUa/INa+/T1\nAQMDyW0TESXDPtdVC0kgM/9kOZn5A8VfB4moOZQ719nUM1lOBH+75g+w7k/UjPwe0Zo//5n5J6ti\n8BeRcSIyX0T+KiIvicg/B8x3i4i8KiJLRGRi0PLCZv5+04iosYXN/Bn84xfmy1U/gG+q6hIRGQFg\nkYg8pqor8jOIyBQAh6vqkSJyHIA7ABzvtzAGf6LWxeDvjoqZv6puUNUlueF3ASwHcIA129kA7srN\nswDAKBEZ67e8sGUfBn+i5uNX9mHwT0dVNX8ROQTARAALrJcOALDWM74epR8QAIov5JTL/P0OEiJq\nbMz83RH6mnqu5PM7AFfkvgHUZO3amXuGFy3K4BOfyLDsQ9Qi/M7r/Dd/tvMvyGazyGazsa4jVPAX\nkSEwgf/Xqvp7n1nWAzjQMz4uN63E+PEzsXq1GT7qKPObZR+i1hCU+Q8MFN/bMyi1zubdkMlkkMlk\n9ozPmjUr8nWE3cW/BPCyqt4c8PpDAL4EACJyPICtqtrlN2PYC74s+xA1n6Cav13yEUlum1pVxcxf\nRE4CcD6Al0RkMQAFcB2AgwGoqs5W1bkicqaIvAagG8DFQctjax+i1hVU9mG9P3kVg7+qPgtgcIj5\nLg+zQjv4DwwU1/q8rxFRcwlK9Bj8k5f6Hb5BGT4zf6Lmw+DvjsSDv93Uk8GfqDXs3l3owdOLZZ90\npN6rZ1CQZ9mHqLmUS/S8pV926paM1Ms+fs08AWb+RM2mXPBn5p+81IM/yz5ErSHo2zzLPulwNviX\ne9wbEbnP+5QugJm/a1IP/mHKPldcAYwYAUyd6t8slIjccuONwJgxwAknlL+fB2Dmn5bUg3+lsk9P\nD3DLLaalwL33Ai+8EP82ElHt+vuBq682D2RasAB46ikznZm/W5xt6pk/GP7+9+Lp6317DCIiV7z1\nVvH4unXmd1DNn8E/Hc429cxPf/PN4umbNsWzXUQUjY0bi8fzCVy5sg+beiYv9bJPpZr/1q3F0+0D\ni4jcYidob79tfrPs45bUg3+lso/dyufdmp8kQERJ2LateHz7dvObZR+3OBv889Ptbwa9vfFsFxFF\nw07Q8uNs7eOW1IN/UNknKPPv6Ylnu4goGt3dxeP5zJ9lH7ekHvyZ+RM1Fzvz9wv+3ou6zPzT4VRT\nT+8/PSj4M/Mncpud+ec/DLwBfsSIwjAz/3Q41dTTe0Cw7EPUmOzMP38Oe8/1vfYqDLNXz3SkXvbx\nZvZ2NgCw7EPUaOxz1i/4e891ln3SkXrwDzogWPYhakz2dbxKwZ9ln3Q4G/xZ9iFqTHbClh8vV/MP\nuvZH8Uk9+HsPlOHDC8Ms+xA1pmozf7vsM3RofNtGBakH/0plH2b+RI2FZZ/G4FRTT28LgPzBwMyf\nqLHY5+yuXaZL9qCyDy/4piP1zL/ask9PT/HTgYjILX43bvb1MfN3jbPt/IPKPkHTiMgNfsF/x47y\n7fwZ/JOXeuZfqbWPX98/DP5E7go6Z73nuvdbvv2tgME/Gc4G/6CyT/59ROSmoMzfe94OGwYMHlwY\n9zbkYGufZKQe/Cvd4euX5Qf1BEpE6QtT9hk6FGhvL4x7+wNi5p+MisFfRO4UkS4RWRrw+qkislVE\nXsz9fLvc8qIo+wT1BEpE6QtT9mlrK87wGfyTF6YLpTkAfgrgrjLzPK2qZ4VaYZmmnmEzfwZ/IneF\nKfvYmb+3MzgG/2RUzPxV9RkAWyrMJmFXGLapJzN/osYUtuzDzD9dUdX8TxCRJSLysIgcVW7Gapt6\nMvgTNZYwZR87+DPzT14UPWcvAnCQqvaIyBQADwJ4X9DMP/rRzD3DfX0Z7NyZ2TPuDf79/eZmrnJl\nn95e4Prrgb33Bq66qrj1ABHF7/77gfnzgW9+EzjsMDMtTObf1sayTznZbBbZbDbWddQd/FX1Xc/w\nPBH5mYiMUdW3/eafNWsmvv99M7x7d/EB0d5urgnkH+wQ9Izf/Hu+8x3g3//dDI8fD3z2s/X+NUQU\n1ptvAuedZ87XhQuBBQvM9KA7fO2af1DZh009gUwmg0wms2d81qxZka8jbNlHEFDXF5GxnuFJACQo\n8AMmO5fcklSL++qxD4idO8sH/3zgB4D77qv8RxBRdP7yl0Ki9sILwKZN5pz2O2ftG7lY9klfxcxf\nRO4BkAGwj4isATADwFAAqqqzAZwrIpcC2AWgF8B5lZbZ1lY4ELz/9KFDi//x3d3+/fj4ZRbbtlVa\nKxFFad264vGNG4HRo/3PWb+7eL1lH+8HBoN/MioGf1X9YoXXbwNwW1UrHVI4ELxf99rbi7OB7dv9\n328/8xMoHSeieG3aVDy+eXNwYwz7gS125u/F4J+MxO/wBYr/ud4LuvYBUS74b7Ean3o/RIgofvb5\nuXlz8N33fjV/b+bvxeCfjNSDv5dd9vGWhLx27gS2bi2eFvRBQUTxsEut77wTnPlXqvl7Mfgnw6ng\nX03Zx870WfMnSpZ9fvb2ls/8y3Xv4MXWPslwJvgPGmRaAnlfCwroDP5E6bPPuZ6e8pk/yz5ucSb4\n5z/tg5p/efX1lQb/oHmJKB72OVgu+POCr3ucC/7e18qVfexg39fHxzsSJcnv+drVlH2Y+acrleA/\nxKeBaf5AqLXmn59ORMnwe742L/g2Ducy/7DB3/vknzw+3pEoOdUG/3LdO3gx+CfDueAf9oIvn+1L\nlK64yj5s7ZMMZ4K/X9mnXDt/Bn+idFWT+XvLtIMHm9Z9zPzT5Uzwr/aCr1+gZ/AnSk6l4B/UZXP+\nXPfL/EXYNXtSnAv+YWv+zPyJ0uUX/L3T9tqrMOw9l/3O9Txm/clxLvgHZf4jRxaGgzJ/b/fQRBQv\n+xzs7Q1+Mp/3XM6f4wz+6XIm+Fdq6unNIpj5E6WvUtnHm7CFLfsw+CfHmXb+lco+DP5E7hgYKG66\nCZQv+/gFf2b+6XIm84+i7JOftns3sGqVOUCJKBpvvFE4x/xa9dhlH2/w97b2KVf2YTPP5DgT/Cs1\n9awm8//yl4EjjgA+85n6t5WIgB/+EDjkEOAjHzHnZZhHNXrPWS+WfdzgTPD3y/y97OAflPmvWgXc\nfbcZnzu39GlDRFS9733P/H75ZeD224OTr6CyjxfLPm5wLvgHfe2zyz5BB9+qVcXT1qypbRuJyFAt\nLtusWRNN8Gfmn66GCf7eA6mvL/jge+ut4mnr19e2jURk2E/N6+/3P//sDwlvwubFpp5ucCb4d3QE\nvwaEv+BrB/933qltG4nIsM+hcs/q9fbHxbKP23waXcbP7+vesGHmd9jM3+8g2bGj9EOBT/giqo99\nDr39drjg39lp+vCxW92VK/vk4wDFL5XM3+8fnJ8WJvPftcs/8+/rK+0Mjg92J6qPfQ7Z7fm9vME/\nqNvmcmUfBv/kpBL88yUev2lhLvgG1fwZ/Imi5/es3qAbKr3ztrf7Z/flMn+/2EDxSKXsU2/mv3On\n+Tpp83u2L8s+RPWpJ/MvF/yZ+acrleDv9+leqeZvZ/5+/J7ty87eiOpjn0MM/s3Bmcy/mrJPuUfF\n2Zk/+/shqo99DoUN/kFln/y3e5Z90uVM8K9U9rHv8PXrt4fBnyh6tQb/oAu+zPzdUPGCr4jcKSJd\nIrK0zDy3iMirIrJERCZWWmYtZZ+OjuLeQPv7S+fp6/PvY5yIamcH+r6+cOcVyz5uC9PaZw6AM4Je\nFJEpAA5X1SMBTAdwR6UF1pL5B32F9PIL/sz8ierjdw5t2VL5fZVa+wweXPrIRpZ9klMx+KvqMwDK\n/avPBnBXbt4FAEaJyNhyy6yl5t/eXrm7V787fxn8iepTa/APyvy90+xzmpl/cqJo538AgLWe8fW5\naYFqKfsMG1Y5+Jcr++zeDSxaVHpNgIiKDQyYcyXfxNOvvl9P8PcGePt1Bv/kJH7Bd+bMmdi4MT+W\nyf1ULvsEHUhe5co+06cDd94JjB8PLFvm/zQxIgK+9jVgzhzg6KOBBQvqK/v4JWzM/CvLZrPIZrOx\nriOKELgewIGe8XG5ab5mzpyJv/3N9AnuVa7s094OiNSe+W/aZAI/AKxcCfz1r8Axx5RfFlGrmjPH\n/F66FHjggWTLPqz5G5lMBplMZs/4rFmzIl9H2LKP5H78PATgSwAgIscD2KqqXeUWVu0F3/zB4ncg\neS8YBWX+a9cWT1u3rtzWEbUu+474jRv9yz6bNxeGq/22zrKPGypm/iJyD0xtZh8RWQNgBoChAFRV\nZ6vqXBE5U0ReA9AN4OJKyywX/Mt9TfR7bdQo08sgYOr5dvv/HTtKn+bFPv6J/Nnnxltv+Wf+3j7+\nR40q7UodCG7tw7KPGyoGf1X9Yoh5Lq9mpX5f7YYPN7/9soj8AeF3II0cWQj+fn339/aWHpjs7I3I\nn30OBQV/73xBwT9M5p8/7/NY9klOKr162geESO2Zv7fbB7tfH8B8ZbXrk2zxQ+TPLvts3epf9vEG\n/6AndgXd4es9/+33MvgnJ5Xg79cjp+SuKJS76y8o86+EwZ8oHL8ePP0y/927C8OjRvkvq62tctnH\nfu/o0eG2k+qXSvC3qRaG/YJ/Z2fwa2GCv/fiFMDgTxTEzvy7uyvfKOkX/IcONQldpbIPg396nAj+\nXn4XfPLB3+9ACnpOqBeDP1E4YTN/r6DgD1TO/Pfeu/g1Bv/kOBf8Bw0q/QAol/l3dFRu/8/gTxRO\nT0/xeHd3cA+eeX7Bv1zzbO/5zb590pNa8L/c0z7oqquKX8sHe3s8KIuoFPztmr/fhWEi8u++uZ7M\nv9IF39NOKwwfeWTh2h/FL7VODm64wdxtu3MncOWVxa8NH15ovgmUz/zzbYnLBXTvsgBm/kRB7EDf\n3e3ffbqX33W3cpm/d9oZZwAXXWTuJp49u6pNpTqlFvz33ht47DH/16rJ/IcNq9znj1/wHxgAvv51\n09XDHXcAEys+hYCo+WzbBkybZoL+Pff4P7LR2yDDj1/mX+5pXd6yz6BBhe4kKFlOdm9mB/9y/f50\ndNQW/O+9F/jlL834VVcBjz9e27YSNbJbbwXmzjXD11xTei51d/s3zfbyC/75c7ZS5k/pce6CL1Bd\n5h8m+NtdPnR3A3ffXRh/4onqt5GoGfzkJ4XhX/2qtOzT3x/8zOw8v+Cfz+7LdeVC6Wqo4B90A1il\nC7627u7SJmWVvtoSNSM7ENfy2FO/mn8+8x8xovQ1Zv5uaPjgHybzt/X0lH4b4LN+qRXZrWtqefJd\nuczf7runvZ3P0nBFQwX/Wss+th07SlsHeXspJGoVdvC32/mHUa7mb2f+ft8EKB0NFfyjyvyB0rb/\nfj2CEjU7O9gXnrIXXrmyj535h7kjn5LRUME/qswfKO2Clpk/tRpV/y6cqzFkSOn5ChTKPsz83dUQ\nwT9/wNTavYMf+yCv5esuUSPbtav0Bi67KxQvv1p9voZvNwfNZ/52SYiZvzucDP72AfMP/2B+V3OT\nl91hlM0+yHnBl1qN3zFfrlmn3zmVD/J2q6H8uN1XT6V7Big5Tv4r3vve4vF88Pf7ehlU9qkU/O3W\nPj09wB/+AJxzDvDII+G3laiRrFwJTJ0K3Hhj9d92qwn+QR20Mfi7w8lGVwccUDyeD/5+9cKg4D96\nNPD66+HXuXo1cO21ZvjZZ4GuLnYyRc3nuuuA++83d7hXyy/4Bz1oyfthIFK4j+bUU6tfL8XDyc/h\nE08EDj7YDM+YUTiw/OqFQTX/Spm/7ZlnCsObNpWvfRI1qvvvLwzffHN176018//DH8w53NEBfO5z\n1a2T4uNk5t/ZCSxbZoLwoYcWpgcF/6DMvxpdXcXj69YB++5b3TKIXGbfxe59FGMY5drzB9X8AeDT\nnzbfwgcNAt7znurWSfFxMvgDpsQTpplYVMHfbt9cS3tnIpfZD2WxH9lYSf5c8y4nbM1/v/2qWxfF\nz8myTxC/zD+otU+1wX/TpuJx9vlPzcY+pqu94DtsWGlQD1PzJzc1VPC3M//2dtNveC2tfWz2icCn\nfVGzqTehaW8PzvDtc5OPY3RfQwV/+yaTcg+JrvdB0Az+1GzqDf6dncHB3062/K4PkFsaKvjb8g9/\n9rsWUG3mb3v3XeCyy4BJk4CFC+tbFlFa3n4bmDzZ/KxdW9+yOjpKM/qgO3nrPf8ofs5e8A2jXPCv\nN/P/4x+Bp582wxdcYG6OIWo03/0u8OijZrjeLkw6OoJb9djBv97zj+LX0Jl//m5BvwvB9R58+cAP\nAK+8UnpHMFEjuO22wvD//E99y+rsDM78x4wpns7M332hgr+ITBaRFSLyiohc4/P6qSKyVURezP18\nO/pNLRV05+/gwdH3Hrh9e7TLI2o0fpl/UM2fwd99FYO/iAwCcCuAMwBMADBNRN7vM+vTqnps7ud7\nEW/nHrNnF4ZvuMH8tjN/v4MUKM1OqmE/BJ6omQX1oBtU9jn77MJ7LryQXaM0gjA1/0kAXlXVNwBA\nRH4L4GwAK6z5Evl3f+Ur5sBqbzedsAH+zcz8WgCNGVN7EN+ypfhuY6JmNmYMsGFD8bRyF3zHjQP+\n9CfghReAiy9OZhupPmGC/wEAvO0E1sF8INhOEJElANYD+N+q+nIE21di8GDga18rnmZn/iNHRp/5\nb9kCrFljunzw612UyBX9/aY7hXHjal/GvvuWBv/OztJzzXsufPzj5ocaQ1QXfBcBOEhVJ8KUiB6M\naLmh2Jn/3nv71/zrCf433GA6mzv66NK7gYlcoWo6TzvySGDKlNqXs88+pdM6OljbbyZhMv/1AA7y\njI/LTdtDVd/1DM8TkZ+JyBhVLSmyzJw5c89wJpNBJpOpcpNL2c8JzWf+gwcXd15VT/B/6inze9Uq\n0xf6j39c+7KI4rJ4selFEwCy2dqX43eu+AV/NumMRzabRbaef2AIYYL/QgBHiMjBAN4EMBXANO8M\nIjJWVbtyw5MAiF/gB4qDf1Ty7f3z2trMdYGRI4sf1F5P8PdavTqa5RBFbf36yvOE4Zf5d3byZq6k\n2InxrFmzIl9HxeCvqrtF5HIAj8GUie5U1eUiMt28rLMBnCsilwLYBaAXwHmRb2kN9tqrOPhHlaXw\naUTkqmp76gwSlPnbXTIz829coe7wVdVHAIy3pv3cM3wbgNvs96VlfG5L7YtTftlMLdjsk1wV1f0o\nfs+y6OgADj+8eBpbwDWupslh/+u/zO+ODuDKK83wyJHF80TVp/jGjeaRj5/5DLt9oPT19Jgm0Bdc\nACxfHs0yhw/3v3/mIx8BJkww49Onl3a2SI2jaf51559vDswxYwpfTe2Dd+zYaNa1dKn5ya/jnnui\nWS5RLe6+G5gzJ9pl5pt1er9JjBhhgv3ChcDLLwMf/nC066RkNU3mDwDvf39xTdLO/KMK/l6/+U30\nyySqRr199vjp7Cy9Szd/B2/+GwCvfTW2pv732Xcj+gX/qK4DEKXFfjxjLfL9ZOV1dLAzw2bXNGUf\nP++8Uzzud+PX/vsDmzfXt5477jDNP6++mh8mlIyBAeA//sO0Ztuxo/7ljR1bfPNiZ2dpE2pqLk0d\n/D/4QeChh8xw/pGPtv32A5Ytq289l15qfu/caU5Iorg9+CBw1VXRLKuzs7S9fkcHcPLJwG9/a8YP\nPjiadZE7mrrsc9VVwIEHmuGf/tTUMO06pn1doB433RTdsojKifKenxEj/B/Gcs015k75IUOA++6L\nbn3khqbO/EePNg9i2bSp8CEwaFBxlw9R9/tPlIT+/uiW5Rf8x4wxpaC1a805E9Xd8eSOpg7+gMlc\n8oEfKL2IZfcLVK/LLzcnyrXXsvdPipYq8ItfAM89Z5paRmX48OA+e/xu9qLm0PTB36ZaPB515p9/\nbN6gQUAM3RhRC8tmgUsuiX65I0aUNtv0e5gLNZemrvn7ueKKwvCVV5YGf7+LwrW48cZolkOU9+c/\nR7Mcu8QzYgRw+umF8fHjQS2g5YL/9dcDkyeblgxXXFFa9jnssGjW09MDnHgi8J//Gc3yqHUtWACc\ncoppShwFu+VOZydw5pnAtGnAsccC994bzXrIbS1X9hk5Epg3rzBu91J46KHR9dfz3HPm54wzzP0E\nRNVSNYE5ys4E7Yu3bW2mTT+7KWktLZf527wXg4F4vvI+/TSwa1f0y6Xmpmpa20Tdi6zfk++o9bR8\n8D/mmEKrnFNOAY44Ivp1TJ0KHHQQ8OKL0S+bmtP27ab/nDhurho+HLjuusL41KnRr4Pc13JlH9vo\n0cAjjwBNJDQTAAAJCUlEQVTz55sHwz/3XPHr7e3R9J2yYQPwxS8Cjz7KuyWpvK4u4OabzSMZ47DX\nXsCMGab8s+++wCc/Gc96yG0tH/wBk/GfcooZtstAhx8eXZvqlSuBQw4Bvv1t80B4Itu8eeY5Ed4b\nEaM2erRpypl/7gW1ppYv+9gmTCg0hTvppHgu1H7ve+bbRlRPXaLG199vvn2eeWY8gf9b3yoMn3NO\n9MunxiNq3/UU58pENMn11WrxYuCJJ8yTkb7whXj6SweAj38ceOqpeJZNjeVf/xX4wQ/iW/7Onebu\n4P33Bz772fjWQ/EQEaiqVJ6zimUy+Jf3gx+YEzMu3/8+8E//BBx5ZHzrIHdt3Qr893+b601xOfFE\n4Nln41s+xY/BPwXbtpkMfeNG4Mc/Bi68MPp1jB5tbuQ54ojSXkepeb3xhvl2+cwz0S971izT7fOG\nDaZb849+NPp1UHIY/FOian527463z5MvfME8j5UPxW5uqsC//Vu83yiffx447jjTkSEft9j44gj+\nPCxCEDEnUFubuQvy8MOB73wn+vXcd59Zx/z50S+b3LBunelCJI7Af+215tvj1VebwA8w8FMwZv51\n+PrXzUW0OBx9tPm6znsCmkNvr7nP48EH41n+hAmmoUJUHROSW1j2cczAALBokWlBceKJ5lb8qA0b\nZgLGGWdEv2yK35IlwFe+Es8NWyLA0qWm+4ePfpTPj2hmDP4O+/OfgV//2nQM9y//Ev3yDzwQuPVW\nczcmnz7mtt27zQX8G2+MJ9O/5BLTRcNxxwHnnRf98sk9DP4NYs4c8+Drxx6LZ/nXXgt8/vOm7xe2\nDnLHmjXAww8D3/hGPMs/6yxT3pk5kw9baTUM/g1m8WLThn/zZtOeOw4XXABcdhnwsY+ZbnkpWa+8\nYq77/Pznpllw1ETMs3TjamZMjSG14C8ikwHcBNM66E5V/ZHPPLcAmAKgG8BFqrrEZ56WCv5et95q\n7ub93e/iW8fw4eZhNWedFU/vpARs2gTMnQvcdJOp58fl9NOBD3zABH1m+ZRK8BeRQQBeAXAagL8D\nWAhgqqqu8MwzBcDlqvppETkOwM2qerzPslo2+Od1dZnuIubNy+KBBzLYsiW+dY0ebbLFT33KXJQ+\n5hg37yHIZrPIZDJpb0aR3buBVatMZr90qcns16yJd50XXgh84ANZnHVWBhMmxLuuRuDicZGWOIJ/\nmFAwCcCrqvpGbiN+C+BsACs885wN4C4AUNUFIjJKRMaqaleUG9sMxo4Fzj0XWLYsi82bM+jqMv0I\nzZ9vuntevz66dW3ZAtxyi/kJMnQo8NWvAqeeau5f2G8/86HR3p7cB0WSJ/nAgPkA3rLFBPYlS4DZ\ns4E330xk9QBM2/vBg4HTTjPNP485BvjQh0yJZ+bMLCZMyCS3MQ5j8I9XmNP7AADeRozrYD4Qys2z\nPjeNwb8MERNszz/f/OT19QG/+Q3w+uvmxq/ly+Pbhp07gdtvNz+2Qw81v/v7zQeB/dPWVjpt8ODy\nF6H9Xlu5EnjhhcKd1EBhuJZpO3aY37t2mW45urvNtvb1meE0fPe75pGhn/+8SQB4oZ7S5mARgNrb\ngYsuMsMzZ5qA1dtryhBPPmkC5euvm6DZ0xPfdqxeHd+yba+9lty64vKxjwH77AMcdRTw6U+bO3n3\n3ZdNc8lNYWr+xwOYqaqTc+PXAlDvRV8RuQPAk6p6b258BYBT7bKPiLR2wZ+IqEZp1PwXAjhCRA4G\n8CaAqQCmWfM8BOAyAPfmPiy2+tX7o954IiKqTcXgr6q7ReRyAI+h0NRzuYhMNy/rbFWdKyJnishr\nME09L453s4mIqB6J3uRFRERuiKTDVxEZLSKPichKEXlUREYFzDdZRFaIyCsico1n+rkiskxEdovI\nsdZ7viUir4rIchE5PYrtjVME+8L3/SJysIj0iMiLuZ+fJfU3VSPo77LmuSX3P10iIhMrvTfsPnVN\nTPtihois8xwHk5P4W+pVw774sGf6nSLSJSJLrflb5bgIsy+qPy5Ute4fAD8CcHVu+BoAP/SZZxCA\n1wAcDKANwBIA78+9Nh7AkQDmAzjW854PAFgMU546JPd+iWKb4/qJYF/4vj8379K0/74Kf3vg3+WZ\nZwqAh3PDxwF4vtZ94vJPjPtiBoBvpv33JbUvcuMnA5hoH/+tdlxU2BdVHxdRPerhbAC/yg3/CoDf\nI6L33CymqrsA5G8Wg6quVNVXAdgXhM8G8FtV7VfV1wG8itJ7DFxT176o8H7XL5iX+7vyim4IBDBK\nRMZWeG+YfeqauPYF4P5xYKtnX0BVnwHgdy98qx0X5fYFUOVxEVXwf4/mWveo6gYA7/GZx+9msQMq\nLDfo5jGX1bsvxpZ5/yG5r3RPisjJ0W963cL8j4PmqXWfuCqufQEAl+fKAb9okFJHLfsizLke5lxz\nTVz7AqjyuAgd/EXkTyKy1PPzUu73WT6zN/VV5IT3Rf79bwI4SFWPBXAlgHtEpBluH6oli23W4yvM\nvvgZgMNUdSKADQB+Eu8mNZRmPS7CqPq4CH2Hr6p+Kui13AWIsaraJSL7AdjoM9t6AAd5xsflppWz\nHsCBVb4ndjHviw1+71fVnQB25oZfFJFVAN4H4MX6/6LIhPkfB/1Ph5Z5r+8+cVws+0JVN3mm/x8A\nf4hoe+NUz74oJ8y55ppY9kUtx0VUZZ+HAFyUG/4ygN/7zLPnZjERGQpzs9hDPvN5s5+HAEwVkaEi\nciiAIwC8ENE2x6XefeH7fhHZV0wPqxCRw2D2xd9i2P56hPkfPwTgS8Ceu8fzNwRWvU8cF8u+yAW5\nvM8BWBbvnxGJevZFnqD0m1GrHRd5JfuipuMioivYYwA8DmAlzM1ge+em7w/gj575JufmeRXAtZ7p\nn4WpcfXClDfmeV77FszV8eUATk/rKn2C+yLo/fl/6IsA/gzgzLT/1oC/v+TvAjAdwCWeeW7N/U//\nguLWXVXtE9d/YtoXdwFYCtNK5EGY6yGp/60x74t7YLqT7wOwBsDFLXxcBO2Lqo8L3uRFRNSCoir7\nEBFRA2HwJyJqQQz+REQtiMGfiKgFMfgTEbUgBn8iohbE4E9E1IIY/ImIWtD/B56f40vmnaNEAAAA\nAElFTkSuQmCC\n",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"\n",
"xx = np.linspace(-0.01,0.01,1000)\n",
"def f(x):\n",
" return (x**4)*(np.cos(1/x)+2)\n",
"\n",
"% matplotlib inline\n",
"plt.plot(xx,f(xx),linewidth=3)\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We explain the construction of this function:\n",
"\n",
"* Start out with $g(x) = \\cos(1/x)+2$ for $x\\neq 0$ and $g(0)=1$. This function has minimizers $x_0=0$ and $x_k = 1/(\\pi k)$ for $k>0$, with values $g(x_k)=1$ at all minimizers. Therefore, any open interval around $0$ contains (infinitely many) local minimizers $x_k$ other than $x_0=0$. \n",
"* Multipy $x^4$ to the function: $f(x) = x^4g(x)$. This ensures that $f(0)=0$ and $f(x)>0$ for $x\\neq 0$. There are still local minima in every neighbourhood of $0$. To see this, compute the derivative\n",
" \n",
" \\begin{equation*}\n",
" f'(x) = x^2(4x\\cos(1/x)+\\sin(1/x)+8x).\n",
" \\end{equation*}\n",
" \n",
"Set $z_m=1/(\\pi/2+m\\pi)$ for $m>0$. Since $\\sin(1/z_m)=\\sin(\\pi/2+m\\pi)= 1$ for $m$ even and $-1$ for $m$ odd, for $m$ sufficiently large the derivative changes signs between successive $z_m$. Since $f'(x)$ is continuous, it has roots between any $z_m$ and $z_{m+1}$ for large enough $m$, and these correspond to maxima and minima of $f$.\n",
"\n",
"The function is in $C^2(\\R)$. For $x\\neq 0$ this is clear, and to verify this at $x=0$, one shows that the right and left limits as $x\\to 0$ of $f'(x)$ and $f''(x)$ coincide (they are in fact $0$).\n",
"\n",
"Note the subtle point that one minimizer $x^*$ can have local minimizers that are arbitrary close: while each open interval $I$ surrounding $x^*$ has another local minimizer $\\tilde{x}$, every such $\\tilde{x}$ has an interval $\\tilde{I}$ surrounding it where this $\\tilde{x}$ is the only minimizer!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solution to Problem 1.2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We want to show that the 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",
"is convex if and only $\\mtx{A}$ is positive semidefinite. To see this, we compute the partial derivatives and the Hessian of $f$. The parts $\\vct{b}^{\\trans}\\vct{x}$ and $c$ disappear when computing second derivatives. The function $\\vct{x}^{\\trans}\\mtx{A}\\vct{x}$ can be written as\n",
"\n",
"\\begin{equation*}\n",
" \\vct{x}^{\\trans}\\mtx{A}\\vct{x} = \\sum_{i=1}^m\\sum_{j=1}^n a_{ij}x_ix_j,\n",
"\\end{equation*}\n",
"\n",
"so that the first derivative is\n",
"\n",
"\\begin{equation*}\n",
" \\frac{\\partial f}{\\partial x_i} = \\frac{1}{2} \\sum_{j\\neq i} (a_{ij}+a_{ji}) x_j + a_{ii}x_i+b_i = \\sum_{j=1}^n a_{ij}x_j+b_i,\n",
"\\end{equation*}\n",
"\n",
"where we used the symmetry of $\\mtx{A}$ (i.e., $a_{ij}=a_{ji}$). The gradient and Hessian are therefore just given by\n",
"\n",
"\\begin{equation*}\n",
" \\nabla f(\\vct{x}) = \\mtx{A}\\vct{x}+\\vct{b}, \\quad \\nabla^2f(\\vct{x}) = \\mtx{A}.\n",
"\\end{equation*}\n",
"\n",
"An interesting special case is when the quadratic function arises in the form\n",
"\n",
"\\begin{equation*}\n",
" f(\\vct{x}) = \\frac{1}{2}\\norm{\\mtx{A}\\vct{x}-\\vct{b}}_2^2. \n",
"\\end{equation*}\n",
"\n",
"The quadratic equation then has the form\n",
"\n",
"\\begin{equation*}\n",
" \\norm{\\mtx{A}\\vct{x}-\\vct{b}}_2^2 = (\\mtx{A}\\vct{x}-\\vct{b})^{\\trans}(\\vct{A}\\vct{x}-\\vct{b}) = \\vct{x}^{\\trans}\\mtx{A}^{\\trans}\\mtx{A}\\vct{x}-2\\vct{b}^{\\trans}\\mtx{A}\\vct{x}+\\norm{\\vct{b}}_2^2.\n",
"\\end{equation*}\n",
"\n",
"The matrix $\\mtx{A}^{\\trans}\\mtx{A}$ is always symmetric and positive semidefinite:\n",
"\n",
"\\begin{equation*}\n",
" (\\mtx{A}^{\\trans}\\mtx{A})^{\\trans} = \\mtx{A}^{\\trans}(\\mtx{A}^{\\trans})^{\\trans} = \\mtx{A}^{\\trans}\\mtx{A}, \\quad \\text{ and } \\quad \\vct{x}^{\\trans}\\mtx{A}^\\trans\\mtx{A}\\vct{x} = \\norm{\\mtx{A}\\vct{x}}_2^2>0 \\text{ if and only if } \\vct{x}\\neq \\zerovct,\n",
"\\end{equation*}\n",
"\n",
"so that the least squares function is convex. We also see that the derivative is\n",
"\n",
"\\begin{equation*}\n",
" \\mtx{A}^{\\trans}(\\mtx{A}\\vct{x}-\\vct{b}).\n",
"\\end{equation*}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solution to Problem 1.3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(a) This set is not convex: take $\\vct{x}=(1,0,0)^{\\trans}$ and $\\vct{y}=(-1,0,0)^{\\trans}$, then $\\frac{1}{2}\\vct{x}+\\frac{1}{2}\\vct{y}=\\zerovct \\not\\in S$.\n",
"\n",
"(b) This set is convex: if $\\vct{x},\\vct{y}\\in S$, then $1\\leq x_1-x_2<2$ and $1\\leq y_1-y_2<2$, and\n",
"\n",
" \\begin{equation*}\n",
" \\lambda x_1+(1-\\lambda)y_1-\\lambda x_2-(1-\\lambda)y_2 = \\lambda (x_1-x_2)+(1-\\lambda)(y_1-y_2)<\\lambda 2+(1-\\lambda)2 = 2,\n",
" \\end{equation*}\n",
" \n",
"with the same argument giving the lower bound. \n",
" \n",
"(c) This set is convex. In fact, $S$ is the unit ball of the $1$-norm\n",
"\n",
"\\begin{equation*}\n",
" \\norm{\\vct{x}}_1 = \\sum_{i=1}^d |x_i|.\n",
" \\end{equation*}\n",
"\n",
"Given $\\vct{x},\\vct{y}\\in S$,\n",
"\n",
"\\begin{equation*}\n",
" \\norm{\\lambda \\vct{x}+(1-\\lambda)\\vct{y}}_1 \\leq \\lambda \\norm{\\vct{x}}_1+(1-\\lambda)\\norm{\\vct{y}}_1 \\leq \\lambda \\cdot 1+(1-\\lambda)\\cdot 1 = 1.\n",
" \\end{equation*}\n",
"\n",
"(d) This set is convex. Here, one needs to show that convex combinations preserve symmetry and positive definiteness of a matrix. The symmetry is clear. As for the positive definiteness, let $\\vct{x}\\neq \\zerovct$ be given. Then\n",
"\n",
" \\begin{equation*}\n",
" \\vct{x}^{\\trans}(\\lambda \\mtx{A}+(1-\\lambda)\\mtx{B})\\vct{x} = \\lambda \\vct{x}^{\\trans}\\mtx{A}\\vct{x}+(1-\\lambda)\\vct{x}^{\\trans}\\mtx{B}\\vct{x} \\geq 0,\n",
" \\end{equation*}\n",
"\n",
"which shows that positive definiteness is also preserved."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solution to Problem 1.4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(a) This function is not convex. There are various ways of deriving this. For example, one can verify that the Hessian, or second derivative, is $-1/x^2$, which is not positive semidefinite. \n",
" \n",
" Alternatively, one can also prove the statement using a pedestrian approach. We have to show that there are points $y\\neq x$ and $\\lambda \\in [0,1]$ such that\n",
" \n",
" \\begin{equation*}\n",
" \\log(\\lambda x+(1-\\lambda)y) > \\lambda \\log(x)+(1-\\lambda)\\log(y).\n",
" \\end{equation*}\n",
" \n",
" Let's choose $y=0$. Then what needs to be shown is that for the points $\\vct{p}_1=(1,0)$ and $\\vct{p}_2=(x,\\log(x))$,\n",
" the line joining $\\vct{p}_1$ and $\\vct{p}_2$ lies {\\em below} the curve $(t,\\log(t))$ between $1$ and $x$. The line is given by the equation\n",
" \n",
" \\begin{equation*}\n",
" \\ell(t) = \\frac{\\log(x)}{x-1}(t-1).\n",
" \\end{equation*}\n",
" \n",
" Evaluating this, for example, at $x=2$ and $t=1.5$, one sees that $\\ell(t)>\\log(t)$, which is enough evidence that $\\log(t)$ is not convex.\n",
" With a little more effort one can deduce that the function is actually concave.\n",
"\n",
"(b) The function $f(x)=x^4$ is convex, as we will verify using Theorem 2.4. First, note that the derivative $4x^3$ is an increasing function with $x$. \n",
"Given two points $(x,x^4)$ and $(y,y^4)$ with $y>x$, the line connecting them has slope $(y^4-x^4)/(y-x)$. By the mean value theorem, there exists a $z\\in (x,y)$ such that\n",
"\n",
"\\begin{equation*}\n",
" \\frac{y^4-x^4}{y-x} = f'(z) = 4z^3 \\geq 4x^3.\n",
"\\end{equation*}\n",
"\n",
"Rearranging this inequality, we get\n",
"\n",
"\\begin{equation*}\n",
" f(y)-f(x) = y^4-x^4 \\geq 4x^3(y-x) = f'(x)(y-x),\n",
"\\end{equation*}\n",
"\n",
"which is precisely the criterium for convexity in Theorem 2.4(1).\n",
"\n",
"(c) Using Theorem 2.4(2), we compute the Hessian as\n",
"\n",
"\\begin{equation*}\n",
" \\nabla^2f(\\vct{x}) = \\begin{pmatrix}\n",
" 0 & 1\\\\\n",
" 1 & 0\n",
" \\end{pmatrix}.\n",
"\\end{equation*}\n",
"\n",
"This matrix is positive semidefinite on $\\R^2_{++}$, since for all $\\vct{x}\\in \\R^2_{++}$ we have\n",
"\n",
"\\begin{equation*}\n",
" \\vct{x}^{\\trans}\\nabla^2f(\\vct{x})\\vct{x} = 2x_1x_2>0.\n",
"\\end{equation*}\n",
"\n",
"It follows that the function $f(\\vct{x})=x_1x_2$ is convex.\n",
"\n",
"(d) The Hessian matrix of $f(\\vct{x})=x_1/x_2$ is \n",
"\n",
"\\begin{equation*}\n",
" \\nabla^2f(\\vct{x}) = \\begin{pmatrix}\n",
" 0 & -\\frac{1}{x_2^2}\\\\\n",
" -\\frac{1}{x_2^2} & 2\\frac{x_1}{x_2^3}\n",
" \\end{pmatrix}.\n",
"\\end{equation*}\n",
"\n",
"This matrix is not positive semidefinite for all valid values of $\\vct{x}$ (take for example $\\vct{x}=(1,1)^{\\trans}$, which leads to a negative eigenvalue).\n",
"\n",
"(e) The function $e^x-1$ is convex, as is easily seen using Theorem 2.4(2) by computing the second derivative.\n",
"\n",
"(f) The function $f(\\vct{x})=\\max_i x_i$ is convex. Here, we can't use the criteria from Theorem 2.4 since the \n",
"function is not differentiable, so we have to verify convexity directly:\n",
"\\begin{equation*}\n",
" \\max_i \\lambda x_i+(1-\\lambda)y_i \\leq \\lambda \\max_i x_i+(1-\\lambda) \\max_i y_i.\n",
"\\end{equation*}"
]
},
{
"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.12"
}
},
"nbformat": 4,
"nbformat_minor": 0
}