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


\usepackage{fancyhdr} % Para modificar los encabezados y pies de página
%%%%% SUGERENCIA DE HEADER Y FOOT
%\pagestyle{fancy}
%\fancyhf{}
%\rhead{Share\LaTeX}
%\lhead{Guides and tutorials}
%\rfoot{Page \thepage}
%%%%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\lhead{Pr\'actica 2 -- Primer Cuatrimestre 2018}




\newtheorem{ejer}{Ejercicio}

\newcommand{\bej}{\begin{ejer} \rm}
\newcommand{\fej}{\end{ejer}}
\renewcommand{\theenumi}{\alph{enumi}} % Para cambiar la forma de enumerar en el entorno \begin{enumerate}

\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 2018}}
\hrulefill

\bigskip

\centerline{\bf  Pr\'actica N$^\circ$ 2: Métodos de descenso.}
\bigskip



\medskip
\noindent \textbf{Algoritmos y convergencia}

\bej Dada una constante $b\in\R$, considerar la función punto a conjunto dada por:
$$f(x) = \{y\in\R^n:\, y^t x\le b\}, \quad\forall x\in\R^n.$$
¿f es cerrada?\fej 

\bej Sean $f:X\to Y$ y $g:Y\to Z$ dos funciones punto a conjunto. Probar que si $f$ es cerrada en el punto $x$, $g$ es cerrada en el conjunto $f(x)$ e $Y$ es compacto, entonces $g\circ f$ es cerrada en $x$. \fej

\bej Sean $f:X\to Y$ punto a punto y $g:Y\to Z$ punto a conjunto. Probar que si $f$ es continua en el punto $x$ y $g$ es cerrada en el punto $f(x)$, entonces $g\circ f$ es cerrada en $x$. \fej 

\bej Mostrar que si $A$ es una aplicación punto a punto continua, en el Teorema de Convergencia Global puede eliminarse la hipótesis de que los puntos $x_k$ caigan sobre un compacto.\fej


\bej {\bf (Orden de Convergencia)} Sea $\{e_k\}$ una sucesi\'on de
n\'umeros no negativos convergente a $0$. Decimos que $\{e_k\}$
{\it converge linealmente} (o geom\'etricamente) si existen $q>0$
y $\beta\in(0,1)$ tales que
\[
e_k\le q\beta^k, \qquad \forall k\ge0.
\]
Decimos que $\{e_k\}$ {\it converge superlinealmente} si para todo
$\beta\in(0,1)$ existe $q>0$ tal que $e_k\le q\beta^k$.
Finalmente, dado $p>1$, decimos que $\{e_k\}$ {\it converge al
menos superlinealmente con orden $p$} si existen $q>0$ y
$\beta\in(0,1)$ tales que $e_k\le q\beta^{p^k}$ para todo $k\ge0$.
\begin{enumerate}
\item Verificar que si para alg\'un $\beta\in(0,1)$ vale que
\[
\limsup_{k\to\infty} \frac{e_{k+1}}{e_k}=\beta,
\]
entonces $\{e_k\}$ converge linealmente. \item Mostrar que si
\[
\limsup_{k\to\infty} \frac{e_{k+1}}{e_k}=0,
\]
entonces $\{e_k\}$ converge superlinealmente. \item Verificar que
si $\{e_k\}$ converge superlinealmente con orden $p>1$, entonces,
efectivamente, converge superlinealmente. \item Mostrar que si
\[
\limsup_{k\to\infty} \frac{e_{k+1}}{e_k^p}=\beta,
\]
entonces $\{e_k\}$ converge superlinealmente con orden $p$.
\end{enumerate}
\fej % Ojo que lo mandé a la práctica 0.


\noindent \textbf{Métodos de descenso}

\bej Sea $f:\R^n\to\R$. El algoritmo de descenso genérico consiste en, dado $x_k\in\R^n$, dar una dirección $d_k$ y un paso $t_k > 0$ tal que $f(x_k+t_k d_k) <f(x_k)$, y tomar $x_{k+1}=x_k+t_k d_k$. 
\begin{itemize}
 \item[a)] Probar que si $f$ es diferenciable en $x_k$ y $\nabla f(x_k)\cdot d_k<0$, entonces $d_k$ es una dirección de descenso. 
 \item[b)] Concluir que $-\nabla f(x_k)$ es una dirección de descenso. 
\end{itemize}
\fej


