Resumen

Investigamos la resolución de programas semidefinidos (SDPs) con un método de punto interior llamado SDP-CUT, que utiliza centros analíticos ponderados y restricciones de planos de corte. SDP-CUT refina iterativamente la región factible para lograr la solución óptima. El algoritmo utiliza el método de Newton para calcular el centro analítico ponderado. Investigamos diferentes técnicas para determinar el tamaño del paso. Descubrimos que el uso del método de Newton con búsqueda de línea exacta es generalmente la mejor implementación del algoritmo. También comparamos nuestro algoritmo con el método SDPT3 y encontramos que SDP-CUT inicialmente se acerca a la solución óptima en menos iteraciones en todos nuestros problemas de prueba. SDP-CUT también requirió menos iteraciones para alcanzar la optimalidad en muchos de los problemas. Sin embargo, SDPT3 requirió menos iteraciones en la mayoría de los problemas de prueba y menos tiempo en todos los problemas. También se discuten algunas propiedades teóricas de la convergencia de SDP-CUT.

• Materias:Modelado matemático Sistemas estocásticos Productos gráficos Ecuaciones matriciales Métodos de descomposición
• Subjects:Mathematical modeling Stochastic systems Graph products Matrix equations Decomposition methods
• Palabras claves:Método del punto interior; SDP-CUT; Centros analíticos ponderados; Restricciones de plano de corte; Método de Newton; Convergencia
• Keywords:Interior point method; SDP-CUT; Weighted analytic centers; Cutting plane constraints; Newton"s method; Convergence