\documentclass[11pt,spanish]{article}
\usepackage[spanish]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig,euscript}
\usepackage[T1]{fontenc}
\usepackage{enumerate}

\newtheorem{ejer}{Ejercicio}

\newcommand{\bej}{\begin{ejer} \rm}
\newcommand{\fej}{\end{ejer}}

\def\A{\mathbb{A}}
\def\C{\mathbb{C}}
\def \N{\mathbb{N}}
\def \P{\mathbb{P}}
\def \Q{\mathbb{Q}}
\def \R{\mathbb{R}}
\def \Z{\mathbb{Z}}


\def\d{\displaystyle}
\def\erf{\mbox{\rm erf}}
\def\dx{\ dx}
\topmargin-1cm \vsize=29.5cm \hsize=21cm
\leftmargin 1cm
\setlength{\textwidth}{14cm} \setlength{\textheight}{23cm}
\setlength{\evensidemargin}{0.0cm}
\def\iint{\int\hskip -7pt\int}


\begin{document}
\thispagestyle{empty}

\centerline{{\small Universidad de Buenos Aires - Facultad de
Ciencias Exactas y Naturales - Depto. de Matem\'atica}}

\vskip 0.2cm

\hrulefill
\vskip 0.2cm
\centerline{{\bf\Huge {\sc Optimización }}}
\vskip 0.2cm
\centerline{{\ttfamily Primer Cuatrimestre 2016}}
\hrulefill

\bigskip

\centerline{\bf  Pr\'actica N$^\circ$ 1: Minimización sin restricciones.}
\bigskip



\medskip

\noindent{\bf Generalidades:}

\bej Mostrar ejemplos de las siguientes situaciones:
\begin{enumerate}[(a)]
 \item $f:[0,1]\to\R$ tal que todos los puntos de $[0,1]$ sean extremos locales de $f$.

 \item $\Omega\subset\R^2$ y $f:\Omega\to\R$ tal que $f$ tenga varios minimizadores locales y globales. 

 \item $\Omega\subset\R$ y $f:\Omega\to\R$ continua tal que $f$ no tenga extremos absolutos en $\Omega$.

 \item $\Omega\subset\R$ compacto y $f:\Omega\to\R$ tal que $f$ no tenga extremos absolutos en $\Omega$. 

 \item $\Omega\subset\R$ compacto y $f:\Omega\to\R$ acotada tal que $f$ no tenga extremos absolutos en $\Omega$. 

\end{enumerate}
\fej


\bej $f:\R^n\to\R$, continua tal que $\lim_{\| x \|
\rightarrow +\infty} f(x) = +\infty$ entonces $f$ tiene un
minimizador global en $\R^n$. \fej

\bej $f:\R^n\to\R$ continua tal que $\exists x_0
\in \R^n$ de modo que el conjunto de nivel $\{x \in \R^n | f(x) \leq f(x_0)
\}$ es acotado, entonces $f$ tiene un minimizador global en
$\R^n$. \fej

%\newpage
%\medskip
%\noindent \textbf{Minimizaci\'on sin restricciones}
%\medskip

%\bej
%Considerar los n\'umeros reales $a_1 \leq a_2 \leq \dots \leq a_n$. Resolver los %siguientes problemas:
%\begin{enumerate}
%\item Minimizar $\sum_{i=1}^n |x-a_i|$

%\item Minimizar M\'aximo $\{ |x-a_i|, i = 1, \dots, n \}$

%\item Minimizar $\sum_{i=1}^n |x-a_i|^2$

%\item Maximizar $\Pi_{i=1}^n |x-a_i|$

%\end{enumerate}
%\fej

%\bej
%Encontrar los puntos cr\'{\i}ticos de
%$$f(x) = 2x_1^3 - 3x_1^2 - 6x_1x_2(x_1 - x_2 - 1)$$

%?`Cu\'ales de esos son minimizadores o maximizadores, locales o globales?
%\fej

\bej\label{ejemplo}
Sea $f(x) = (x_1 - x_2^2)(x_1 - \frac{1}{2}x_2^2)$.
Verificar que, para $x = (0,0)$, $\lambda = 0$ es un
minimizador local de $\phi(\lambda) = f(x+\lambda
d)$ para todo $d \in \R^2$, pero $x$ no es un
minimizador local de $f$.
\fej

%\bej
%Sea $f(x) = (x_2 - x_1^2)^2 + x_1^5$. Hallar los puntos cr\'{\i}ticos de $f$.
%?`Cu\'ales de esos son minimizadores o maximizadores, locales o globales?
%\fej

%\bej
%Encontrar, si es posible, $a$ y $b$ de manera que $f(x) = x^3 + ax^2 + bx$ tenga un m\'aximo
%local en $x=0$ y un m\'{\i}nimo local en $x=1$.
%\fej

%\bej Considere la función $f : \mathbb R^2 \to \mathbb R$ definida por:
%$$f (x)=x^2_1+x^2_2(1-x_1)^3$$
%\begin{enumerate}
%\item Realice un gráfico de la función e identifique un minimizador local.
%\item ?`Existe un único minimizador local?
%\item ?`Es este un caso donde existe un único minimizador local estricto, el
%cual no es global?
%\end{enumerate}
%\fej


\bej
Encontrar ejemplos donde:

\begin{enumerate}[(a)]
\item $x^*$ es minimizador local de $f$ en $\Omega$, pero $\nabla f(x^*)\neq0$

\item $x^*$ es minimizador local de $f$ en $\Omega$, $\nabla f(x^*)=0$, pero $\nabla^2 f(x^*)$ no es semidefinida positiva.

\item $\Omega$ es abierto, $\nabla f(x^*)=0$ pero $x^*$ no es minimizador local.

\item $\Omega$ es abierto, $\nabla f(x^*)=0$, $\nabla^2f(x^*)\geq0$,  pero $x^*$ no es minimizador local.

\item $\Omega$ es abierto, $x^*$ minimizador local estricto, pero $\nabla^2 f(x^*)$ no sea definida positiva.

\end{enumerate}
\fej

%\bej
%Sea $f(x,y,z)= 2x^2+xy+y^2+yz+z^2-6x-7y-8z+9,$

%\begin{itemize}
%\item[a)] Usando las condiciones de primer orden, encuentre un punto m\'inimo de %$f$.
%\item[b)] Verifique que el punto es un m\'inimo relativo verificando que se %cumplen las condiciones de segundo orden.
%\item[c)] Pruebe que el punto es un m\'inimo global.
%\end{itemize}
%\fej

\bej Sea $f\in C^2(\mathbb R^n)$ una funci\'on cuadr\'atica, $f(x)=\frac 12 x^T Q x-b^T x+c$.
Escribir un algoritmo que verifique si $f$ tiene un mínimo y, en tal caso lo encuentre resolviendo un sistema de ecuaciones apropiado.
\fej

\bej Escribir un algoritmo que dada una función $f:\R^n\to\R$, un punto $a\in\R^n$ y un índice $i$, $1\le i\le n$, aproxime $\frac{\partial f}{\partial x_i}(a)$. \fej

\bej Utilizando el programa del ejercicio anterior, escribir programas que calculen $\nabla f(a)$ y $Hf(a)$, para $f$ y $a$ dados.\fej

\bej Escribir un programa que dada una $f$ y un punto inicial $x_0$ busque un mínimo $x^*$ de $f$ usando el algoritmo de Newton generalizado. Pruébelo para i) el caso del Ejercicio \ref{ejemplo} y ii) para la función $f(x,y,z) = -1 - 4x + 6x^2 - 4x^3 + x^4 - 4y + y^2 + 4z + 6z^2 + 4z^3 + z^4$.\fej