\bej {\bf (Descenso más rápido)}
Sea $f$ de clase $C^1$ en $\mathbb{R}^n$.
\begin{itemize}
\item[(a)] Mostrar que la dirección de $-\nabla f(x_k)$ es la de máximo descenso. Es decir, mostrar que la pendiente de $\phi(t) := f(x_k+t d)$ en $t = 0$ se minimiza entre todas las direcciones $d$ de norma 1 en $d^* = -\frac{\nabla f(x_k)}{\|\nabla f(x_k)\|}$.
\item[(b)] {\bf (Efecto zigzag)} Dada la sucesión $(x_k)_{k\geq1}$ generada por el método del descenso más rápido con búsqueda lineal óptima, mostrar que las direcciones entre iteraciones consecutivas son ortogonales. %Dar condiciones sobre f de manera que fi tenga minimo global en cada iteración. (f unimodal? Podŕe pedir menos?)
\end{itemize}

\fej


\bej Sea $f:\R^n\to\R$ una función cuadrática, y sea $d_k$ una dirección de descenso en el punto $x_k$. Probar que el paso óptimo está dado por:
$$t_k = -\frac{d_k^t\nabla f(x_k)}{d_k^t Hf(x_k) d_k}.$$
\fej

\bej Una función $f:\R\to\R$ se dice \emph{unimodal} en el intervalo $[a,b]$ si existe $x^*\in(a,b)$ tal que $f$ es estrictamente decreciente en $(a,x^*)$ y estrictamente creciente en $(x^*,b)$. Probar que si $f$ es unimodal y continua en $[a,b]$ entonces tiene un único mínimo en $[a,b]$. Probar además que dados $\alpha,\beta$ tales que $a<\alpha<\beta<b$ vale que:
\begin{itemize}
 \item Si $f(\alpha)\le f(\beta)$, entonces $f$ es unimodal en $[a,\beta]$,
 \item Si $f(\alpha) \ge f(\beta)$, entonces $f$ es unimodal en $[\alpha,b]$. 
\end{itemize}
\fej
%
%\bej Dada una función $f$ unimodal en $[a,b]$, se propone el siguiente algoritmo para buscar su mínimo $x^*$: 
%\begin{itemize}
% \item[1.] Se fijan $a_0=a$, $b_0=b$. 
% \item[2.] Para $k=1,2,\dots$ se eligen $\alpha_k,\beta_k$ tales que $a_k<\alpha_k<\beta_k<b_k$.
% \begin{itemize}
% \item[2.1.] Si $f(\alpha_k)\le f(\beta_k)$, se toman: $a_{k+1}=a_k$, $b_{k+1}=\beta_k$.
% \item[2.2.] Si $f(\alpha_k)>f(\beta_k)$, se toman: $a_{k+1}=\alpha_k$, $b_{k+1}=b_k$
%\end{itemize}
%\end{itemize}
%Probar que $\lim a_k = \lim b_k = x^*$. ¿Cuántas veces debe evaluarse $f$ para calcular $[a_{n+1},b_{n+1}]$?
%\fej
%
%\bej {\bf (Búsqueda por la razón dorada:)} Se desea fijar un criterio para la elección de $\alpha_k$, $\beta_k$ en el algoritmo anterior, de manera tal que se cumplan:
%\begin{itemize}
% \item que en cada paso el intervalo se vea reducido en un factor fijo $\eta$:
%$$\beta_{k+1}-\alpha_{k+1}=\eta(\beta_k-\alpha_k),$$
%\item que en cada paso sea necesario evaluar $f$ una sola vez. Es decir, que alguno de los nuevos puntos: $\alpha_{k+1}$ ó $\beta_{k+1}$ coincida con alguno de los anteriores $\alpha_k$ ó $\beta_k$.
%\end{itemize}
%Escribir las fórmulas para $\alpha_{k+1}$ y $\beta_{k+1}$	 en función de $a_k$, $b_k$ y $\eta$ para que se satisfaga la primera condición, y calcular el valor de $\eta$ para que se cumpla la segunda.   \fej

\bej Implementar un algoritmo que reciba como entrada una función $f$, un intervalo $[a,b]$, y una tolerancia $\delta$ y calcule el mínimo de $f$ en $[a,b]$ con error menor o igual que $\delta$, mediante el algortimo de búsqueda por la razón dorada.\fej


