Estudio comparativo entre el método de Lemke y el método de los conjuntos activos para programación cuadrática / Comparative study between Lemke’s method and the active set method for quadratic programming

Resumen

En este trabajo se presentan dos métodos para resolver el problema general de programación cuadrática convexa con restricciones de igualdad y desigualdad. Uno es el método de los conjuntos activos y el otro es el de Lemke. Se realizaron varias pruebas variando el tamaño del problema y el número de restricciones de igualdad y desigualdad, mostrando que el método de los conjuntos activos es eficiente cuando el problema tiene un alto nú- mero de restricciones de igualdad, pero resulta lento cuando existe un alto número de restricciones de desigualdad. Mientras que el algoritmo de Lemke resultó eficiente en problemas cuadráticos convexos con un alto número de restricciones de desigualdad.

Abstract

In this paper, we present two different methods in order to solve a general convex quadratic programming problem with equality and inequality constraints: a pivot method (Lemke’s algorithm) and the most used method, the strategies of active set. Active set method is efficient when the problem has many equality constraints, but it is inefficient when the problem has many inequalities constraints. In the search for a strategy that offers a best time of response for this kind of problems, we studied into the pivots methods, Lemke’s algorithm. We provide numerical simulations and comparative results that show the Lemke’s method is effective on problems with a large number of inequality constraints.