Optimización de polinomios no negativos

Abstract

La optimización es un campo fundamental en el desarrollo tecnológico actual. Sus herramientas permiten realizar avances en robótica, economía financiera o regresión estadística. Presentamos una nueva perspectiva con la que tratar los problemas de optimización sobre polinomios no negativos, que consisten en minimizar o maximizar imponiendo restricciones equivalentes a que uno o varios polinomios sean no negativos. La formulación sos (sum of squares) ha supuesto un gran avance para este tipo de optimización en los últimos años ya que,como veremos, se puede solventar usando programación semidefinida. En este trabajo, definimos este tipo de programación y estudiamos las cualidades de os polinomios que son suma de cuadrados, así como su relación con los polinomios no negativos. Sin embargo, para problemas con un gran número de variables, la formulación sos se ve limitada y no es capaz de proporcionar una solución. Es por ello que introducimos la optimización dsos y sdsos como alternativa. Se basa en el uso de polinomios de las clases homónimas. Éstos cumplen estar contenidos en la clase sos por lo que perdemos, en principio, región factible y, por tanto, fiabilidad en la solución. Esta pérdida de precisión se compensa ya que veremos que optimizar sobre polinomios dsos y sdsos se puede realizar usando programación lineal y cónica de segundo orden, respectivamente. Esto supone una mejora en eficiencia ya que, si usamos métodos de punto interior, la programación lineal y cónica de segundo orden son menos complejas de resolver que la programación semidefinida. Hablamos de una técnica que nos permite reducir el tiempo de computación significativamente. Además, en algunos casos en los que la programación sos no puede dar una solución, la programación dsos y sdsos sí nos proporciona una.

Optimization is a fundamental field in current technological development. Its tools allow advances in robotics, financial economics or statistical regression. We present a new perspective with which to deal with optimization problems over non-negative polynomials. These problems consist of minimizing or maximizing while imposing restrictions equivalent to one or several polynomials being non-negative. Sos (sum of squares) optimization has made important progress in this area because, as we will see, it can be solved using semidefinite programming. In this paper, we introduce this type of programming and study the characteristics of sos polynomials, as well as their relationship with non-negative polynomials. However, for problems with a large number of variables, sos formulation is limited and is not able to provide a solution. That is why we present the dsos and sdsos optimization as an alternative. It is based on the use of polynomials of homonymous classes. These are contained in the sos polynomials set so we lose, in principle, feasible region and, therefore, reliability in the solution. This loss of precision is compensated since, as we will see, optimizing on dsos and sdsos polynomials can be done using linear and second order conic programming , respectively. This means that we are improving the efficiency since linear and second order conic programming are less complex to solve than semidefinite programming, if we use interior point methods. We are talking about a technique that allows us to reduce computing time significantly. Also, in some cases in which sos programming can not give a solution, dsos and sdsos programming does provides one.