Examen Profesional ITAM
Forfatter
Cesar Becerra Campos
Last Updated
a year ago
License
LaTeX Project Public License 1.3c
Resumé
Presentación para usar en la defensa del trabajo de titulación. De preferencia para Itamitas
\documentclass[fleqn]{beamer}
\usepackage[spanish]{babel}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
% vertical separator macro
\newcommand{\vsep}{
\column{0.0\textwidth}
\begin{tikzpicture}
\draw[very thick,black!10] (0,0) -- (0,7.3);
\end{tikzpicture}
}
% More space between lines in align
\setlength{\mathindent}{0pt}
% Beamer theme
\usetheme{ZMBZFMK}
\usefonttheme[onlysmall]{structurebold}
\mode<presentation>
%\setbeamercovered{transparent=10}
% align spacing
\setlength{\jot}{0pt}
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\AtBeginSubsection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsubsection]
\end{frame}
}
% Only the first Slide
\title{El Método de la Ruptura}
\author{César Becerra Campos}
\institute[Instituto Tecnológico Autónomo de México]{ Asesor:\\ Dr. Andreas Wachtel }
\date{\today}
% Portada
\begin{document}
\begin{frame}
\titlepage
\end{frame}
% Índice
\begin{frame}{Índice}
\tableofcontents
\end{frame}
% Frame 1
\section{¿Qué es el Método de la Ruptura?}
\begin{frame}
\frametitle{Introducción}
¿Qué es el Método de la Ruptura?
\begin{itemize}[<+->]
\item Un método de optimización numérica
\item Implementado para funciones $f:\mathbb{R}^2\rightarrow \mathbb{R}$
\item Con un punto de partida $\vec{x}_0$ estima, potencialmente, \\todos los mínimos locales
\end{itemize}
\end{frame}
\section{¿Cómo funciona?}
\subsection{Intuición en general}
\begin{frame}{Curvas de Nivel}
\begin{itemize}
\item Conjunto de Nivel: $\ell_{f}(\vec{x}_0)= \{\vec{x}: f(\vec{x}) = f(\vec{x}_0) \}$
\item Curva de Nivel: Una parte conexa de $\ell_f(\vec{x}_0)$
\end{itemize}
\end{frame}
\begin{frame}{Primera Curva de Nivel}
\begin{figure}
\centering
\includegraphics[width = 0.6\textwidth]{Hourglass-cropped.pdf}
\caption{Función de Himmelblau: $\vec{x}_0 = (3,-2)$}
\label{fig:my_label}
\end{figure}
\end{frame}
\begin{frame}{Encontrando Mínimos}
\begin{figure}
\centering
\includegraphics[width = 0.6\textwidth]{FirstSplit-cropped.pdf}
\caption{Función de Himmelblau: $\vec{x}_0 = (3,-2)$}
\label{fig:my_label}
\end{figure}
\end{frame}
\begin{frame}
\frametitle{Haz recursión y conquistarás...}
\begin{figure}
\centering
\includegraphics[width = 0.6\textwidth]{FullMethod.pdf}
\caption{Función de Himmelblau: $\vec{x}_0 = (4,4)$}
\label{fig:my_label}
\end{figure}
\end{frame}
\subsection{Siguiendo curvas de nivel}
\begin{frame}
\frametitle{Para Seguir una Curva de Nivel}
\begin{block}{Requisitos:}
Introducir un parámetro de tiempo, $t$. Así, $\Phi(t) = (x(t),y(t))$ es la parametrización de la curva de nivel.\\
\vspace{10 pt}
Encontrar una EDO que siga la curva. \\
\vspace{10 pt}
Aplicar un método numérico que siga la EDO
\end{block}
\end{frame}
\begin{frame}{Obteniendo una EDO}
Sabemos que $\nabla f(\vec{x})$ y la curva de nivel son perpendiculares.\\
\vspace{10 pt}
Calculamos $\nabla f(\vec{x})$ de manera exacta o con diferencias finitas.\\
\vspace{ 10pt}
Multiplicamos por $A = \begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}$ para girar $90^{\circ}$\\
\vspace{ 10pt}
Así, $\begin{pmatrix}
\dot{x} \\
\dot{y}
\end{pmatrix}
=
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix} \nabla f(\vec{x})$, es la EDO que necesitamos para seguir la curva de nivel.
\end{frame}
\begin{frame}{La EDO}
Definimos $H(x) = \begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix} \nabla f(\vec{x})$, y tenemos el siguiente PVI:\\
\vspace{10 pt}
\begin{block}{PVI en cada paso:}
$$\begin{pmatrix}
\dot{x} \\
\dot{y}
\end{pmatrix}
=
\frac{H(\vec{x})}{\max\{1,\left|| \nabla f(\vec{x}(t_i))\right||\}}$$\\
\vspace{3 pt}
$$\vec{x}(0) = \vec{x}(t_i)$$
\end{block}
\end{frame}
\begin{frame}{¿Cómo seguir esa EDO?}
\begin{itemize}
\item RK4
\item Trapecio Explícito
\item ¡Muchos más!
\end{itemize}
\end{frame}
\subsection{Decidiendo qué hacer}
\begin{frame}{Una Medida Importante}
\begin{block}{Para medir la curvatura...}
$\theta_i$ es el ángulo de $\nabla f(\vec{x}_i)$ respecto al eje $x$.
\end{block}
\begin{figure}
\centering
\includegraphics[width = 0.5\textwidth]{figure31.pdf}
\caption{Midiendo la Curvatura}
\label{fig:my_label}
\end{figure}
\end{frame}
\begin{frame}{Convexidad y Concavidad}
\begin{block}{Tres opciones:}
\begin{itemize}[<+->]
\item Donde $\theta^{'} > 0$, la curva de nivel es convexa (bien inflada).
\item Donde $\theta^{'} < 0$, la curva de nivel es cóncava (hundida hacia adentro).
\item Donde $\theta^{'} = 0$, la curva de nivel es una línea recta.
\end{itemize}
\end{block}
\end{frame}
\begin{frame}{Ejemplo Ilustrativo}
\begin{columns}
\column{0.5\textwidth}
\begin{figure}
\centering
\includegraphics[width = \textwidth]{FINALIHOPE-cropped.pdf}
\label{fig:my_label}
\end{figure}
\column{0.5\textwidth}
\begin{figure}
\centering
\includegraphics[width = \textwidth]{Hourglass-cropped.pdf}
\label{dual}
\end{figure}
\end{columns}
\centering{Figura: Una Curva de Nivel y su medida $\theta^{'}$}
\end{frame}
\begin{frame}{Recursión por Ruptura}
\begin{block}{Def: Picos negativos}
Para una curva de nivel $M_{\vec{x}_0}$, los \emph{Picos Negativos} son aquellos puntos $\vec{x}_i$ donde $\theta^{'}_i$ alcanza un mínimo
\end{block}
Si dos Picos Negativos están cerca, creamos una \emph{ruptura}. %Es decir, tomamos $\vec{y}_0$ y $\vec{z}_0$ en lados opuestos de los Picos Negativos, y llamamos recursivamente al método sobre $\vec{y}_0$ y $\vec{z}_0$.
\end{frame}
\begin{frame}{Recursión por Ruptura}
\begin{figure}
\centering
\includegraphics[width = 0.6\textwidth]{SiSePudo-cropped.pdf}
\caption{Ruptura}
\label{fig:my_label}
\end{figure}
\end{frame}
\begin{frame}{Encontrar el Mínimo}
\begin{block}{Convexidad Global}
Si $\theta^{'}_i>0$ para toda $i$, entonces la curva de nivel es \emph{globalmente convexa.}
\end{block}
\vspace{10 pt}
Si una curva de nivel es globalmente convexa, entonces:\\
\vspace{10 pt}
\begin{columns}
\column{0.4\textwidth}
\begin{block}{¿Está cerca de un mínimo?}
Método de Newton
\end{block}
\column{0.4\textwidth}
\begin{block}{¿Está lejos?}
Bajar el Nivel
\end{block}
\end{columns}
\end{frame}
\begin{frame}{Bajar el Nivel}
Sea $L$ la longitud de la curva. Luego, tomamos:\\ $$\vec{y}_0 = \vec{x}_i-kL\frac{\nabla f(\vec{x})}{\left||\nabla f(\vec{x})\right||}$$
\vspace{10 pt}
Aquí, $k$ es un parámetro que representa la proporción de $L$ a avanzar.
\end{frame}
\begin{frame}{Bajar el Nivel}
\begin{figure}
\centering
\includegraphics[width = \textwidth]{Logo.png}
%\caption{Bajando el Nivel sin Convexidad Global}
\label{fig:my_label}
\end{figure}
\end{frame}
\begin{frame}{Esquema General}
\begin{figure}
\centering
\includegraphics[width = 0.75\textwidth]{SplitMethod.pdf}
% \caption{Método Completo}
\label{fig:my_label}
\end{figure}
\end{frame}
\section{Resultados y comentarios}
\begin{frame}{Resultados}
\begin{table}[h]
\centering
\caption{Función de Himmelblau: $\vec{x}_0 = (4,4)$}
\begin{tabular}{|c|c|c|}\hline
Minimos & Minimos estimados & Error \\
\hline
(3.0,2.0) & (3.0000..., 1.9999...) & 1.7117 e-12\\
(-2.805118, 3.131312) & (-2.805118..., 3.131312...) & 5.3283 e-07\\
(-3.779310, -3.283186) & (-3.779310..., -3.283185...) & 2.5449 e-07\\
(3.584428, -1.848126) & (3.584428..., -1.848126...) & 6.2730 e-07\\
\hline
\end{tabular}
\label{tab:HimMinima}
\end{table}
\end{frame}
\begin{frame}{Resultados}
\begin{table}[h]
\centering
\caption{Método de la ruptura aplicado a diferentes funciones}
\begin{tabular}{|c|c|c|c|}\hline
Función & $\vec{x}_0$ & Minimos estimados & Error \\
\hline
Styblinski -Tang & (4,4) &(-2.9035,-2.9035) & 3.9274e-08\\
Easom & (1.6,1.6) &(3.1415,3.1415) & 1.7796e-11\\
Booth & (0,10) &(0.9999,2.9999) & 1.0422e-09\\
White \& Holst & (0,0) &(0.9999,0.9999) & 4.2564e-11\\
\hline
\end{tabular}
\label{tab:Various}
\end{table}
\end{frame}
\begin{frame}{Comentarios}
\begin{itemize}[<+->]
\item El método requiere funciones suaves y con curvas de nivel cerradas.
\item Aproxima bien los mínimos, aunque algunos parámetros deben ser ajustados para cada función $f$.
\item Tener información parcial sobre el conjunto de nivel ha sido un problema constante.
\end{itemize}
\end{frame}
\begin{frame}{Bibliografía}
\begin{enumerate}
\item Amir Beck, \emph{Introduction to Nonlinear Optimization - Theory, Algorithms and Applications} MOS-SIAM series on Optimization. SIAM, 2014.\\
\item Andrei Neculai, \emph{An Unconstrained Optimization Test Function Collection} Advanced Modeling and Optimization, Vol. 10, number 1, 2008.\\
\item Jorge Nocedal and Stephen Wright, \emph{Numerical Optimization}. New York: Springer, 2006.
\end{enumerate}
\end{frame}
\end{document}