\bej
Dada $\delta>0$, sea la funci\'on punto a conjunto $\textbf{S}^\delta$ definida como
\[\textbf{S}^\delta(x,d)=\Big\{y:y=x+\alpha d,\quad 0\leq\alpha\leq\delta;\quad f(y)=\min_{0\leq\beta\leq\delta}f(x+\beta d)\Big\}.\]
Explicar lo que hace $\textbf{S}^\delta$ y probar que si $f$ es continua entonces $\textbf{S}^\delta(x,d)$ es cerrada en (x,d). ¿Por qué es importante este resultado?
\fej
%
\bej
Sea $\varepsilon>0$, sea la funci\'on punto a conjunto $\textbf{S}^\varepsilon$ definida como
\[\textbf{S}^\varepsilon(x,d)=\Big\{y:y=x+\alpha d,\quad 0\leq\alpha;\quad f(y)\leq\min_{0\leq\beta}f(x+\beta d)+\varepsilon\Big\}.\]
Explicar lo que hace $\textbf{S}^\varepsilon$ y probar que si $f$ es continua y $d\neq0$ entonces $\textbf{S}^\varepsilon(x,d)$ es cerrada en (x,d). ¿Por qué es importante este resultado?
\fej
%
%\bej {\bf (Búsqueda Compacta)}
%
%Sea $f: \R^n\rightarrow\R$ una funci\'on $C^2$, \emph{estrictamente} convexa con un \'unico m\'inimo $x^*$ y tal que  $f(x)\rightarrow+\infty$ cuando $||x||\rightarrow+\infty$. 
%\begin{enumerate}
%\item [$a)$] Probar que, fijado un $x_0\in\R^n$, el conjunto $$\{y\in\R^n: f(y)<f(x_0)\}$$ es acotado.
%
%\item[b)] Sea $\mathcal{D}=\{e_1,-e_1,e_2,-e_2, \dots,e_n,-e_n\}$. Probar que para todo $x\neq x^*$ existe $d\in\mathcal{D}$ direcci\'on de descenso en $x$. (Es decir, existe $d\in\mathcal{D}$ y $t_0>0$ tal que $f(x+td)<f(x)$ $\forall\, t\in (0,t_0)$).
%
%\item[\textbf{c)}] Consideramos, para $x\in\mathbb R^n$, $\alpha>0$, la funci\'on punto a conjunto 
%$$A(x,\alpha)=\{y\in\R^n: y=x+\alpha d, \, d\in\mathcal{D}\}$$
%Probar que $A$ es cerrada en $(x,\alpha)$ si $\alpha\neq 0$. 
%
% \item[\textbf{d)}] Estudiamos el algoritmo de B\'usqueda Compacta, dado por:
% 	\begin{tabbing}
%		012\=4567\=8901\=\kill
%	 	$i.$ Tomar $x_0\in\R^n$, $\alpha_0>0$, $k=0$. \\
%		$ii.$ Si existe $y\in A(x_k,\alpha_k)$ tal que $f(y)<f(x)$: \,Poner $x_{k+1} = y$, $\alpha_{k+1} = \alpha_k$, $k = k+1$.\\
%			       \>Si no:\, Poner $\alpha_{k} = \frac{\alpha_k}{2}$\\
%	        $iii.$ Ir a $ii.$
%	\end{tabbing}
%	Probar que $x_k\rightarrow x^*$ $(k\rightarrow\infty)$.
%\end{enumerate}
%\fej

\bej Implementar un algoritmo que reciba como datos una función $f$, un punto $x_k$ y una dirección $d_k$ y aplique la condición de Armijo para determinar el paso del descenso, devolviendo el correspondiente $x_{k+1}$.\fej

\bej Implementar un programa similar al del ejercicio anterior, pero utilizando la condición de Goldstein.\fej

