Publication: Herramientas de optimización convexa y aplicaciones de telecomunicaciones
Loading...
Identifiers
Publication date
2011
Defense date
2011-09-06
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
En las últimas décadas se han producido resultados fundamentales en teoría de optimización convexa y su utilización práctica. La comunidad de ingenieros no sólo se ha beneficiado de estos avances al encontrar aplicaciones prácticas, sino que también ha contribuido en agilizar el desarrollo matemático de la teoría y de algoritmos eficientes. Esto se ha traducido en la creación y comercialización de una gran cantidad de herramientas que permiten resolver problemas de grandes dimensiones con mucha precisión y rapidez. Frente a toda esta diversidad de opciones a la hora de escoger una u otra herramienta, este trabajo ofrece un recorrido por las técnicas más utilizadas y los programas que permiten la resolución de este tipo de problemas. El motivo de estudiar en particular la optimización convexa es la altísima eficiencia que podemos obtener en su resolución, en comparación con problemas no convexos. Tradicionalmente se hacía una distinción entre problemas lineales y no lineales para delimitar la condición de fácil o difícil de resolver, pero en realidad esta frontera se encuentra en su naturaleza convexa o no convexa. Cuando un problema es convexo, se puede resolver de forma óptima bien con una solución cerrada por medio de las condiciones derivadas de la dualidad de Lagrange, o bien de forma numérica con algoritmos muy eficientes. Como consecuencia, una vez que hemos expresado un problema en forma convexa podemos decir que está resuelto. El principal objetivo de este trabajo es la exposición de los recursos de optimización convexa más importantes que puede encontrar un ingeniero de telecomunicación para resolver diferentes problemas en su ámbito de trabajo. Estos recursos se materializan en los algoritmos existentes y los programas disponibles en el mercado que los utilizan. Para conocerlos en detalle comenzamos con los fundamentos teóricos básicos que se presentan en la primera parte de esta memoria, y a continuación se revisan los programas más relevantes que un usuario puede adquirir; por último se estudian dos casos de aplicación en los que se ponen en práctica todos principios aprendidos hasta aquí. La primera parte de este trabajo contiene el marco teórico que nos permite transformar el planteamiento de diferentes problemas para desvelar su carácter convexo de forma que lo podamos resolver con los algoritmos y programas disponibles. Por desgracia, la mayoría de los problemas de ingeniería no son directamente convexos tal como se formulan inicialmente, aunque muchos de ellos contienen una convexidad oculta que tendremos que descubrir para ser capaces de utilizar toda la maquinaria disponible de optimización convexa. En la segunda parte se examinan los principales programas de optimización convexa. En ella se ponen de manifiesto las características principales de un conjunto de herramientas seleccionadas por su relevancia en el mercado. Analizaremos factores como su complejidad o facilidad de uso, los algoritmos y técnicas que implementan, o la forma en que se pueden adquirir. Dejaremos patente la diferencia entre herramientas de resolución o solvers y de modelado, y veremos cómo las primeras forman parte del núcleo de las segundas, siendo los solvers los encargados de proporcionar la ejecución de los algoritmos de minimización, mientras que los sistemas de modelado sirven como lenguaje con el que el usuario describe las funciones y restricciones del problema en un formato matemático más intuitivo que en los anteriores. En la tercera parte veremos dos ejemplos de aplicación en telecomunicaciones en los que se utilizan herramientas de optimización convexa, y que nos sirven para consolidar las ideas y los datos de los capítulos anteriores. El primero es un conformador de haz robusto en el que se tienen en cuenta las variaciones del vector de apuntamiento para que estas no perjudiquen la calidad del receptor. En este ejemplo se consigue replicar los resultados de la bibliografía consultada y poner en relieve algunos aspectos de la naturaleza del problema que no había detectado antes de la implementación, por ejemplo la importancia del tamaño asignado a la región de incertidumbre y los valores que hacen inviable el problema. Los resultados muestran una comparativa en el comportamiento de distintas herramientas de optimización y en especial se comprueba la gran ventaja en rendimiento que ofrecen los programas de optimización convexa con respecto a los que están orientados a optimización global (no convexa). La segunda aplicación consiste en optimizar el diseño del precodificador lineal en sistemas MIMO-OFDM en función de dos criterios: minimizar el error cuadrático medio de los flujos de datos transmitidos, o maximizar la información mutua del sistema. En ambos casos se aplica una restricción de control de potencia para reducir las variaciones de nivel de la señal OFDM. Se implementan dos modelos de optimización: un esquema no cooperativo en el que cada portadora se considera como un canal independiente, y un esquema cooperativo en el que el conjunto completo de portadoras constituye un solo canal que agrupa a todos y la optimización permite la distribución óptima de información entre distintas portadoras. En este segundo ejemplo únicamente he utilizado herramientas de optimización convexa debido a la diferencia de fiabilidad demostrada en el primer caso práctico. ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Several paramount results in convex optimization theory and its practical use have taken place over the last few decades. The engineering community not only has benefited from these recent advances by finding practical applications, but has also contributed to speeding up the mathematical development of both the theory and efficient algorithms. This has resulted in the creation and marketing of a great deal of tools that allow us to solve high dimensional problems very fast and accurately. Given all this diversity of options when it comes to choosing one tool or another, this work presents a survey of the most frequently used techniques and the programs that make possible the resolution of this kind of problems. The reason of focusing on convex optimization in particular is the extremely high solving efficiency that can be achieved, compared to non convex problems. Traditionaly, a distinction between linear and non linear problems used to be made to mark the difference between easy and hard to solve problems, but the actual watershed is their convexity or non convexity. When a problem is found to be convex, it can be efficiently solved either with a closed solution by means of Lagrange duality and its derivative conditions, or numerically with very powerful algorithms. As a consequence, once a problem is stated in convex form we can consider it solved. The main goal of this work is to present the most important resources in convex optimization that a telecommunication engineer may use to solve different problems within his/her professional field. These resources arise as existing algorithms and available programs in the market that use them. In order to get acquainted with them, we start with the basic theoretical foundations which are introduced in the first part of this report, and afterwards, the most relevant programs a user can get are examined; finally, two application cases are studied where all the principles that we have learned so far are put into practice. The first part of this work comprises the theoretical framework that allows us to transform the approach to different problems in order to reveal their convexity and thus to be able to solve them with available algorithms and programs. Unfortunately, most engineering problems are not convex as they are initially stated; although many of them keep a hidden convexity that we will have to discover if we want to be able to use all the available convex optimization machinery. In the second part, the main convex optimization software packages are examined. The foremost features of a set of tools selected by their relevance in the market are highlighted therein. We will analyze factors like their complexity or simplicity in use, implemented algorithms and techniques, or the way they can be acquired. We will shed some light on the difference between solvers and modeling systems, and we will see how the former is part of the core of the latter, where solvers are in charge of providing the execution of the minimization algorithms, whereas modeling systems serve as a descriptive languaje for the user to formulate the problem functions and constraints in a more intuitive format than the one used by the solvers. In the third part we will see two application cases in telecommunications where convex optimization tools are used. These will consolidate all the ideas and data from the previous chapters. The first one is a robust beamformer where variations in the steering vector are taken into account in order to keep them from damaging the receiver’s quality. In this example the results of the bibliography I looked up are successfully replicated, and several features of the underlying nature of the problem which I had not detected before the implementation are highlighted, for instance, the importance of the size assigned to the uncertainty region, and the values that make the problem unfeasible. The results show a comparative in the behaviour of different optimization tools, and the big advantage in throughput offered by convex optimization packages with respect to those oriented to (nonconvex) global optimization is specially noticed. The second application consists on the design optimization of a linear precoder in MIMO-OFDM systems as a function of two criteria: minimizing the mean square error of the transmitted data streams, or maximizing the system mutual information. Either way, a power control constraint is applied to reduce the OFDM signal level variations. Two optimization models are implemented: a non-cooperative scheme where each carrier is considered as an independent channel, and a cooperative strategy where the full set of carriers is considered as a single channel spanning all of them, and the optimization allows the optimal distribution of information among different carriers. In this second example I have only used convex optimization tools due to the difference in reliability shown in the first practical case.
Several paramount results in convex optimization theory and its practical use have taken place over the last few decades. The engineering community not only has benefited from these recent advances by finding practical applications, but has also contributed to speeding up the mathematical development of both the theory and efficient algorithms. This has resulted in the creation and marketing of a great deal of tools that allow us to solve high dimensional problems very fast and accurately. Given all this diversity of options when it comes to choosing one tool or another, this work presents a survey of the most frequently used techniques and the programs that make possible the resolution of this kind of problems. The reason of focusing on convex optimization in particular is the extremely high solving efficiency that can be achieved, compared to non convex problems. Traditionaly, a distinction between linear and non linear problems used to be made to mark the difference between easy and hard to solve problems, but the actual watershed is their convexity or non convexity. When a problem is found to be convex, it can be efficiently solved either with a closed solution by means of Lagrange duality and its derivative conditions, or numerically with very powerful algorithms. As a consequence, once a problem is stated in convex form we can consider it solved. The main goal of this work is to present the most important resources in convex optimization that a telecommunication engineer may use to solve different problems within his/her professional field. These resources arise as existing algorithms and available programs in the market that use them. In order to get acquainted with them, we start with the basic theoretical foundations which are introduced in the first part of this report, and afterwards, the most relevant programs a user can get are examined; finally, two application cases are studied where all the principles that we have learned so far are put into practice. The first part of this work comprises the theoretical framework that allows us to transform the approach to different problems in order to reveal their convexity and thus to be able to solve them with available algorithms and programs. Unfortunately, most engineering problems are not convex as they are initially stated; although many of them keep a hidden convexity that we will have to discover if we want to be able to use all the available convex optimization machinery. In the second part, the main convex optimization software packages are examined. The foremost features of a set of tools selected by their relevance in the market are highlighted therein. We will analyze factors like their complexity or simplicity in use, implemented algorithms and techniques, or the way they can be acquired. We will shed some light on the difference between solvers and modeling systems, and we will see how the former is part of the core of the latter, where solvers are in charge of providing the execution of the minimization algorithms, whereas modeling systems serve as a descriptive languaje for the user to formulate the problem functions and constraints in a more intuitive format than the one used by the solvers. In the third part we will see two application cases in telecommunications where convex optimization tools are used. These will consolidate all the ideas and data from the previous chapters. The first one is a robust beamformer where variations in the steering vector are taken into account in order to keep them from damaging the receiver’s quality. In this example the results of the bibliography I looked up are successfully replicated, and several features of the underlying nature of the problem which I had not detected before the implementation are highlighted, for instance, the importance of the size assigned to the uncertainty region, and the values that make the problem unfeasible. The results show a comparative in the behaviour of different optimization tools, and the big advantage in throughput offered by convex optimization packages with respect to those oriented to (nonconvex) global optimization is specially noticed. The second application consists on the design optimization of a linear precoder in MIMO-OFDM systems as a function of two criteria: minimizing the mean square error of the transmitted data streams, or maximizing the system mutual information. Either way, a power control constraint is applied to reduce the OFDM signal level variations. Two optimization models are implemented: a non-cooperative scheme where each carrier is considered as an independent channel, and a cooperative strategy where the full set of carriers is considered as a single channel spanning all of them, and the optimization allows the optimal distribution of information among different carriers. In this second example I have only used convex optimization tools due to the difference in reliability shown in the first practical case.
Description
Keywords
Optimización convexa, Telecomunicaciones