\bej
Sea $g: \R \rightarrow \R$ una funci\'on estrictamente creciente y $f: \R^n \rightarrow \R$.
Probar que minimizar $f(x)$ es equivalente a minimizar $g(f(x))$.
\fej

\medskip 

\noindent{\bf Funciones Convexas:}

\bej Probar que si $f:\R^n\to\R$ es estrictamente convexa y tiene mínimo, entonces el mínimo es único. Dar un ejemplo de función estrictamente convexa sin mínimo. \fej

\bej $f:\R^n\to\R$ estrictamente convexa con un único mínimo $x^*$. Probar que $f(x)\to\infty$ cuando $\|x\|\to\infty$. \fej

\bej Sea $\{f_i\}_{i\in I}$ un conjunto de funciones convexas definidas sobre un conjunto convexo $\Omega$. Muestre que la funci\'on $f(x)=\sup_{i\in I} f_i(x)$ es convexa en la regi\'on en la cual es finita.
\fej

\bej Sea $\gamma$ un funci\'on mon\'otona no decreciente de una variable, es decir $r'>r$ implica $\gamma(r')\geq\gamma(r)$, que adem\'as es convexa y sea $f$ una funci\'on convexa definida en un conjunto convexo. Muestre que la funci\'on $\gamma(f)$ definida como $\gamma(f)(x)=\gamma(f(x))$ es convexa sobre $\Omega$.\fej


\bej Sea $f\in C^2(\Omega)$, $\Omega\subset\mathbb R^n$. Muestre que una condici\'on necesaria y suficiente para que un punto $x^*$ en el interior de $\Omega$ sea un m\'inimo relativo de $f$ es que $\nabla f(x^*)=0$ y que $f$ sea localmente convexa en $x^*.$
\fej

\medskip

\noindent{\bf QR y SVD:}


\bej Sea $v\in \C^n$. Probar que la matriz $I-vv^*$ es unitaria si y s\'olo si $\|v\|_2^2=2$ o $v=0$.
\fej

\bej Dados  $x\neq y$ en $\C^n$ tal que $\|x\|_2=\|y\|_2$ y $\langle x, y \rangle$ es real. Probar que la matriz unitaria $U=I-vv^*$ con $\displaystyle v=\frac{\sqrt{2}}{\|x-y\|_2} (x-y)$ satisface que  $Ux=y$.
\fej

\bej\label{qrimp} Implementar un programa que calcule la descomposición $QR$ de una matriz aplicando de manera directa el método de ortonormalización de Gram-Schmidt. Generar algunas matrices aleatorias y comparar las descomposiciones arrojadas por estos programas entre sí y con las dadas por el comando \verb+qr+ de Matlab.
\fej



\bej Considerar el problema de cuadrados mínimos, es decir el problema de buscar, dadas por $A\in\R^{n\times m}$ ($n>m$) y $b\in\R^n$, un punto $x^*\in\R^m$ tal que:
$$\|Ax^*-b\| = \min_{x\in\R^m} \|Ax-b\|.$$
Probar que la descomposición $QR$ de $A$ permite resolver este problema. En particular, que si $A=QR$, entonces $x^*$ satisface que $Rx^* = Q^t b.$\fej

\bej Escribir un programa que resuelva el problema de cuadrados mínimos utilizando el algoritmo del Ejercicio \ref{qrimp}. \fej

\bej  Dada $A\in\R^{n\times m}$, con descomposición en valores singulares $A=U\Sigma V^*$, se define 
	  $A^\dagger=V\Sigma^\dagger U^*$ la \emph{pseudoinversa} de Moore-Penrose de $A$, donde $\Sigma^\dagger$ es la matriz resultante de invertir los elementos no nulos de $\Sigma$ y trasponerla:
\begin{displaymath}
 \Sigma=\begin{pmatrix}
 \sigma_1 & 0 & 0 & \dots &  & &0\\
  0 & \sigma_2 & 0 & \dots  & &\\
  0 &  0 & \ddots & \dots & & &\vdots\\
  \vdots & & & \sigma_r & & &\\
    & & & & 0 & &\\
    & & & &  & \ddots &\\
    & & & &  & & 0 \\
    \vdots& & & &  & & \vdots \\
    0 & \dots & & & & & 0
\end{pmatrix}\longrightarrow
\Sigma^\dagger =\begin{pmatrix}
 \frac{1}{\sigma_1} & 0 & 0 & \dots &  & &0 &\dots & 0\\
  0 & \frac{1}{\sigma_2} & 0 & \dots  & & & &\vdots\\
  0 &  0 & \ddots & \dots & & &\vdots & & \\
  \vdots & & & \frac{1}{\sigma_r} & & & & &\\
    & & & & 0 & & & & \\
    & & & &  & \ddots & & &\vdots\\
    & & & &  & & 0 & \dots & 0\\
\end{pmatrix}
\end{displaymath}
\begin{itemize}
       \item[a)] Probar que $A^\dagger$ satisface las condiciones de Penrose (En muchas ocasiones $A^\dagger$ se define como la única matriz que
		cumple estas condiciones):
	      \begin{itemize}
	      \item[i.] $A^\dagger AA^\dagger=A^\dagger$ 
	      \item[ii.] $AA^\dagger A=A$
	      \item[iii.] $(AA^\dagger)^*=AA^\dagger$
	      \item[iv.] $(A^\dagger A)^*=A^\dagger A$
	      \end{itemize}
	\item[b)] Concluir que la transformación dada por $AA^\dagger$ es la proyección ortogonal sobre $Im(A)$.