\bej Probar que la condición de Goldstein determina un algoritmo de búsqueda cerrado. \fej
%
%\bej {\bf (Braquistocrona)} Considerar el problema de la \emph{braquistocrona} consistente en hallar la curva que minimiza el tiempo de caída de una particula por efecto de la gravedad. Concretamente, buscamos una función $\varphi:[0,1]\to[0,1]$ tal que $\varphi(0)=1$, $\varphi(1)=0$ tal que minimice el funcional:
%$$T(\varphi) = \int_0^1 \sqrt{\frac{1+\varphi'(x)^2}{2g(1-\varphi(x))}},$$
%donde $g$ es la aceleración gravitatoria. Para resolver este problema se realiza una discretización en la variable $x$: $0=x_0<x_1<\dots<x_n<x_{n+1}=1$ y una discretización en $\varphi$: $1=\varphi_0>\varphi_1>\dots>\varphi_n>\varphi_{n+1}=0$, de manera tal que $\varphi_i$ será la aproximación de $\varphi(x_i)$. Por comodidad, asumiremos que la discretización en $\varphi$ está fijada de antemano (por ejemplo: $\varphi_{i+1}-\varphi_i = \frac{1}{n+1}$), y que las $x_i$ son las variables cuyo valor debe optimizarse. 
%\begin{itemize}
% \item[a)] Probar que si se asume que $\varphi$ es lineal en los intervalos de la discretización, el funcional $T$ puede escribirse:
% $$\widetilde{T}= \sqrt{\frac{2}{g}} \sum_{i=0}^n\sqrt{1+\Big(\frac{x_{i+1}-x_i}{\varphi_{i+1}-\varphi_i}\Big)^2}\Big(\sqrt{1-\varphi_{i+1}}-\sqrt{1-\varphi_i}\Big).$$
% \item[b] Calcular analíticamente el gradiente de la expresión anterior de $\widetilde{T}$.
% \item[c] Implementar funciones que reciban como input el número $n$ de incógnitas de la discretización y devuelvan el funcional $\widetilde{T}$ y su gradiente. 
% \item[d] Calcular la curva braquistocrona minimizando el funcional $\widetilde{T}$ a través de los distintos métodos estudiados hasta el momento: método de Newton y método del gradiente con búsqueda lineal por la razón de oro, y por búsqueda lineal inexacta utilizando la condición de Armijo y la condición de Goldstein. Comparar los resultados.  
%\end{itemize}
%\fej


\bej
Sea $Q\in\mathbb R^{n\times n}$ definida positiva y sean $v_1,...v_n$ vectores l.i. Mostrar que el m\'etodo de Gram-Schmidt puede ser usado para generar una secuencia de direcci\'ones $Q$-ortogonales desde los $v_i$. Espec\'ificamente, muestre que 

\[d_1=v_1;\qquad d_{k+1}=v_{k+1}-\sum_{i=1}^{k} \frac{v^t_{k+1}Q d_i}{d_i^t Q d_i}d_i\]

forma un conjunto $Q-$ortogonal.

\fej


\bej Sea $f(x)=\frac 12 x^t Q x-b^t x$ con $Q$ simétrica DP. Sea $x_1$ un minimizante de $f$ en un subespacio $S_1$ que contiene al vector $d$ y sea $x_2$ un minimizante de $f$ en un subespacio $S_2$ que contiene a $d$. Mostrar que $\overline x=x_1-x_2$ es $Q-$ortogonal a $d$.

\fej



\bej Implementar el m\'etodo del Gradiente Conjugado para minimizar una funci\'on cuadr\'atica $f(x)=\frac 12 x^t Q x-b^t x$:


\begin{itemize}
 \item[(1)] A partir de un $x_0$ tomar $d_0=-g_0=b-Q x_0$
 \item[(2)] Para $k=0,1,...n-1$ hacer:
\begin{itemize}
\item[(a)] Hacer $x_{k+1}=x_k+\alpha_k d_k$ con 

\[\alpha_k=\frac{-g^t_k d_k}{d^t_k Qd_k}, \qquad g_k=Qx_k-b.\]

\item[(b)] Hacer $d_{k+1}=-g_{k+1}+\beta_k d_k$ con 
\[\beta_{k}=\frac{g^t_{k+1} Q d_k}{d^t_k Q d_k}.\]
\end{itemize}
\end{itemize}

\fej


\bej Dada $f(x) = \frac 12 x^t Q x-b^t x$ con $Q$ simétrica definida positiva, si definimos $\mathcal B_k=<d_0,\cdots,d_{k-1}>$ el subespacio generado por las primeras $k$ direcciones conjugadas, mostrar que el m\'etodo de las direcciones conjugadas, en cada $x_k$ minimiza la funci\'on objetivo tanto en la recta $L:x_{k-1}+\alpha d_{k-1}:\alpha\in\mathbb R$, como en la variedad lineal $x_0+\mathcal B_k.$ 

\fej



\bej Implementar el siguiente algoritmo que generaliza el del gradiente conjugado a funciones no cuadr\'aticas:

\begin{itemize}
 \item[(1)] A partir de un $x_0$ tomar $g_0=\nabla f(x_0)^T$ y hacer $d_0=-g_0.$
 \item[(2)] Para $k=0,1,...n-1$ hacer:
\begin{itemize}
\item[(a)] Hacer $x_{k+1}=x_k+\alpha_k d_k$ con $\alpha_k=\frac{-g^T_k d_k}{d^T_k Hf(x_k)d_k}.$
\item[(b)] Hacer $g_{k+1}=\nabla f(x_{k+1})^T$.
\item[(c)] Si $k\neq n-1$, hacer $d_{k+1}=-g_{k+1}+\beta_k d_k$ con 
\[\beta_{k}=\frac{g^T_{k+1} Hf(x_k)d_k}{d^T_k Hf(x_k)d_k}.\]
y repetir $(a)$.
\end{itemize}
\item[(3)] Hacer $x_0=x_n$ y volver a $(1)$.
\end{itemize}
\fej




\end{document}