You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

233 lines
7.8 KiB

\documentclass[10pt]{article}
\usepackage[activeacute,spanish]{babel}
\usepackage[left=1.5cm,top=1.5cm,right=1.5cm, bottom=1.5cm,letterpaper, includeheadfoot]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amssymb, amsmath, amsthm}
\usepackage{graphicx}
\usepackage{lmodern,url}
%\usepackage{fourier-orns}
\usepackage{colonequals}
\usepackage{algorithm2e}
\setlength{\parindent}{0em}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancypagestyle{plain}{%
\fancyhf{}
\lhead{\footnotesize\itshape\bfseries\rightmark}
\rhead{\footnotesize\itshape\bfseries\leftmark}
}
% macros
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\C}{\mathbb C}
%Teoremas, Lemas, etc.
\theoremstyle{plain}
\newtheorem{teo}{Teorema}
\newtheorem{lema}{Lema}
\newtheorem{prop}{Proposición}
\newtheorem{cor}{Corolario}
\newtheorem*{obs}{Observación}
\theoremstyle{definition}
\newtheorem*{defi}{Definición}
\newtheorem*{ej}{Ejemplo}
\newtheorem*{warning}{\raisebox{0.2em}{\danger} Advertencia}
% fin macros
%%%%% NOMBRE ESCRIBAS Y FECHA
\newcommand{\sca}{Felipe Contreras}
\newcommand{\scb}{Emilio Molina}
\newcommand{\catnum}{20 (?)}
\newcommand{\fecha}{15 de Noviembre de 2013}
%%%%%%%%%%%%%%%%%%
%Macros para este documento
\newcommand{\cin}{\operatorname{cint}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\conv}{\mathop\mathrm{conv}}
\begin{document}
%Encabezado
\fancyhead[L]{Facultad de Ciencias Físicas y Matemáticas}
\fancyhead[R]{Universidad de Chile}
\vspace*{-1.2 cm}
\begin{minipage}{0.6\textwidth}
\begin{flushleft}
\hspace*{-0.5cm}\textbf{MA4701. Optimización Combinatorial. 2013.}\\
\hspace*{-0.5cm}\textbf{Profesor:} José Soto\\
\hspace*{-0.5cm}\textbf{Escriba(s):} \sca~y~\scb\\
\hspace*{-0.5cm}\textbf{Fecha:} \fecha.
\end{flushleft}
\end{minipage}
\begin{minipage}{0.36\textwidth}
\begin{flushright}
\includegraphics[scale=0.15]{fcfm}
\end{flushright}
\end{minipage}
\bigskip
%Fin encabezado
\begin{center}
\LARGE\textbf{Cátedra \catnum}
\end{center}
\section{Método de la Elipsoide}
Originalmente, fue propuesto por N. Shor ('70) en el contexto de Optimización
convexa. En el '79, Khachiyan mostró, que haciendo ciertos cambios, este método
corre en tiempo polinomial para optimizar PL.
Dado $K$ convexo y cerrado en $\R^d$ (de manera implícita que veremos más
adelante), con $K$ satisfaciendo ciertas hipótesis mínimas, puede o bien
certificar que $K$ es vacío o encontrara $x^*\in K$.
\begin{defi}
Un Oŕaculo de separación para $K\subseteq\R^d$ es un algoritmo que dado
un punto $z\in\R^d$, certifica que $z\in K$ o encuentra un hiperplano
separador, es decir, encuentra $a\in R^d$ tal que $a^Tx < a^Tz, \forall
x\in K$.
Diremos que el oráculo es polinomial si, dados
\begin{itemize}
\item $N = \#\text{ bits del problema original}$
\item $d = \text{ dim. del espacio}$
\item $<z> = \#\text{bits necesarios para codificar $z$}$,
\end{itemize}
éste es polinomial en $N, d, <z>$.
\end{defi}
\begin{ej}
\begin{enumerate}
\item $K = \{x\in\R^d: Ax\leq b\}$ con $A, b$ dados. Un oráculo para
$K$, dado $z\in\R^d$ es el siguiente
\begin{itemize}
\item Llamemos $a_i$ a la fila $i$-ésima de $A$
\item Revisar para todo $i$ si $a_i^T<\leq b$
\item Si es cierto, respondemos $z\in K$
\item Si no, devolvemos el $a_i$ donde falla
\end{itemize}
\item Dado $G = (V,E)$, $d = |E|$. $K = \{x\in\R^d: x(\delta(S))\geq 1,
\forall \varnothing\subsetneq S\subsetneq V, x\geq 0\}$. Si
queremos un oráculo polinomial, no podemos revisar todas las
desigualdades, pues hay una cantidad exponencial de ellas. Sin embargo,
podemos hacer lo siguiente:
\begin{itemize}
\item Revisar si $z\geq 0$
\item Revisar si $\min_{\varnothing\subsetneq S\subsetneq V}
z(\delta(S)) \geq 1$. Para ello, basta calcular el corte mínimo
$S^*$ y revisar si $z(\delta(S^*))\geq 1$. Si no lo es, devolver el
hiperplano $x(\delta(S^*))$.
\end{itemize}
\end{enumerate}
\end{ej}
\begin{defi}
Una elipsoide $E\subseteq\R^d$ es una transformación lineal afín invertible
de $B(0,1)$.
\end{defi}
\begin{ej}
Si $T(x) = Mx + b$ con $M$ invertible,
\[T(B(0,1)) = \{T(x): x^Tx\leq 1\} = \{y: (M^{-1}(y-b))^T(M^{-1}(y-b)\}
= \{y: (y-b)^T((M^-1)^TM^{-1})(y-b)\leq\}\]
Si llamamos $A = MM^T$, entonces $T(B) = \{y: (y-b)A^{-1}(y-b)\leq 1\}$. A
esta elipsoide la llamaremos $E(A,b)$, donde $A$ es definida positiva.
\end{ej}
\begin{prop}
\begin{itemize}
\item $B(0, r) = E(=, r^2I)$.
\item Una elipsoide alineada con semiradios $r_i$ es
$E\left(0,\begin{pmatrix}r_1^2 & & \\ & \ddots & \\ & &
r_d^2\end{pmatrix}\right)$.
\item $Vol(E(b,A)) = Vol(B(0,1))\sqrt{\det{A}} =
Vol(B(0,1))\prod\sqrt{\lambda_i}$, donde $\lambda_i$ son los valores
propios de $A$.
\end{itemize}
\end{prop}
\subsection*{Método de Elipsoide}
DATOS: Convexo cerrado $K$ con oráculo de separación. Supondremos que tenenemos
$p,R$ tales que $K\subseteq B(p,R)$. $l$ tal que si $K\neq\varnothing$,
entonces $Vol(K)\geq l$. Alternativamente, se puede dar un $r$ tal que si
$K\neq\varnothing$, entonces existe $c\in K$ tal que $B(c,R)\subseteq K$.
%%Meter dibujito
\begin{algorithm}
$E\gets B(p,R)$\;
\While{$Vol(E)>l$}{
\If{$p$ (centro de $E$) está en $K$}{
Devuelve $p$\;
}\Else{
Usar oráculo para encontrar $c$ tq $K\subseteq E\cap \{x:c^Tx\leq
c^Tp\}$\;
$E\gets$ el elipsoide de volumen mínimo que contiene $E\cap
\{x:c^Tx\leq c^Tp\}$\;
}
}
\Return ``$K=\varnothing$''
\end{algorithm}
\begin{lema}[de la media elipsoide]
$E(a,A)\cap \{x:c^Tx\leq c^Ta\}$ está contenida en $E' = E(a', A')$ con $a'
= a-\frac{b}{d+1}, A' = \frac{d^2}{d^2-1}\left(A-\frac{2}{d+1}bb^t\right)$
con $b=\frac{Ac}{\sqrt{c^TAc}}$ y $\frac{Vol(E')}{Vol(E)}\leq
e^{\frac{-1}{2d}}$.
\end{lema}
\begin{obs}
Si usamos este método de manera exacta, entonces en la $i$-ésima
iteración, para la elipsoide actual ($E_i$), tenemos
\[\frac{Vol(E_i)}{Vol(E_0)} = \prod_{j = 1}^i\frac{Vol(E_j)}{Vol(E_{j-1}}
\leq e^{\frac{-i}{2d}}\]
Luego, si $i > 2d\ln\left(\frac{Vol(E_0)}{l}\right)$, entonces
$Vol(E_i)< l$. Luego, el algoritmo termina en
$O\left(\ln\left(\frac{Vol(E_0)}{l}\right)\right) =
O\left(d^2\ln\left(\frac{R}{r}\right)\right)$.
\end{obs}
Veamos ahora como reducimos un problema de optimización en un problema de
factibilidad.
Idea 1: Queremos $\min_{x\in K}w^tx$. Podemos revisar $K_v = K\cap \{x:w^Tx\leq
v\}$ y hacer búsqueda binaria en $v$.
Idea 2: Para programación lineal dada por $\min\{w^Tx: Ax\leq b\}$, tenemos que
si $x^*$ es óptimo, entonces existe $y^*$ óptimo para $\max\{b^ty: A^Ty=w,
y\geq 0\}$ tq $w^Tx^* = B^ty^*$. Entonces podemos buscar
$\binom{x}{y}\in\{Ax\leq b, A^Ty = w: y\geq 0, w^Tx c^Ty\}$.
\begin{teo}
Si $K$ es convexo cerrado en $\R^d$, dado por oráculo de separación
polinomial, y $R,r$ son como en las hipótesis, entonces el método de la
elipsoide resuelve factibilidad en $K$ en
$O\left(d^2\ln\left(\frac{R}{r}\right)\right)$ iteraciones.
Además, usando la Idea 1, podemos encontrar $x\in K$ tq $w^Tx^*\leq w^Tx
\leq x^Tx + \epsilon$, donde $x^*$ es mínimo de $\{w^Tx:x\in K\}$, en
tiempo polinomial en $<c>$ y $\frac{1}{\epsilon}$.
\end{teo}
\begin{teo}{Khachiyan}
Sean $P = \{x: Ax\leq b\}$ con $A\in\Z^{m\times d}, b\in\R^m$ y $U$ el
valor absoluto del coeficiente más grande de $A$ y $b$. Luego, el método
elipsoidal resuelve factibilidad en tiempo polinomial en $m,d$ y $\log U$.
Además, si $c\in\Z^d$, podemos optimizar $c^Tx$ en $P$ usando un número
polinomial en $\log(C_{MAX}), d,\log U$ de llamadas al método elipsoidal
que revisa factibilidad.
\end{teo}
\begin{teo}
Sean $S\subseteq\{0,1\}^d$, $P=\conv(S)$ dada por un oráculo de separación
polinomial. Si $P$ es de dimensión completa, entonces podemos encontrar
un vértice óptimo de $P$ para $\min\{c^Tx:x\in P\}$ en tiempo polinomial
usando $O(d^3\log(dc_{MAX})$ trabajo y llamadas al oráculo de separación.
\end{teo}
\end{document}