\end{itemize}
\fej


\bej Dada $A\in\R^{n\times m}$ con $n\geq m$ y $b\in\R^n$. Sea $A=U\Sigma V^t$ la descomposición en valores
singulares de $A$. se quiere encontrar un 
	    $\hat{x}\in\R^m$ tal que:
\begin{equation}\label{eqfun}
 \|A\hat{x}-b\|_2=\min_{x\in\R^n}\|Ax-b\|_2
\end{equation} 

\begin{itemize}
\item[a)] Probar que si rg$(A)=m$, entonces $\hat{x}$ es única y $\hat{x}=A^\dagger b$. (Sugerencia: recordar que $Nu(A^t)=Im(A)^\perp$).
 \item[b)] Si rg$(A)=r<m$, $\hat{x}$ no es única. En efecto, si consideramos $\tilde{x}\in Nu(A)$, $A(\hat{x}+\tilde{x})=A\hat{x}$. Probar
	    que $\hat{x}=A^\dagger b$ es la única solución a \eqref{eqfun} en $Nu(A)^\perp$.
\end{itemize}
\fej

\bej Escriba un programa en Matlab que reciba como input una matriz $A$ y un entero positivo $r$ y:
\begin{itemize}
 \item Calcule la descomposición en valores singulares $A=U\Sigma V'$, utilizando el comando \verb+svd+. 
 \item Corrija la matriz $\Sigma$ poniendo $\sigma_i=0$, $\forall i>r$.
 \item Devuelva $B=U\widetilde{\Sigma} V'$, siendo $\widetilde{\Sigma}$ la matriz que resulta de corregir $\Sigma$ según el ítem anterior.
