Last active
August 29, 2015 14:16
-
-
Save byronyi/de1a7e8c1124a78c223a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "metadata": { | |
| "name": "", | |
| "signature": "sha256:41aa6aecbe1aaab11b826e73169570b1c6e66ce50c092f82a7abd0572e721b63" | |
| }, | |
| "nbformat": 3, | |
| "nbformat_minor": 0, | |
| "worksheets": [ | |
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "# Assignment 1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Yi Bairen, 20026373\n", | |
| "\n", | |
| "(Available online at http://git.io/xR3u)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "from IPython.display import Latex, display\n", | |
| "\n", | |
| "from sympy.interactive import printing\n", | |
| "from sympy.printing.latex import latex\n", | |
| "from sympy.mpmath import mp\n", | |
| "\n", | |
| "printing.init_printing(use_latex=True)\n", | |
| "\n", | |
| "def print_func(func_str, func):\n", | |
| " if hasattr(func, 'expr'):\n", | |
| " latex_str = '$$' + func_str + '=' + latex(func.expr) + '$$'\n", | |
| " else:\n", | |
| " latex_str = '$$' + func_str + '=' + latex(func) + '$$'\n", | |
| " display(Latex(latex_str))\n", | |
| "\n", | |
| "mp.pretty = True" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 1 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "import numpy as np\n", | |
| "from sympy import log, exp, diff, symbols, vectorize, solve\n", | |
| "from sympy import Symbol, Float, Lambda, Matrix\n", | |
| "from sympy.abc import x\n", | |
| "\n", | |
| "@vectorize(0, 1)\n", | |
| "def vdiff(f, x):\n", | |
| " return diff(f, x).simplify()" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [], | |
| "prompt_number": 2 | |
| }, | |
| { | |
| "cell_type": "heading", | |
| "level": 1, | |
| "metadata": {}, | |
| "source": [ | |
| "Problem 1" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "f = Lambda((x), 2*log(exp(x)+1)-x)\n", | |
| "\n", | |
| "print_func(\"f(x)\", f)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x)=- x + 2 \\log{\\left (e^{x} + 1 \\right )}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1052a6f90>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 3 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "def Newton1D(f, x0, n_iter):\n", | |
| " df = Lambda((x), f.expr.diff(x).simplify())\n", | |
| " d2f = Lambda((x), df.expr.diff(x).simplify())\n", | |
| " \n", | |
| " print_func(\"f(x)\", f)\n", | |
| " print_func(\"f'(x)\", df)\n", | |
| " print_func(\"f''(x)\", d2f)\n", | |
| " \n", | |
| " xk = Float(x0)\n", | |
| " for k in range(n_iter+1):\n", | |
| " \n", | |
| " print ' '.join([\n", | |
| " \"x({}) = {:.3f}\".format(k, float(xk)),\n", | |
| " \"f(x) = {:.3f}\".format(float(f(xk))),\n", | |
| " \"f'(x) = {:.3f}\".format(float(df(xk))),\n", | |
| " \"f''(x) = {:.3f}\".format(float(d2f(xk)))\n", | |
| " ])\n", | |
| " x_temp = xk - df(xk) / d2f(xk)\n", | |
| " xk = x_temp\n", | |
| "\n", | |
| "Newton1D(f, 2., 4)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x)=- x + 2 \\log{\\left (e^{x} + 1 \\right )}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107110f10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f'(x)=\\tanh{\\left (\\frac{x}{2} \\right )}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10711c690>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f''(x)=\\frac{1}{2 \\cosh^{2}{\\left (\\frac{x}{2} \\right )}}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10711c790>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "x(0) = 2.000 f(x) = 2.254 f'(x) = 0.762 f''(x) = 0.210\n", | |
| "x(1) = -1.627 f(x) = 1.986 f'(x) = -0.671 f''(x) = 0.275\n", | |
| "x(2) = 0.819 f(x) = 1.549 f'(x) = 0.388 f''(x) = 0.425\n", | |
| "x(3) = -0.095 f(x) = 1.389 f'(x) = -0.047 f''(x) = 0.499\n", | |
| "x(4) = 0.000 f(x) = 1.386 f'(x) = 0.000 f''(x) = 0.500\n" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 4 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "def Secant(f, x_1, x0, n_iter):\n", | |
| " df = Lambda((x), f.expr.diff(x).simplify())\n", | |
| " print_func(\"f(x)\", f)\n", | |
| " print_func(\"f'(x)\", df)\n", | |
| " xk_1 = Float(x_1)\n", | |
| " xk = Float(x0)\n", | |
| " for k in range(n_iter+1):\n", | |
| " secant = (df(xk) - df(xk_1)) / (xk - xk_1)\n", | |
| " print ' '.join([\n", | |
| " \"x({}) = {:.3f}\".format(k-1, float(xk_1)),\n", | |
| " \"x({}) = {:.3f}\".format(k, float(xk)),\n", | |
| " \"f(x({})) = {:.3f}\".format(k, float(f(xk))),\n", | |
| " \"f'(x({})) = {:.3f}\".format(k-1, float(df(xk_1))),\n", | |
| " \"f'(x({})) = {:.3f}\".format(k, float(df(xk))),\n", | |
| " 'secant = {:.3f}'.format(float(secant))\n", | |
| " ])\n", | |
| " x_temp = xk - df(xk) / secant\n", | |
| " xk_1 = xk\n", | |
| " xk = x_temp\n", | |
| " \n", | |
| "Secant(f, 2.01, 2., 4)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x)=- x + 2 \\log{\\left (e^{x} + 1 \\right )}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10711c9d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f'(x)=\\tanh{\\left (\\frac{x}{2} \\right )}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071474d0>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "x(-1) = 2.010 x(0) = 2.000 f(x(0)) = 2.254 f'(x(-1)) = 0.764 f'(x(0)) = 0.762 secant = 0.209\n", | |
| "x(0) = 2.000 x(1) = -1.641 f(x(1)) = 1.995 f'(x(0)) = 0.762 f'(x(1)) = -0.675 secant = 0.395\n", | |
| "x(1) = -1.641 x(2) = 0.070 f(x(2)) = 1.388 f'(x(1)) = -0.675 f'(x(2)) = 0.035 secant = 0.415\n", | |
| "x(2) = 0.070 x(3) = -0.014 f(x(3)) = 1.386 f'(x(2)) = 0.035 f'(x(3)) = -0.007 secant = 0.500\n", | |
| "x(3) = -0.014 x(4) = 0.000 f(x(4)) = 1.386 f'(x(3)) = -0.007 f'(x(4)) = 0.000 secant = 0.500\n" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 5 | |
| }, | |
| { | |
| "cell_type": "heading", | |
| "level": 1, | |
| "metadata": {}, | |
| "source": [ | |
| "Problem 2" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "x1, x2 = symbols('x_1, x_2')\n", | |
| "x = (x1, x2)\n", | |
| "f = Lambda(x, 2*x1**2 + x2**2 - 2*x1*x2 + 2*x1**3 + x1**4)\n", | |
| "\n", | |
| "print_func(\"f{}\".format(x), f)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=x_{1}^{4} + 2 x_{1}^{3} + 2 x_{1}^{2} - 2 x_{1} x_{2} + x_{2}^{2}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10712d4d0>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 6 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "def Newton2D(f, x0, n_iter):\n", | |
| " g = Lambda(x, vdiff(f.expr, x))\n", | |
| " F = Lambda(x, Matrix(vdiff(g.expr, x)))\n", | |
| " \n", | |
| " g = Lambda(x, Matrix(g.expr))\n", | |
| " \n", | |
| " print_func(\"f{}\".format(x), f)\n", | |
| " print_func(\"g{}\".format(x), g)\n", | |
| " print_func(\"F{}\".format(x), F)\n", | |
| " \n", | |
| " xk = Matrix(x0)\n", | |
| " for k in range(n_iter+1):\n", | |
| " print\n", | |
| " print 'Iter {}'.format(k)\n", | |
| " print_func('x^{{({})}}'.format(k), \n", | |
| " Matrix(np.round(np.array(xk).astype(np.float), 3).squeeze()))\n", | |
| " print_func('f{}'.format(x), \n", | |
| " np.round(np.array(f(*xk)).astype(np.float), 3))\n", | |
| " print_func('g{}'.format(x), \n", | |
| " Matrix(np.round(np.array(g(*xk)).astype(np.float), 3).squeeze()))\n", | |
| " print_func('F{}'.format(x), \n", | |
| " Matrix(np.round(np.array(F(*xk)).astype(np.float), 2).squeeze()))\n", | |
| " x_temp = xk - F(*xk)**-1 * g(*xk)\n", | |
| " xk = x_temp\n", | |
| " \n", | |
| "Newton2D(f, (0.5, 0.6), 4)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=x_{1}^{4} + 2 x_{1}^{3} + 2 x_{1}^{2} - 2 x_{1} x_{2} + x_{2}^{2}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107034090>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}4 x_{1}^{3} + 6 x_{1}^{2} + 4 x_{1} - 2 x_{2}\\\\- 2 x_{1} + 2 x_{2}\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107034150>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}12 x_{1}^{2} + 12 x_{1} + 4 & -2\\\\-2 & 2\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1038fd810>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 0\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(0)}=\\left[\\begin{matrix}0.5\\\\0.6\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071885d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.572$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071895d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}2.8\\\\0.2\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107188ed0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}13.0 & -2.0\\\\-2.0 & 2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189a10>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 1\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(1)}=\\left[\\begin{matrix}0.227\\\\0.227\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107110dd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.078$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107191150>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.811\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189d10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}7.35 & -2.0\\\\-2.0 & 2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107191b10>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 2\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(2)}=\\left[\\begin{matrix}0.076\\\\0.076\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071a1450>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.007$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189210>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.187\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071898d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}4.97 & -2.0\\\\-2.0 & 2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189c90>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 3\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(3)}=\\left[\\begin{matrix}0.013\\\\0.013\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071a1790>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071a1bd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.026\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071a1810>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}4.15 & -2.0\\\\-2.0 & 2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071975d0>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 4\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(4)}=\\left[\\begin{matrix}0.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189a90>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189690>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.001\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189fd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}4.01 & -2.0\\\\-2.0 & 2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1038fd810>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 7 | |
| }, | |
| { | |
| "cell_type": "heading", | |
| "level": 1, | |
| "metadata": {}, | |
| "source": [ | |
| "Problem 3" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**Let $f(x) = (x \u2212 x_0)^4$ for $x \\in \\mathbb{R}$, where $x_0 \\in \\mathbb{R}$ is a constant. Suppose that we apply\n", | |
| "Newton\u2019s method to the problem of minimizing $f$.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "---" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(1) Write down the update equation for Newton\u2019s method applied to the problem.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "Suppose $x^{(k)} \\neq x_0$, \n", | |
| "\n", | |
| "$$ f'(x) = 4(x-x_0)^3 $$\n", | |
| "\n", | |
| "$$ f''(x) = 12(x-x_0)^2 $$\n", | |
| "\n", | |
| "Therefore,\n", | |
| "\n", | |
| "$$ x^{(k+1)} = x^{(k)} - \\dfrac{f'(x^{(k)})}{f''(x^{(k)})} = x^{(k)} - \\dfrac{1}{3}(x^{(k)}-x_0) $$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(2) Let $y^{(k)} = \\left|x^{(k)} \u2212 x_0\\right|$, where $x^{(k)}$ is the k-th iterate in Newton\u2019s method. Show that the sequence $\\left\\{y^{(k)}\\right\\}$ satisfies $y^{(k+1)} = \\frac{2}{3} y^{(k)}$.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "As in (1),\n", | |
| "\n", | |
| "$$ x^{(k+1)} = x^{(k)} - \\dfrac{1}{3}(x^{(k)}-x_0) $$\n", | |
| "\n", | |
| "$$ y^{(k+1)} = \\left|x^{(k+1)} - x_0\\right| = \\left|x^{(k)} - \\dfrac{1}{3}(x^{(k)}-x_0) - x_0 \\right|= \\frac{2}{3}\\left|x^{(k)}-x_0 \\right| = \\frac{2}{3} y^{(k)} $$" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(3) Show that $x^{(k)} \\rightarrow x_0$ for any initial guess $x^{(0)}$.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "If $x^{(k)} = x_0$, the case is trivial. \n", | |
| "\n", | |
| "Otherwise, as $\\forall x^{(0)} \\neq x_0$, $\\left\\{y^{(k)}\\right\\} \\rightarrow 0$, then $x^{(k)} \\rightarrow x_0$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(4) Show that the order of convergence of the sequence $\\left\\{x^{(k)}\\right\\}$ in (2) is 1.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "As $$ \\lim_{k \\to \\infty} \\dfrac{\\left\\|x^{(k+1)} - x_0\\right\\|}{\\left\\|x^{(k)} - x_0\\right\\|} = \\dfrac{y^{(k+1)}}{y^{(k+1)}} = \\dfrac{2}{3} $$\n", | |
| "By definition, order of convergence of $\\left\\{x^{(k)}\\right\\}$ is 1." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(5) The theorem (Theorem 9.1 in Ref. [1]) states that under certain conditions, the order of convergence of Newton\u2019s method is at least 2. Why does that the theorem not hold in this particular problem?**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "One precondition for Theorem 9.1 is that the Hessian of $f$ is invertible at $x_0$, which is clearly not satisfied as $f''(x_0) = 0$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "heading", | |
| "level": 1, | |
| "metadata": {}, | |
| "source": [ | |
| "Problem 4" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**Consider the problem of finding minimizer of the function $f(x_1, x_2) = 100(x_2 \u2212 x_1^2)^2 + (1-x_1)^2$.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "---" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(1) Show that $(1, 1)^T$ is the unique global minimizer of $f$ over $\\mathbb{R}^2$.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "x1, x2 = symbols('x_1, x_2')\n", | |
| "x = (x1, x2)\n", | |
| "\n", | |
| "f = Lambda(x, 100*(x2-x1**2)**2 + (1-x1)**2)\n", | |
| "g = Lambda(x, vdiff(f.expr, x))\n", | |
| "F = Lambda(x, Matrix(vdiff(g.expr, x)))\n", | |
| "\n", | |
| "g = Lambda(x, Matrix(g.expr))\n", | |
| "\n", | |
| "print_func(\"f{}\".format(x), f)\n", | |
| "print_func(\"g{}\".format(x), g)\n", | |
| "print_func(\"F{}\".format(x), F)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=\\left(- x_{1} + 1\\right)^{2} + 100 \\left(- x_{1}^{2} + x_{2}\\right)^{2}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107180350>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}400 x_{1} \\left(x_{1}^{2} - x_{2}\\right) + 2 x_{1} - 2\\\\- 200 x_{1}^{2} + 200 x_{2}\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107034110>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}1200 x_{1}^{2} - 400 x_{2} + 2 & - 400 x_{1}\\\\- 400 x_{1} & 200\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107190590>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 8 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "var = (1, 1)\n", | |
| "\n", | |
| "print_func('f{}'.format(var), f(*var))\n", | |
| "print_func('g{}'.format(var), g(*var))\n", | |
| "print_func('F{}'.format(var), F(*var))\n", | |
| "print_func('\\det F{}'.format(var), F(*var).det())\n", | |
| "print_func('trace\\ F{}'.format(var), F(*var).trace())" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(1, 1)=0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10713b910>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(1, 1)=\\left[\\begin{matrix}0\\\\0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10713b990>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(1, 1)=\\left[\\begin{matrix}802 & -400\\\\-400 & 200\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189210>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$\\det F(1, 1)=400$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10713d050>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$trace\\ F(1, 1)=1002$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10719d4d0>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 9 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "solve(g(*x))" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$\\left [ \\left \\{ x_{1} : 1, \\quad x_{2} : 1\\right \\}\\right ]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "pyout", | |
| "png": "iVBORw0KGgoAAAANSUhEUgAAAJwAAAAVBAMAAABBKZpuAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAdt3NMolEZpkQ76tU\nuyIarfQFAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAB/klEQVQ4EWNgAAL2dhBJEXCUhGgXMmHgNKXI\nJIhmLwcGhmI1hjCg4z7gMI55Ag4JNGFLIJ/DAEiEgYxjXQBkYQF894kz7u1PoGZWBSCBzzjOG/uJ\nMm5uN9i4BQSMY2CQJ8o4BkbaGzdR+pmoANC9YMC0AUxhcR2n4L7EQKgqBgZtMAvNddwGDAycAeyK\nTAYMLBfACmYBRYAAi3FTGYoElBlYeztB8pyLQSTEs+DkAY6K8w7AiJnA+pPnAUu3AkgeBrAYF8kQ\nP+EcQxzDZpgaIA12HcNVIAtknPcSIIOTgRnkMB4FIAEHWIybwGALlNZj8H8AVwU1jlsdmlCyHEBS\n/AJAgqBxDAwfgcqWMbxPAFJQAHGdBZAH9iw3OMD8HRgmEGEcyxegTxgYzk+AGYYRdqAEzTNBnoGR\nCONOMn5gkASapIgwDVu6yz9wn+E53LOImOX8jKSPgYHtD+8HvgJgzDWAhJFjlnUBUACeyWYLTgwH\nKoOGHSTdda/XLmDQR/IV0ICNkqLlQH0VQAwE4HTHsevTdmjGhxsHkYYZB+WBKLYHSBwYky2AzQHG\nhtKsC4AMDONAgiiAHYUH5TifOYviaKAw6wIgATYOUd7xNf0WAIoig+nIHBh7/f//MCaMRpR3DPhK\nY2CAEgWyEoDKwhiEVIARIEOUDnyKPCKBskJqAFH0ePgSUjwYAAAAAElFTkSuQmCC\n", | |
| "prompt_number": 10, | |
| "text": [ | |
| "[{x\u2081: 1, x\u2082: 1}]" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 10 | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "However, as $(1, 1)^T$ is the only solution to $g(x_1,x_2) = 0$, and there is no on-interior points in $\\mathbb{R}$, by SONC, there is no other local minimizer. \n", | |
| "\n", | |
| "Therefore, $(1, 1)^T$ is the unique global minimizer of $f$." | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(2) With the starting point $(0, 0)^T$, apply two iterations of Newton\u2019s method (use the inverse formula for a $2\\times 2$ matrix).**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "Newton2D(f, (0., 0.), 2)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=\\left(- x_{1} + 1\\right)^{2} + 100 \\left(- x_{1}^{2} + x_{2}\\right)^{2}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189d50>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}400 x_{1} \\left(x_{1}^{2} - x_{2}\\right) + 2 x_{1} - 2\\\\- 200 x_{1}^{2} + 200 x_{2}\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071885d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}1200 x_{1}^{2} - 400 x_{2} + 2 & - 400 x_{1}\\\\- 400 x_{1} & 200\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107020f50>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 0\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(0)}=\\left[\\begin{matrix}0.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10719acd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=1.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10712d550>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}-2.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107187550>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}2.0 & 0.0\\\\0.0 & 200.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10713b2d0>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 1\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(1)}=\\left[\\begin{matrix}1.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10712d690>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=100.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10719ae10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}400.0\\\\-200.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10712d490>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}1202.0 & -400.0\\\\-400.0 & 200.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189250>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 2\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(2)}=\\left[\\begin{matrix}1.0\\\\1.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107190ad0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107020b50>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107190b90>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}802.0 & -400.0\\\\-400.0 & 200.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071d4910>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 11 | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "**(3) Repeat part (2) using a gradient algorithm with a fixed step size of $\\alpha_k = 0.05$ at each iteration.**" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "def Gradient(f, x0, alpha, n_iter):\n", | |
| " g = Lambda(x, vdiff(f.expr, x))\n", | |
| " F = Lambda(x, Matrix(vdiff(g.expr, x)))\n", | |
| " \n", | |
| " g = Lambda(x, Matrix(g.expr))\n", | |
| " \n", | |
| " print_func(\"f{}\".format(x), f)\n", | |
| " print_func(\"g{}\".format(x), g)\n", | |
| " print_func(\"F{}\".format(x), F)\n", | |
| " \n", | |
| " xk = Matrix(x0)\n", | |
| " for k in range(n_iter+1):\n", | |
| " print\n", | |
| " print 'Iter {}'.format(k)\n", | |
| " print_func('x^{{({})}}'.format(k), \n", | |
| " Matrix(np.round(np.array(xk).astype(np.float), 3).squeeze()))\n", | |
| " print_func('f{}'.format(x), \n", | |
| " np.round(np.array(f(*xk)).astype(np.float), 3))\n", | |
| " print_func('g{}'.format(x), \n", | |
| " Matrix(np.round(np.array(g(*xk)).astype(np.float), 3).squeeze()))\n", | |
| " x_temp = xk - alpha * g(*xk)\n", | |
| " xk = x_temp\n", | |
| " \n", | |
| "Gradient(f, (0., 0.), 0.05, 2)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=\\left(- x_{1} + 1\\right)^{2} + 100 \\left(- x_{1}^{2} + x_{2}\\right)^{2}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107034090>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}400 x_{1} \\left(x_{1}^{2} - x_{2}\\right) + 2 x_{1} - 2\\\\- 200 x_{1}^{2} + 200 x_{2}\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107189bd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$F(x_1, x_2)=\\left[\\begin{matrix}1200 x_{1}^{2} - 400 x_{2} + 2 & - 400 x_{1}\\\\- 400 x_{1} & 200\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10719ac90>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 0\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(0)}=\\left[\\begin{matrix}0.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3190>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=1.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3d50>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}-2.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3a10>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 1\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(1)}=\\left[\\begin{matrix}0.1\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071e3a10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=0.82$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071e3ed0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}-1.4\\\\-2.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071e3b50>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 2\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(2)}=\\left[\\begin{matrix}0.17\\\\0.1\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071e3550>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=1.194$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3a10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}-6.495\\\\14.22\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071e3390>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 12 | |
| }, | |
| { | |
| "cell_type": "heading", | |
| "level": 1, | |
| "metadata": {}, | |
| "source": [ | |
| "Problem 5" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "x1, x2 = symbols('x_1, x_2')\n", | |
| "x = (x1, x2)\n", | |
| "f = Lambda(x, x1 + x2/2 + x1**2/2 + x2**2 + 3)\n", | |
| "\n", | |
| "print_func(\"f{}\".format(x), f)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=\\frac{x_{1}^{2}}{2} + x_{1} + x_{2}^{2} + \\frac{x_{2}}{2} + 3$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071885d0>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 13 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "def SteepestDescent(f, x0, n_iter):\n", | |
| " g = Lambda(x, Matrix(vdiff(f.expr, x)))\n", | |
| " alpha = Symbol('\u03b1')\n", | |
| " \n", | |
| " print_func(\"f{}\".format(x), f)\n", | |
| " print_func(\"g{}\".format(x), g)\n", | |
| " \n", | |
| " xk = Matrix(x0)\n", | |
| " for k in range(n_iter+1):\n", | |
| " print\n", | |
| " print 'Iter {}'.format(k)\n", | |
| " print_func('x^{{({})}}'.format(k), \n", | |
| " Matrix(np.round(np.array(xk).astype(np.float), 3).squeeze()))\n", | |
| " print_func('f{}'.format(x), \n", | |
| " np.round(np.array(f(*xk)).astype(np.float), 3))\n", | |
| " print_func('g{}'.format(x), \n", | |
| " Matrix(np.round(np.array(g(*xk)).astype(np.float), 3).squeeze()))\n", | |
| " \n", | |
| " # Line search on \u03b1 for the steepest step size\n", | |
| " x_temp = Lambda((alpha), xk - alpha * g(*xk))\n", | |
| " a, = solve(vdiff(f(*x_temp(alpha)), alpha))\n", | |
| " \n", | |
| " print_func('f_{\u03b1}', f(*x_temp(alpha)).simplify())\n", | |
| " print_func('\u03b1_{optimal}', np.round(float(a), 3))\n", | |
| " \n", | |
| " xk = x_temp(a)\n", | |
| " \n", | |
| "SteepestDescent(f, (0, 0), 2)" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=\\frac{x_{1}^{2}}{2} + x_{1} + x_{2}^{2} + \\frac{x_{2}}{2} + 3$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107147cd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}x_{1} + 1\\\\2 x_{2} + \\frac{1}{2}\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107110a90>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 0\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(0)}=\\left[\\begin{matrix}0.0\\\\0.0\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f33d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=3.0$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3b10>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}1.0\\\\0.5\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3e90>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f_{\u03b1}=\\frac{3 \u03b1^{2}}{4} - \\frac{5 \u03b1}{4} + 3$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3a90>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$\u03b1_{optimal}=0.833$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107147bd0>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 1\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(1)}=\\left[\\begin{matrix}-0.833\\\\-0.417\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071ea0d0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=2.479$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071ea390>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.167\\\\-0.333\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071ea690>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f_{\u03b1}=\\frac{\u03b1^{2}}{8} - \\frac{5 \u03b1}{36} + \\frac{119}{48}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10712d350>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$\u03b1_{optimal}=0.556$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x10713b7d0>" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "stream": "stdout", | |
| "text": [ | |
| "\n", | |
| "Iter 2\n" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$x^{(2)}=\\left[\\begin{matrix}-0.926\\\\-0.231\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3a90>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f(x_1, x_2)=2.441$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3450>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$g(x_1, x_2)=\\left[\\begin{matrix}0.074\\\\0.037\\end{matrix}\\right]$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071f3ed0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$f_{\u03b1}=\\frac{\u03b1^{2}}{243} - \\frac{5 \u03b1}{729} + \\frac{3163}{1296}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x107147cd0>" | |
| ] | |
| }, | |
| { | |
| "latex": [ | |
| "$$\u03b1_{optimal}=0.833$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "display_data", | |
| "text": [ | |
| "<IPython.core.display.Latex at 0x1071d4650>" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 14 | |
| }, | |
| { | |
| "cell_type": "code", | |
| "collapsed": false, | |
| "input": [ | |
| "g = Lambda(x, Matrix(vdiff(f.expr, x)))\n", | |
| "solve(g(*x))" | |
| ], | |
| "language": "python", | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "latex": [ | |
| "$$\\left \\{ x_{1} : -1, \\quad x_{2} : - \\frac{1}{4}\\right \\}$$" | |
| ], | |
| "metadata": {}, | |
| "output_type": "pyout", | |
| "png": "iVBORw0KGgoAAAANSUhEUgAAAL8AAAAyBAMAAAD/6hczAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAEJlUzSJmiTKrRN3v\ndrsdCiq5AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAC20lEQVRYCe1Wz2vTUBz/pmma/m4Yosicq8eB\noCKC4A4VL4IgwYMHB2sO6sXD6g6elBXx7OpBYehobwoiQ9hlFJnCLnoxOw3B0bh/oJ1OWRVX3/vm\nJU2XNN3aPLzse/j+fp9P8vJ9SQCIDGWpDlomKxaiuKVabpA2sqMwuKlCkLgU6yICTrw1caNN0wan\nJzcRS2LAMTMMDv/4GEM8VUTQTC44bBMpxQgWNIxHS7wI8lnOBOzS+d3BAUHX2bCm6GCL/tsWhV78\neeY8Yb3PQdh673a9Zu/CXh+yVOdLIGyUByOYLXjfYDtb65MgYyDGVKUN5e31SxB+j3hVqoX1p28e\nYEjVku2h40Ew8uXGmm51JUqW12nFXzSWf1J9BO7oiwCPqQ/CChpbuQmEQuRdIgfTG7h5x3J2a6dT\nVkl8v0KTd2FGOQcPn1PfJW4CWZE3RVVWYzlXszMR+wQw/AQzClyl9oKjLFypElksArgJBAgbAAk1\nirdvLjpE26uXIdOiYubGdRg+Ybrwl1onAcsT4yYAyOgAyYr0u93l5b0mXSeLWIlug7AfgtkiKACi\n/x9JiGwRhLYpwZlUA1b3TiAqNUgRggS5Qh+ZKdIiGR6I/0g3JM0i8JgiYYu22rJwug7XSTSNmW5T\nFMdth1qFDOb86tpt0syeQec5GPu8pMEyud62HF0fuacBRLKY6nYO0g0s5wtoUHk/ZFqKq+0u23sJ\nr2zf6USzGLFfulEzwtQ4ai8V8UhGL5395pEmj8bAtPt1fW153nMBSR72KCRbLXMTdte+GphxE+xu\ndMSaw+/lSjcNbNkXQS9QZ12mx5wIN4JbnAkEnTOBjG9Cjlt0njOBUOBMIM7NlT/qXKcIkgbF5zem\nwP5X2EuIHQfkDEbJ9aZGkfJZqiGZQ8NBsV+6tP9nbwBi84MG0vcBMPyWCjusWsOZ8mvtrzbxga2L\nNJX+EPxXiSs27FDJv7W/6iONrvsHsVvCB2UUts0AAAAASUVORK5CYII=\n", | |
| "prompt_number": 15, | |
| "text": [ | |
| "{x\u2081: -1, x\u2082: -1/4}" | |
| ] | |
| } | |
| ], | |
| "prompt_number": 15 | |
| } | |
| ], | |
| "metadata": {} | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment