{ "cells": [ { "cell_type": "markdown", "id": "686c2d28", "metadata": {}, "source": [ "\n", "*This notebook contains material from [CBE60499](https://ndcbe.github.io/CBE60499);\n", "content is available [on Github](git@github.com:ndcbe/CBE60499.git).*\n" ] }, { "cell_type": "markdown", "id": "47d768ee", "metadata": {}, "source": [ "\n", "< [3.6 Descent and Globalization](https://ndcbe.github.io/CBE60499/03.06-Globalization.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [3.8 Algorithms Homework 2](https://ndcbe.github.io/CBE60499/03.08-Algorithms2.html) >

\"Open

\"Download\"" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 1, "link": "[3.7 Algorithms Homework 1](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7-Algorithms-Homework-1)", "section": "3.7 Algorithms Homework 1" } }, "source": [ "# 3.7 Algorithms Homework 1" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "nbpages": { "level": 1, "link": "[3.7 Algorithms Homework 1](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7-Algorithms-Homework-1)", "section": "3.7 Algorithms Homework 1" } }, "outputs": [], "source": [ "# Load required Python libraries.\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "from scipy import linalg" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[3.7.1 Linear Algebra Review](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1-Linear-Algebra-Review)", "section": "3.7.1 Linear Algebra Review" } }, "source": [ "## 3.7.1 Linear Algebra Review" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.1 Exact solution](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.1-Exact-solution)", "section": "3.7.1.1 Exact solution" }, "tags": [ "gradescope" ] }, "source": [ "### 3.7.1.1 Exact solution" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.1 Exact solution](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.1-Exact-solution)", "section": "3.7.1.1 Exact solution" } }, "source": [ "Solve the following system of linear equations BY HAND with exact arithmetic:\n", "\n", "$$3 x_1 + 2 x_2 + x_3 = 6$$\n", "$$-x_1 + 4 x_2 + 5x_3 = 8$$\n", "$$2x_1 -8 x_2 + 10 x_3 = 4$$\n", "\n", "Turn in your work via Gradescope." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.2 Solve using the inverse](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.2-Solve-using-the-inverse)", "section": "3.7.1.2 Solve using the inverse" } }, "source": [ "### 3.7.1.2 Solve using the inverse\n", "\n", "Solve the same linear system by first inverting the matrix A and performing matrix multiplication. You should use Python and SciPy.\n", "* Tutorials and documentation: https://docs.scipy.org/doc/scipy-1.1.0/reference/tutorial/linalg.html" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.2 Solve using the inverse](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.2-Solve-using-the-inverse)", "section": "3.7.1.2 Solve using the inverse" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A = \n", " [[ 3 2 1]\n", " [-1 4 5]\n", " [ 2 -8 10]]\n", "\n", "b = \n", " [6 8 4]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.2 Solve using the inverse](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.2-Solve-using-the-inverse)", "section": "3.7.1.2 Solve using the inverse" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 2.85714286e-01 -1.00000000e-01 2.14285714e-02]\n", " [ 7.14285714e-02 1.00000000e-01 -5.71428571e-02]\n", " [ 4.62592927e-19 1.00000000e-01 5.00000000e-02]]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.2 Solve using the inverse](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.2-Solve-using-the-inverse)", "section": "3.7.1.2 Solve using the inverse" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1. 1. 1.]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.3 Solve using LU decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.3-Solve-using-LU-decomposition)", "section": "3.7.1.3 Solve using LU decomposition" } }, "source": [ "### 3.7.1.3 Solve using LU decomposition\n", "\n", "Do the following:\n", "1. Use ``linalg.lu(A)`` to calculate $P$, $L$, and $U$.\n", "2. Write a function to solve any linear system given the factorization and $b$. You may not use ```linalg.solve``` in your function. Instead, you should write loops to implement back substitution.\n", "3. Use your function to solve the linear system.\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.3 Solve using LU decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.3-Solve-using-LU-decomposition)", "section": "3.7.1.3 Solve using LU decomposition" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1. 0. 0.]\n", " [0. 0. 1.]\n", " [0. 1. 0.]]\n", "[[ 1. 0. 0. ]\n", " [ 0.66666667 1. 0. ]\n", " [-0.33333333 -0.5 1. ]]\n", "[[ 3. 2. 1. ]\n", " [ 0. -9.33333333 9.33333333]\n", " [ 0. 0. 10. ]]\n" ] } ], "source": [ "# You need to define the matrix A1 somewhere (or change the variable name)\n", "P, L, U = linalg.lu(A1)\n", "\n", "# Permutation matrix\n", "print(P)\n", "\n", "# Lower diagonal matrix\n", "print(L)\n", "\n", "# Upper diagonal matrix\n", "print(U)" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.3 Solve using LU decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.3-Solve-using-LU-decomposition)", "section": "3.7.1.3 Solve using LU decomposition" } }, "source": [ "Tip: We discussed this algorithm in class. First write pseudocode on paper (how to translate our notes into loops, logical statements, etc.?). Once you are happy with the logic, code it up." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.3 Solve using LU decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.3-Solve-using-LU-decomposition)", "section": "3.7.1.3 Solve using LU decomposition" } }, "outputs": [], "source": [ "# Write function here.\n", "def my_lu_solve(P, L, U, b, LOUD=True):\n", " ''' \n", " Solves linear system Ax = b given PLU decomposition of A\n", " \n", " Arguments:\n", " P - N by N permutation matrix\n", " L - N by N lower triangular matrix with 1 on diagonal\n", " U - N by N upper triangular matrix\n", " b - N by 1 vector\n", " \n", " Returns:\n", " x - N by 1 solution to linear system\n", " '''\n", " \n", " # Define x so this does not give an error. You can delete the line below.\n", " x = []\n", " \n", " # YOUR SOLUTION HERE\n", " \n", " return x" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.3 Solve using LU decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.3-Solve-using-LU-decomposition)", "section": "3.7.1.3 Solve using LU decomposition" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Forward solve...\n", "y[ 0 ]= 6.0\n", "y[ 1 ]= 0.0\n", "y[ 2 ]= 10.0\n", "\n", "Backward solve...\n", "x[ 2 ]= 1.0\n", "x[ 1 ]= 1.0\n", "x[ 0 ]= 1.0\n" ] } ], "source": [ "x = my_lu_solve(P, L, U, b, LOUD=True)" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.4 Solve using `linalg.solve`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.4-Solve-using-`linalg.solve`)", "section": "3.7.1.4 Solve using `linalg.solve`" } }, "source": [ "### 3.7.1.4 Solve using `linalg.solve`\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "nbpages": { "level": 3, "link": "[3.7.1.4 Solve using `linalg.solve`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.1.4-Solve-using-`linalg.solve`)", "section": "3.7.1.4 Solve using `linalg.solve`" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x = [1. 1. 1.]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[3.7.2 Eigenvalues](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2-Eigenvalues)", "section": "3.7.2 Eigenvalues" } }, "source": [ "## 3.7.2 Eigenvalues" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.1 Calculate eigenvalues by hand (on paper)](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.1-Calculate-eigenvalues-by-hand-(on-paper))", "section": "3.7.2.1 Calculate eigenvalues by hand (on paper)" }, "tags": [ "gradescope" ] }, "source": [ "### 3.7.2.1 Calculate eigenvalues by hand (on paper)" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.1 Calculate eigenvalues by hand (on paper)](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.1-Calculate-eigenvalues-by-hand-(on-paper))", "section": "3.7.2.1 Calculate eigenvalues by hand (on paper)" } }, "source": [ "Calculate the eigenvalues for the following matrix:\n", "\n", "$$\n", "A = \\begin{bmatrix} 0 & -4 & -6 \\\\ -1 & 0 & -3 \\\\ 1 & 2 & 5 \\end{bmatrix}\n", "$$\n", "\n", "You may need to do this for a small system on an exam to characterize stationary points of an optimization problem. Hence I would like you to practice at least once on the homework." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.2 Calculate eigenvalues using `linalg.eig`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.2-Calculate-eigenvalues-using-`linalg.eig`)", "section": "3.7.2.2 Calculate eigenvalues using `linalg.eig`" } }, "source": [ "### 3.7.2.2 Calculate eigenvalues using `linalg.eig`\n", "\n", "Calculate the eigenvalues and corresponding (right) eigenvectors." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.2 Calculate eigenvalues using `linalg.eig`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.2-Calculate-eigenvalues-using-`linalg.eig`)", "section": "3.7.2.2 Calculate eigenvalues using `linalg.eig`" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A2 = \n", " [[ 0 -4 -6]\n", " [-1 0 -3]\n", " [ 1 2 5]]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.2 Calculate eigenvalues using `linalg.eig`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.2-Calculate-eigenvalues-using-`linalg.eig`)", "section": "3.7.2.2 Calculate eigenvalues using `linalg.eig`" }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Eigenvalues = [1.+0.00000000e+00j 2.+1.63168795e-15j 2.-1.63168795e-15j]\n", "Eigenvectors = \n", "[[-0.81649658+0.j -0.77616123+0.j -0.77616123-0.j ]\n", " [-0.40824829+0.j -0.26081756-0.31398875j -0.26081756+0.31398875j]\n", " [ 0.40824829+0.j 0.43259879+0.20932583j 0.43259879-0.20932583j]]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.3 Definiteness](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.3-Definiteness)", "section": "3.7.2.3 Definiteness" }, "tags": [ "gradescope" ] }, "source": [ "### 3.7.2.3 Definiteness" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.3 Definiteness](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.3-Definiteness)", "section": "3.7.2.3 Definiteness" } }, "source": [ "Based on your calculations above, is this matrix\n", "1. positive definite\n", "2. positive semi definite\n", "3. negative definite\n", "4. negative semi definite\n", "5. indefinite or\n", "6. cannot say without additional calculations?\n", "\n", "Briefly comment to justify your answer.\n", "\n", "*Note*: In this class, \"briefly comment\" means write a few sentences, sketch a picture, write an equation or some combination... whichever you feel is necessary to succinctly provide justification." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.4 Singular Value Decomposition](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.4-Singular-Value-Decomposition)", "section": "3.7.2.4 Singular Value Decomposition" } }, "source": [ "### 3.7.2.4 Singular Value Decomposition\n", "\n", "**TODO:** Make this a separate problem (after the assignment is turned in this year)." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.5 SVD calculation using `linalg.svd`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.5-SVD-calculation-using-`linalg.svd`)", "section": "3.7.2.5 SVD calculation using `linalg.svd`" } }, "source": [ "### 3.7.2.5 SVD calculation using `linalg.svd`\n", "\n", "Calculate the singular value decomposition of the following matrix using `linalg.svd`:\n", "\n", "$$\n", "A_3 = \\begin{bmatrix} 1 & 2 & 0 & -1 \\\\ 2 & 4 & 10^{-6} & -2 \\\\ 0 & 2 & -1 & 10^{-3} \\end{bmatrix}\n", "$$" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.5 SVD calculation using `linalg.svd`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.5-SVD-calculation-using-`linalg.svd`)", "section": "3.7.2.5 SVD calculation using `linalg.svd`" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A = \n", " [[ 1.e+00 2.e+00 0.e+00 -1.e+00]\n", " [ 2.e+00 4.e+00 1.e-06 -2.e+00]\n", " [ 0.e+00 2.e+00 -1.e+00 1.e-03]]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.5 SVD calculation using `linalg.svd`](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.5-SVD-calculation-using-`linalg.svd`)", "section": "3.7.2.5 SVD calculation using `linalg.svd`" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "U = \n", " [[-4.25830830e-01 -1.36631105e-01 -8.94427217e-01]\n", " [-8.51661650e-01 -2.73262656e-01 4.47213544e-01]\n", " [-3.05516837e-01 9.52186674e-01 1.91553449e-07]]\n", "S = \n", " [5.73316009e+00 1.45975216e+00 3.38134101e-07]\n", "Vh = \n", " [[-3.71375314e-01 -8.49329490e-01 5.32892822e-02 3.71322025e-01]\n", " [-4.67994798e-01 3.68597169e-01 -6.52293569e-01 4.68647091e-01]\n", " [-3.77573248e-01 3.77856348e-01 7.56090836e-01 3.78139751e-01]\n", " [ 7.07460026e-01 -3.53377112e-04 -9.52352187e-10 7.06753272e-01]]\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.6 Condition number](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.6-Condition-number)", "section": "3.7.2.6 Condition number" } }, "source": [ "### 3.7.2.6 Condition number\n", "What is the condition number of the matrix? Calculate it two ways:\n", "1. Using SVD results\n", "2. Using ``np.linalg.cond()``" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.6 Condition number](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.6-Condition-number)", "section": "3.7.2.6 Condition number" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Condition number = 16955285.123025477\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.6 Condition number](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.6-Condition-number)", "section": "3.7.2.6 Condition number" }, "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Condition number = 16955285.123025477\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.7 Linear system](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.7-Linear-system)", "section": "3.7.2.7 Linear system" } }, "source": [ "### 3.7.2.7 Linear system" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.7 Linear system](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.7-Linear-system)", "section": "3.7.2.7 Linear system" } }, "source": [ "Consider the linear system $A_4 \\cdot x = b$ with $b = [1, 0, 3]^T$ and\n", "\n", "$$\n", "A_4 = \\begin{bmatrix} 1 & 2 & 0 \\\\ 2 & 4 & 10^{-1} \\\\ 0 & 2 & -1 \\end{bmatrix} ~.\n", "$$\n", "\n", "Approximately how much uncertainty $||\\Delta b||_2$ can you tolerate if you want the uncertainty $||\\Delta x||_2$ to be less than $10^{-2}$?\n" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.7 Linear system](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.7-Linear-system)", "section": "3.7.2.7 Linear system" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Condition number = 181.90540228772272\n" ] } ], "source": [ "# YOUR SOLUTION HERE" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.7 Linear system](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.7-Linear-system)", "section": "3.7.2.7 Linear system" } }, "source": [ "**Answer**:" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.8 Make it singular](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.8-Make-it-singular)", "section": "3.7.2.8 Make it singular" } }, "source": [ "### 3.7.2.8 Make it singular\n" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.8 Make it singular](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.8-Make-it-singular)", "section": "3.7.2.8 Make it singular" } }, "source": [ "Do/answer the following:\n", "1. Propose a change to a single entry in $A_4$ to make it singular.\n", "2. What are the singular values and condition number after this change?\n", "3. What can you say about the solution to $A_4 \\cdot x=b$ after the change?" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.2.8 Make it singular](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.2.8-Make-it-singular)", "section": "3.7.2.8 Make it singular" } }, "source": [ "**Answer:**" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[3.7.3 Convexity](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3-Convexity)", "section": "3.7.3 Convexity" }, "tags": [ "gradescope" ] }, "source": [ "## 3.7.3 Convexity\n", "\n", "Please turn in via Gradescope." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.3.1 Determine if the following functions are convex](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.1-Determine-if-the-following-functions-are-convex)", "section": "3.7.3.1 Determine if the following functions are convex" } }, "source": [ "### 3.7.3.1 Determine if the following functions are convex" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.3.1 Determine if the following functions are convex](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.1-Determine-if-the-following-functions-are-convex)", "section": "3.7.3.1 Determine if the following functions are convex" } }, "source": [ "1. $x^2 + ax + b, ~x \\in \\mathbb{R}$\n", "2. $x^3, ~x \\in \\mathbb{R}$\n", "3. $| x |, ~ x \\in [ -5, 5]$\n", "4. $x + y, ~ x \\in \\mathbb{R}, ~ y \\in \\mathbb{R}$\n", "5. $x \\cdot y, ~ x \\in \\mathbb{R}, ~ y \\in \\mathbb{R}$\n", "6. $\\log(x), ~ x \\in (0,1]$" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.3.2 Prove the following properties](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2-Prove-the-following-properties)", "section": "3.7.3.2 Prove the following properties" } }, "source": [ "### 3.7.3.2 Prove the following properties" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 3, "link": "[3.7.3.2 Prove the following properties](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2-Prove-the-following-properties)", "section": "3.7.3.2 Prove the following properties" } }, "source": [ "Consider twice differentiable function $f(x): \\mathbb{R}^n \\rightarrow \\mathbb{R}$.\n", "\n", "Recall that $f(x)$ is convex on $x \\in \\mathbb{R}^n$ if and only if\n", "\n", "$f(x+p) \\geq f(x) + \\nabla f(x)^T p$ for all $x, p \\in \\mathbb{R}^n$\n" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 4, "link": "[3.7.3.2.1 PSD implies Convexity](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2.1-PSD-implies-Convexity)", "section": "3.7.3.2.1 PSD implies Convexity" } }, "source": [ "#### 3.7.3.2.1 PSD implies Convexity\n", "\n", "Prove that if $\\nabla^2 f(x)$ is positive semidefinite for all $x \\in \\mathbb{R}^n$, then $f(x)$ must be convex.\n" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 4, "link": "[3.7.3.2.2 Convexity implies PSD](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2.2-Convexity-implies-PSD)", "section": "3.7.3.2.2 Convexity implies PSD" } }, "source": [ "#### 3.7.3.2.2 Convexity implies PSD" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 4, "link": "[3.7.3.2.2 Convexity implies PSD](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2.2-Convexity-implies-PSD)", "section": "3.7.3.2.2 Convexity implies PSD" } }, "source": [ "Prove that if $f(x)$ is convex then $\\nabla^2 f(x)$ must be positive semidefinite." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 4, "link": "[3.7.3.2.3 PD implies Strictly Convex](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2.3-PD-implies-Strictly-Convex)", "section": "3.7.3.2.3 PD implies Strictly Convex" } }, "source": [ "#### 3.7.3.2.3 PD implies Strictly Convex" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 4, "link": "[3.7.3.2.3 PD implies Strictly Convex](https://ndcbe.github.io/CBE60499/03.07-Algorithms1.html#3.7.3.2.3-PD-implies-Strictly-Convex)", "section": "3.7.3.2.3 PD implies Strictly Convex" } }, "source": [ "Prove that if $\\nabla^2 f(x)$ is positive definite for all $x \\in \\mathbb{R}^n$, then $f(x)$ must be strictly convex." ] }, { "cell_type": "markdown", "id": "75f56236", "metadata": {}, "source": [ "\n", "< [3.6 Descent and Globalization](https://ndcbe.github.io/CBE60499/03.06-Globalization.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [3.8 Algorithms Homework 2](https://ndcbe.github.io/CBE60499/03.08-Algorithms2.html) >

\"Open

\"Download\"" ] } ], "metadata": { "celltoolbar": "Tags", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }