\documentclass[11pt]{article} \usepackage{verbatim} \usepackage{amsmath,amsfonts} \usepackage[mathscr]{eucal} \usepackage{amssymb,amsmath} \usepackage{latexsym} \usepackage{amsfonts} \usepackage{amscd} \usepackage{amsthm} \newcommand {\C}{\mathbb {C}} \newcommand {\R}{\mathbb {R}} \newcommand {\T}{\mathbb {T}} \newcommand {\D}{\mathcal {D}} \newcommand {\I}{\mathcal {I}} \newcommand {\G}{\mathcal {G}} \newcommand {\N}{\mathcal {N}} \newcommand {\Z}{\mathbb {Z}} \topmargin=-0.20in \textheight=8.5in \textwidth=6.5in \oddsidemargin=-0.10in \begin{document} \noindent{\bf Math 273} \noindent{\bf Homework \#4, due on Wednesday, November 25, or on Monday, November 30} \bigbreak \noindent{\bf [1]} Consider the quadratic program $$\min_{x} q(x)=\frac{1}{2}x^T G x+x^Td,\mbox{ subject to } Ax=b,$$ where $G\in\R^{n\times n}$ is a symmetric matrix, $A\in \R^{m\times n}$. Assume that $A$ has full row rank $m$. (a) Express the first order necessary conditions for $x_*$ to be a solution in the form of a linear matrix equation in the unknown $(x_*\ \ \lambda^*)^T$. (b) Express in (a) $x_*$ by $x+p$, with $x$ some fixed feasible estimate and unknown $p\in Null(A)$. Re-write the matrix equation now in the unknown $(-p\ \ \lambda^*)^T$. (c) Assume in addition that the reduced-Hessian $Z^T G Z$ is positive definite. Show that the coefficient matrix in (b) is non-singular, thus there is a unique vector pair $(x_*,\lambda^*)$ satisfying the matrix equation in (a). \medbreak \noindent{\bf [2]} Show that $(0,-1)^T$ is a local minimizer for the problem Minimize \ $f(x)=2x_1^2+x_2$ \ subject to $x_2\geq x_1^2-1$ $x_1\geq x_2$. \medbreak \noindent{\bf [3]} The problem of finding the shortest distance from a point $x_0$ to the hyperplane $\{x:\ Ax=b\}$ where $A$ has full row rank can be formulated as the quadratic program $$\min \frac{1}{2}(x-x_0)^T(x-x_0),\ \ \mbox{ s.t. } Ax=b.$$ (i) Show that the optimal multiplier is $\lambda^*=(AA^T)^{-1}(b-Ax_0)$, and that the solution is $x_*=x_0+A^T(AA^T)^{-1}(b-Ax_0)$. (ii) Show that in the special case where $A$ is a row vector, the shortest distance from $x_0$ to the solution set of $Ax=b$ is $\frac{|b-Ax_0|}{\|A\|}$. \medbreak \noindent{\bf [4]} Repeat problem [3], Hw \#3 using now Newton's method, and compare the two methods. Give details about your implementation (computation of gradient, of Hessian, of inverse, about $\alpha$, about your stopping criteria, etc), and include your code. \medbreak \noindent{\bf [5]} Let $V$ be a real vector space and $F:V\rightarrow \overline{\R}$ be a convex function, thus for every $u,v\in {\cal V}$, we have $F(\lambda u+(1-\lambda)v)\leq \lambda F(u)+(1-\lambda)F(v)$, $\forall\lambda\in [0,1]$, whenever the RHS is defined (the RHS is not defined when $F(u)=-F(v)=+\infty$ or $F(u)=-F(v)=-\infty$). (a) If $F$ is convex, show that for every $u_1,...,u_n$ of points of $V$ and for every family $\lambda_1,...,\lambda_n$, $\lambda_i\geq0$, $\sum_{i=1}^n\lambda_i=1$, we have $$F(\sum_{i=1}^n\lambda_i u_i)\leq\sum_{i=1}^n\lambda_iF(u_i).$$ (b) If $F:V\rightarrow \overline{\R}$ is convex, show that the sections $\{u:\ F(u)\leq a\}$ and $\{u: \ F(u)