\hfill \thepage} %} \input{tcilatex} \begin{document} \vspace{1pt}Introduction to Non-linear optimization Based on Chong/Zak Chapter 6, ``Basics of Unconstrained Optimization'' Author: Robert Beezer History: 1999/03/15\qquad First version. \vspace{1pt} \begin{enumerate} \item Basic problem statement: \ Let \ $x=(x_{1},x_{2},\ldots ,x_{n})$ \ be a vector. minimize $f(x)$ subject to \ $x\in \Omega $ Variants: \begin{enumerate} \item \ \ $\Omega $ \ is an intersection of ``halfspaces'' and \ $f(x)$ \ is linear. \ This is linear programming. \item $\ \ \Omega $ \ is all of \ $R^{n}$ , this is ``unconstrained'' optimization. \item $\ \ \Omega =\{x\mid h(x)=0,g(x)\geq 0\}$ , \ \ this is ``constrained'' optimization. \ \ Do this later.\bigskip \end{enumerate} \item Minimizers: \begin{enumerate} \item Local: \ $x^{\ast }$ \ is a local minimizer if there exists an \ $% \epsilon >0$ \ so that \ $f(x)\geq f(x^{\ast })$ \ for all \ $x$ \ such that \ \ $x\in \Omega $ \ and \ $0\leq \Vert x-x^{\ast }\Vert \leq $\ $\epsilon $. \item Global: \ $x^{\ast }$ \ is a global minimizer if \ $f(x)\geq f(x^{\ast })$ \ for all\ \ $x\in \Omega ,$ $\ x\neq x^{\ast }$. \item Strict versus `` \ ''. \ (no equality in the first instance, explains $\neq $ \ in above) \item Pictures: \ $R^{1},R^{2}$ \ local vs global, none of various types, etc.\bigskip \end{enumerate} \item Derivative analogs? \begin{enumerate} \item Define gradient as \ $Df=\nabla f(x)$ \ to be vector of first derivatives. \item Hessian as \ $F(x)=D^{2}f(x)$ \ as matrix of second partial derivatives. \item Example: \ $f(x_{1},x_{2},x_{3})=x_{1}x_{3}+x_{2}^{2}x_{3}^{4}$ \ to illustrate both.\bigskip \end{enumerate} \item Directional derivatives. \begin{enumerate} \item A feasible direction \ is a vector that points into a set: \ i.e. $d\neq 0$ is feasible at \ $x\in \Omega $ \ there exists an $\alpha _{0}>0$ \ so that \ \ $x+\alpha d\in \Omega $ \ for all \ $0\leq \alpha \leq \alpha _{0}$. \item Example: \ Picture such a direction on a blobular 3-D picture. \item Directional derivative: \ \[ \frac{\partial f}{\partial d}(x)=\lim_{\alpha \rightarrow 0}\frac{f(x+\alpha d)-f(x)}{\alpha } \] \item Fact: \ \[ \frac{\partial f}{\partial d}(x)=d^{t}\nabla f(x) \] \item So if \ $\Vert d\Vert =1$,, i.e \ $d$ \ is a unit vector, this is the rate of increase of \ $f$ \ in the direction of \ $d.$ \item Example: \ $f(x_{1},x_{2},x_{3})=x_{1}x_{3}+x_{2}^{2}x_{3}^{4}$, \ $% \Omega =\{x\mid x_{1}^{2}+x_{2}^{2}+x_{3}^{2}\leq 14\}$, \ \ $x=(2,3,-1)$ \ (right on boundary), $d=(-2,-3,1)$ \ is feasible as it points right at the center. \ Then \[ \frac{\partial f}{\partial d}(x)=(-2,-3,1)\cdot (-1,6,-34)=-50 \] and when scaled down by $\Vert d\Vert $ \ we get $\frac{50}{\sqrt{14}}$. \end{enumerate} \item Conditions that must be satisfied by extremes: \begin{enumerate} \item First order necessary condition (FONC): \ If \ $x^{\ast }$ \ is a local minimizer of \ $\ f$, \ then \[ \frac{\partial f}{\partial d}(x^{\ast })=d^{t}\nabla f(x^{\ast })\geq 0 \] \ for every feasible direction $\ d$ \ at \ $x^{\ast }$. \item Observe that at an interior point \emph{all }directions are feasible. \item Second order necessary condition (SONC): \ \ If \ $x^{\ast }$ \ is a local minimizer of \ $\ f$, \ $d$ \ is a feasible direction at \ $x^{\ast }$% , \ and $\frac{\partial f}{\partial d}(x^{\ast })=d^{t}\nabla f(x^{\ast })=0$% , \ then \[ d^{t}F(x^{\ast })d\geq 0\text{.} \] \item Stress the use of these equations for \emph{searching} for possible minimizers. \item Example: \ (Chong/Zak Example 6.5) \ $% f(x_{1},x_{2})=x_{1}^{2}-x_{2}^{2}$. \ Has a FONC point at the origin - this is only possible local minimizer (and thus only possible lobal minimizer). \ However, the Hessian is$\left( \begin{array}{ll} 2 & 0 \\ 0 & -2 \end{array} \right) $at all points, and particularly at the origin. \ It is ``indefinite'' \ (foreshadow positive definite matrices here), as can be seen with \ $(1,0)$ \ and \ $(0,1)$.\bigskip \end{enumerate} \item Sufficient condition for a local minimizer: \begin{enumerate} \item Second order sufficient condition (SOSC) - interior case: \ \ Suppose that $\ \ \frac{\partial f}{\partial d}(x^{\ast })=d^{t}\nabla f(x^{\ast })=0 $, \ and $\ F(x^{\ast })>0$ \ (this expression means positive definite, according to Chong/Zak). \ Then \ $x^{\ast }$ \ is a strict local minimizer of \ $\ f$. \item remark that this is the only result (other than the definition) that yields us a local minimizer. \end{enumerate} \end{enumerate} \vspace{1pt} \vspace{1pt} \subsubsection{Positive Definite Matrices} \vspace{1pt} \begin{enumerate} \item Defn: \ A matrix \ $Q$ \ is positive definite if the quadratic form \ $xQx$ \ is positive for all non-zero \ $x$.\bigskip \item Fact: \ $Q$ \ is positive definite if and only if the leading principal minors of \ $Q$ \ are all positive.\bigskip \item Example (from Peressini/Uhl): \ $\left( \begin{array}{rrr} 2 & -1 & -1 \\ -1 & 2 & 1 \\ -1 & 1 & 2 \end{array} \right) $ \ has principal leading minors equal to $2$, \ $3$, \ and $4$ \ (respectively). \ Thus it is positive definite.\bigskip \item Example (from Peressini/Uhl): $\left( \begin{array}{rr} 1 & 4 \\ 4 & 1 \end{array} \right) $ \ is not positive definite. \ Minors don't meet condtion and the vector \ $x=(1,-1)$ \ yields $-6$ \ for the associated quadratic form.\bigskip \item Fact: \ A symmetric matrix (as the Hessian usually is) is positive definite if and only if its eigenvalues are all positive.\bigskip \item See Chong/Zak Section 3.4 for more, particularly ``semidefinite'' and ``negative definite''. \ \ Might be a good time to discuss the multivariate form of Taylor's Theorem. \end{enumerate} Problems: \ Chong/Zak, Chapter 6, \ page 76, \ \ 3, 5, 6, 4, 11 \end{document} %%%%%%%%%%%%%%%%%%%%%%% End /document/chap6.tex %%%%%%%%%%%%%%%%%%%%%%%