Problema de optimización de valores propios/definición positiva de la matriz

Question

Me he encontrado con un problema de optimización matricial a partir de un sistema de EDO's, sin embargo no estoy muy familiarizado con la optimización.

Dejemos que $A(\lambda)$ ser un $4 \times 4$ matriz dependiente de un valor $\lambda >0$ (algunas entradas son constantes, otras son múltiplos escalares de $\lambda$ ) donde mi objetivo es maximizar este valor de $\lambda$ . Sin embargo, hay algunas limitaciones adicionales:

1. la parte simétrica de la matriz el producto de la matriz $-CA(\lambda)$ es positiva definida (o equiv. valores propios estrictamente positivos). Donde la parte simétrica se define como $M_{symmetric} = \frac{1}{2}(M+M^{T})$

2. $C$ simétrico

3. $C$ conserva el signo (no negativo)

Aquí $C$ es un $4 \times 4$ que debe ser elegida libremente siempre que satisfaga estas restricciones (el objetivo es encontrar una elección inteligente de $C$ maximizando este valor de $\lambda$ ).

He hecho este trabajo para $A$ a $2 \times 2$ en Mathematica (sólo 3 variables en $C$ utilizando NMaximize[]). Sin embargo, para grandes $C$ esto ya no funciona. ¿Existe algún software para solucionar este problema? ¿Conocen problemas similares con pasos conocidos a seguir? ¡Cualquier orientación en la dirección sería muy bienvenida!

Answer 1

Parece que se trata de un problema de desigualdad matricial bilineal (IMC), que no es convexo y es difícil. Se trata de una IMC, en lugar de una IML (desigualdad matricial lineal) más sencilla, debido al producto de las variables $C$ y $\lambda$ . Puede formularse e intentar resolverse con un solucionador compatible con el IMC, como PENLAB (gratuito) o PENBMI (mejor, pero no gratuito), que puede utilizarse con YALMUP (bajo MATLAB). La formulación no es tan difícil, pero la solución puede serlo.

El código de YALMIP es algo así como

C = sdpvar(4,4); % symmetric matric variable by default
lambda = sdpvar; % scalar variable
A = ...  supply the code to build up A from lambda
Constraints = [lambda >= 0, C(:) >= 0, -C*A-A'*C - min_eig*eye(4) >= 0];
optimize(Constraints,-lambda,sdpsettings('solver','penlab'))

donde min_eig se elige como un número positivo pequeño (valor propio mínimo de -C*A-A'*C para garantizar la definición positiva estricta).

Dado que se trata de un difícil problema no lineal y no convexo, proporcionar un valor inicial no predeterminado para C y lambda podría ayudar mucho. Eso puede hacerse con el comando assign de YALMIP y 'usex0',1 en sdpsettings. En el mejor de los casos se obtendrá un óptimo local, que puede no ser globalmente óptimo, El óptimo local obtenido puede depender del valor inicial.

Editar : En realidad, usted podría intentar obtener una solución globalmente óptima, pero podría no tener éxito, utilizando el solucionador de optimización global BMIBNB de YALMUIP, usando PENLAB (o mejor aún, PENBMI) como solucionador superior (es decir, para resolver problemas de optimización local generados por BMIBNB). Cambie el comando de optimización a

optimize(Constraints,lambda,sdpsettings('solver','bmibnb','bmibnb.uppersolver','penlab'))

o mejor aún, especificar penbmi en lugar de penlab, si penbmi está disponible.

Incluso si BMIBNB no consigue encontrar la solución globalmente óptima (dentro de cierta tolerancia), puede encontrar una solución lcalmente óptima tan buena, o posiblemente mejor, que la que se habría encontrado si sólo se hubiera utilizado penlab 9o penbmi) como solucionador local.