En la convexidad de elemento sabio norma 1 de la inversa de la

Question

Definamos $\|A\|_1$ el elemento sabio norma 1 de una matriz de $A \in \mathbb{R}^{n \times m}$ $$ \|\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviamente, esta función es convexa $\mathbb{R}^{n \times m}$. Es cierto que la función $f:S^n_{++} \longrightarrow \mathbb{R}$, definido como:$f(A) = \|A^{-1}\|_1$, es convexo?

Algunos de observación:

Por desgracia, la inversión de matrices es $S_+$ - convexa, mientras que $\|.\|_1$ es no decreciente con respecto a la cone $R^{n \times m}_+$ y no con respecto al $S_+$ (es fácil encontrar contraejemplos). Por lo tanto teoremas en la combinación de las funciones convexas no son aplicables.

He tratado de formular la función $f$ $max\{ \ trace(M_i A^{-1}) \ \}_{i\in\mathcal{I}}$ cuando la $M_i\in S^n$ vive en una familia de matrices con elementos iguales a 1 o -1, así como para cubrir todas las posibles combinaciones de firmado sumas de los elementos de $A^{-1}$, pero por desgracia no todos los $M_i$ PSD y por lo tanto no todos los $trace(M_i A^{-1})$ son convexas en $A$. Por lo tanto, yo no era capaz de definir $f$ como el pointwise max de las funciones convexas.

También he probado a considerar $$ \|A^{-1}\|_1= \sum_{i,j}=\frac{|\det A_{\hat{\algebra}\hat{\jmath}}|}{detA} $$ donde $\det A_{\hat{\imath}\hat{\jmath}}$ es el menor asociada a la $n-1 \times n-1$ sub-matriz obtenida al eliminar la fila $i$ y la columna $j$$A$. Pero yo no tengo la intuición sobre cómo ir más allá...

Cualquier pensamiento?

Answer 1

Aquí es un contraejemplo para $n \geq 3$. Es suficiente para demostrar que $f$ no es convexa a lo largo de un rango-1 dirección. Deje $x \in \mathbb{R}^n$ $\lVert x \rVert = 1$ y considere la función $$g(t) = \lVert (I + t xx^T)^{-1} \rVert_1 \,, t \geq 0 \,.$$ Por la inversión de la matriz lema, $$ (I + t xx^T)^{-1} = - \frac{t}{1 + t} xx^T \,. $$ Tenga en cuenta que las diagonales de la anterior matriz son no negativos. Entonces $$ g(t) = n + \alpha \frac{t}{1 + t} \,, $$ donde $$ \alpha = -1 + \sum_{i \neq j} \lvert x_i \rvert \lvert x_j \rvert = -2 + \sum_{ij} \lvert x_i \rvert \lvert x_j \rvert = \lvert x \rvert_1^2 - 2 \,. $$ Podemos optar $x$, de modo que $\lvert x \rvert_1^2 = n$ $n > 2$ por supuesto. La elección de los rendimientos de $g$ que no es convexo.

Answer 2

Voy a compartir el trabajo que hice sobre este problema---aunque yo no conseguir un resultado positivo. Tal vez usted puede trabajar con él.

Podemos escribir el problema de la siguiente manera: $$f(A) = \inf \{ \|B\|_1 \,|\, B=A^{-1} \}$$ Ahora considere la siguiente modificación de la función: $$\tilde{f}(A) = \inf \{ \|B\|_1 \,|\, B\succeq A^{-1} \} = \inf\{ \|B\|_1 \,|\, B - A^{-1} \in \mathcal{S}^n_+ \}$$ Esta función es convexa. Aquí está la prueba. En primer lugar, defina los siguientes ampliado valores de la función: $$g(A,B) = \begin{cases} \|B\|_1 & A \succ 0, ~ B \succeq A^{-1} \\ +\infty & \text{otherwise} \end{cases}$$ Si $g(A,B)$ es convexa, entonces así debe de ser $\tilde{f}$, ya que el parcial minimizations de las funciones convexas son convexas, y $\tilde{f}(A) = \inf_B g(A,B).$ Claramente, $g$ es convexa en los puntos de su dominio---pero no sabemos si el dominio es convexa, sin embargo: $$\mathop{\textrm{dom}}(g) = \{ (a,B)\in\mathcal{S}^n\times\mathcal{S}^n \,|\, Un \succ 0, ~ B \succeq A^{-1} \} = \left\{ (a,B)\in\mathcal{S}^n\times\mathcal{S}^n \,\medio|\, Un \succ 0, ~ \begin{bmatrix} B & I \\ I & A \end{bmatrix} \succeq 0 \right\}.$$ Este es un conjunto convexo, siendo la intersección de algunas lineal de la matriz de las desigualdades en $(A,B)$. Por lo tanto, $g$ es convexa, y así es $\tilde{f}$.

Ahora: es $f\equiv \tilde{f}$? Es cierto para otras funciones convexas en $B$, tales como la traza y el determinante: y de hecho, tanto el $\mathop{\textrm{Tr}}(A^{-1})$ $\mathop{\textrm{det}}(A^{-1})$ son convexas. Pero, ¿es cierto para $\|A^{-1}\|_1$? Antes de que yo traté de probar esto, escribí algunas código de MATLAB utilizando CVX, una caja de herramientas que escribí para la optimización convexa. Aquí está el código:

function test_norm1inv( A )
n = size(A,1);
cvx_begin quiet
    variable B(n,n) symmetric
    minimize(sum(sum(abs(B))));
    [B,eye(n);eye(n),A] == semidefinite(2*n)
cvx_end
fprintf( 'CVX result: %g\n', cvx_optval )
fprintf( 'Analytic result: %g\n', sum(sum(abs(inv(A)))) );

Aquí un ejemplo de la salida:

>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 44998.8
Analytic result: 45000.3
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 686.876
Analytic result: 686.889
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 87.0088
Analytic result: 99.938
>> A = randn(10,10); test_norm1inv( A*A' )
CVX result: 82.3252
Analytic result: 96.8455

BZZT. Me alegro de no gastar tiempo tratando de probar el positivo---es claro que la $\tilde{f}\not\equiv f$. He manualmente confirmó que la matriz $B$ producido por la CVX en efecto satisfacer $B\succeq A^{-1}$,$\|B\|_1<\|A^{-1}\|_1$. De hecho, los valores de $B$ producido por este enfoque look bastante diferente de $A^{-1}$.

Ahora tengo que decir que esta sacude la confianza que yo podría haber tenido de que su función original, $f$, es convexa. Dicho esto, yo también escribí un código simple para realizar la convexidad de las pruebas en los pares se generan de forma aleatoria PSD matrices, y no se ha podido encontrar un contraejemplo. Si pienso en nada más, voy a editar mi respuesta.