Thesis:

On the polyhedral outer-approximation of convex functions with unbounded domains

Computing polyhedral outer-approximation (POA) of convex functions with unbounded domains and uniformly bounded pointwise error suffices to ensure the boundedness of convex MINLP linearizations. This thesis provides apparently new theoretical results that link functional and geometrical properties of a convex function and the finiteness of the error of a given approximation. Furthermore, a cutting-plane algorithm is developed to globally reduce the error of a POA as much as desired. The algorithm is proven correct, and in a series of numerical tests it is confirmed the convergence under reasonable times. Under mild assumptions, it is shown that the approximations developed in this work possesses sufficient properties to ensure that linearizations of convex MINLP are bounded.

Para asegurar que las linealizaciones de problemas MINLP convexos sean acotadas, es suficiente con computar aproximaciones poliedrales externas (POA) de funciones convexas con dominios no acotados, con un error puntual uniformemente acotado. En esta tesis, se presentan resultados teóricos aparentemente nuevos, que conectan propiedades funcionales y geométricas de una función convexa con la finitud del error de alguna aproximación dada. Más aún, se desarrolla un algoritmo de planos cortantes para reducir, tanto como se desee, globalmente el error de una POA. Se prueba la correctitud del algoritmo y se confirma su convergencia en una serie de experimentos numéricos que terminaron en tiempos razonables. Bajo condiciones razonables, se demuestra que las aproximaciones desarrolladas en este trabajo poseen propiedades suficientes para garantizar que las linealizaciones de problemas MINLP convexos sean acotadas.