\end{itemize}

Este programa calcula la matriz $B$ de rango $r$ tal que  la norma $\|A-B\|_2$ es mínima. Aplique este programa a distintas matrices, con distintos valores de $r$. 
\fej

\bej
El programa del ejercicio anterior puede utilizarse para comprimir imágenes. En efecto, dada una imagen blanco y negro el comando \verb+imread+ de Matlab convierte la imagen en una matriz en la que cada casillero representa un píxel y su valor corresponde al color del píxel en escala de grises.  El comando \verb+imshow+ aplicado a esta matriz, muestra la imagen, mientras que el comando \verb+imwrite+ permite guardar la matriz como un archivo de imagen.

Implementar un algoritmo que reciba como input un archivo de imagen y un entero positivo $r$, realice la compresión como en el ejercicio anterior y guarde el resultado en otro archivo. Experimentar con el valor de $r$, observando cuán chico puede ser $r$ en relación con el tamaño de la matriz si se desea conservar calidad en la imagen. 

La misma experiencia puede repetirse con imágenes en color. En este caso, debe tenerse en cuenta que el comando \verb+imread+ devuelve un arreglo $A$ de tamaño $m\times n\times 3$: la imagen es de $m\times n$ píxeles y $A(:,:,1)$, $A(:,:,2)$, $A(:,:,3)$ son las matrices correspondientes a su descomposición $RGB$ (red-green-blue).
\fej


\end{document}

