Sesión Análisis Numérico y Optimización

Diciembre 13, 11:20 ~ 11:40

Cotas a priori para la aproximación de problemas de transporte óptimo

Frungillo, Maximiliano

Dados $(X, d_X, \mu)$ e $(Y, d_Y, \nu)$ espacios métricos junto con medidas borelianas de probabilidad en ellos, para cada función de costo $c:X\times Y \to \mathbb{R}$ el \emph{problema de Monge} consiste en hallar una función $T:X\to Y$ que transporte $\mu$ en $\nu$ con el menor costo posible. Si $T_\# \mu$ denota el pushforward de $\mu$ por $T$, resolver el problema de Monge es hallar un minimizante de \begin{equation*} \inf_{T \,:\, T_\# \mu = \nu}{\int_{X}{c(x,T(x)) \, d\mu(x)}} \label{problema_monge_mfrungillo} \, . \end{equation*} Se conoce como \emph{problema de Kantorovich} a la relajación del problema de Monge dada por \begin{align} \inf_{\pi \in \mathcal{A}(\mu,\nu)}{\int_{X \times Y}{c(x,y) \, d\pi(x,y)}}\label{problema_kantorovich_mfrungillo}\, , \end{align} donde $\mathcal{A}(\mu,\nu)$ denota el conjunto de medidas en $X\times Y$ con marginales $\mu$ y $\nu$ en ese orden. Cuando $\mu$ y $\nu$ son medidas finitamente soportadas, el problema (\ref{problema_kantorovich_mfrungillo}) se reduce a un problema de programación lineal finita con una estructura particular, admitiendo algoritmos eficientes tanto exactos como aproximados \cite{ahuja2015_mfrungillo, oberman2015_mfrungillo, schmitzer2016_mfrungillo, rigollet2017_mfrungillo}. En este trabajo estudiamos el error de aproximación cometido cuando (\ref{problema_kantorovich_mfrungillo}) se discretiza aproximando las medidas $\mu$ y $\nu$ por medidas finitamente soportadas. En particular, obtenemos cotas a priori para el error de aproximación del valor óptimo de (\ref{problema_kantorovich_mfrungillo}) mediante una técnica de refinamiento de soluciones. Como corolario de estas cotas de error se obtienen cotas de complejidad para $\varepsilon$--aproximar el problema (\ref{problema_kantorovich_mfrungillo}) bajo hipótesis generales, a condición de tener algún control sobre las dimensiones de $X$ e $Y$ y la continuidad de $c$. \vspace{10pt} \begingroup \renewcommand{\section}[2]{\noindent{\sc Referencias}} \begin{thebibliography}{} \bibitem{villani2003topics_mfrungillo} Villani, C., \emph{Topics in Optimal Transportation}. American Mathematical Soc., 2003. \bibitem{ahuja2015_mfrungillo} Ahuja, R., Magnanti, T., Orlin, J. \emph{Network flows: theory, algorithms, and applications}. Prentice Hall, 1993. \bibitem{oberman2015_mfrungillo} Oberman, A., Ruan, Y., An efficient linear programming method for Optimal Transportation. arXiv preprint arXiv:1509.03668, 2015. \bibitem{schmitzer2016_mfrungillo} Schmitzer, B., A Sparse Multiscale Algorithm for Dense Optimal Transport. \emph{Journal of Mathematical Imaging and Vision}, 2016, 56(2), 238-259. \bibitem{rigollet2017_mfrungillo} Altschuler, J., Rigollet, P., Weed, J., Near-linear time approximation algorithms for Optimal Transport via Sinkhorn iteration. arXiv preprint arXiv:1705.09634, 2017. \end{thebibliography} \endgroup

Autores: Frungillo, Maximiliano.