1 votos

¿Cómo formular el Lagrangiano Aumentado como función objetivo para el problema SOS?

Estoy implementando el algoritmo ADMM para resolver un problema de optimización complejo con restricciones SOS. La actualización de x del algoritmo se ve así:

$$ x^{k+1}= {\arg\min}_{x \in S} \|x-z^{k}+\lambda^{k}\|^2_F$$

donde S es una función indicadora que implica el cumplimiento de algunas restricciones de suma de cuadrados.

Estoy buscando utilizar SOSTools en MATLAB para resolver este problema, pero los programas SOS solo permiten una función objetivo lineal, mientras que en mi caso es cuadrática. Aunque he visto que las personas han resuelto estos problemas en la literatura, estoy un poco perdido. Cualquier ayuda será apreciada.

2voto

domdetre Puntos 91

En primer lugar, parece que estás confundiendo la limitación de la teoría (programación de la suma de cuadrados) y las limitaciones de una herramienta en particular (sostools).

En segundo lugar, sospecho que estás confundiendo cuál es el objetivo del problema original y cuál es el objetivo del programa de suma de cuadrados.

En tercer lugar, ¿realmente comienzas con representaciones de suma de cuadrados del conjunto factible en la variable independiente $x$, o hay algún problema subyacente donde comienzas con una restricción polinómica? Suena extremadamente extraño que tengas una representación de suma de cuadrados de ese conjunto para empezar, ¿y luego quieras elevarlo de nuevo? Espero que signifique que quieres usar la representación de suma de cuadrados de $S$ al minimizar tu objetivo.

De todos modos, aquí tienes una implementación en YALMIP, asumiendo que tienes una representación polinómica de $S$. Ten en cuenta que la optimización polinómica a través de sos requiere que obtengas una representación de suma de cuadrados del problema de optimización, es decir, la función objetivo en tu modelo original no es el objetivo en el modelo de suma de cuadrados, y para cumplir con las restricciones, debes aplicar el positivstellensatz e introducir multiplicadores.

Ejemplo trivial: minimizar $(x-5)^2$ sobre $x^4 + x \leq 1$

 sdpvar x
 sdpvar t
 p = (x-5)^2;
 g = 1 - x - x^4;
 % Multiplicador
 [s,c] = polynomial(x,2);
 % p(x) >= t cuando g(x) >= 0
 Model = [sos(p-t-s*g), sos(s)];
 % Maximizar límite inferior t
 optimize(Model,-t,[],[c;t])
 value(t)

https://yalmip.github.io/tutorial/sumofsquaresprogramming/

Dicho esto, la gente a menudo tiene expectativas demasiado altas de la suma de cuadrados (y no logra ver que típicamente no calcula una solución, sino que solo calcula un límite en el objetivo alcanzable). Para resolver tu problema estándar de optimización polinómica no lineal, generalmente es mucho mejor simplemente usar un solucionador de optimización global.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X