On the convexity of element-wise norm 1 of the inverse

Solution 1:

Here is a counterexample for $n \geq 3$. It is enough to show that $f$ is not convex along a rank-1 direction. Let $x \in \mathbb{R}^n$ with $\lVert x \rVert = 1$ and consider the function $$g(t) = \lVert (I + t xx^T)^{-1} \rVert_1 \,, t \geq 0 \,.$$ By the matrix inversion lemma, $$ (I + t xx^T)^{-1} = I - \frac{t}{1 + t} xx^T \,. $$ Note that the diagonals of the above matrix are non-negative. Then $$ g(t) = n + \alpha \frac{t}{1 + t} \,, $$ where $$ \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 \,. $$ We can choose $x$ so that $\lvert x \rvert_1^2 = n$ and $n > 2$ by assumption. Such a choice yields $g$ that is not convex.

Solution 2:

I'm going to share the work I did on this problem---even though I didn't get a positive result. Perhaps you can work with it.

We can write your problem as follows: $$f(A) = \inf \{ \|B\|_1 \,|\, B=A^{-1} \}$$ Now consider the following modified function: $$\tilde{f}(A) = \inf \{ \|B\|_1 \,|\, B\succeq A^{-1} \} = \inf\{ \|B\|_1 \,|\, B - A^{-1} \in \mathcal{S}^n_+ \}$$ This function is convex. Here's the proof. First, define the following extended-valued function: $$g(A,B) = \begin{cases} \|B\|_1 & A \succ 0, ~ B \succeq A^{-1} \\ +\infty & \text{otherwise} \end{cases}$$ If $g(A,B)$ is convex, then so must be $\tilde{f}$, since partial minimizations of convex functions are convex, and $\tilde{f}(A) = \inf_B g(A,B).$ Clearly, $g$ is convex at points in its domain---but we do not know if the domain is convex, yet: $$\mathop{\textrm{dom}}(g) = \{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,|\, A \succ 0, ~ B \succeq A^{-1} \} = \left\{ (A,B)\in\mathcal{S}^n\times\mathcal{S}^n \,\middle|\, A \succ 0, ~ \begin{bmatrix} B & I \\ I & A \end{bmatrix} \succeq 0 \right\}.$$ This is a convex set, being the intersection of some linear matrix inequalities on $(A,B)$. Therefore, $g$ is convex, and so is $\tilde{f}$.

Now: is $f\equiv \tilde{f}$? It is true for other convex functions on $B$, such as the trace and the determinant: and indeed, both $\mathop{\textrm{Tr}}(A^{-1})$ and $\mathop{\textrm{det}}(A^{-1})$ are convex. But is it true for $\|A^{-1}\|_1$? Before I tried to prove this, I wrote some MATLAB code using CVX, a toolbox I wrote for convex optimization. Here's the code:

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)))) );

Here's some example output:

>> 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. I'm glad I didn't spend any time trying to prove the positive---it is clear that $\tilde{f}\not\equiv f$. I've manually confirmed that the matrix $B$ produced by CVX does indeed satisfy $B\succeq A^{-1}$, and that $\|B\|_1<\|A^{-1}\|_1$. Indeed, the values of $B$ produced by this approach look quite different from $A^{-1}$.

Now I have to say that this shakes any confidence I might have had that your original function, $f$, is convex. That said, I also wrote some simple code to perform convexity tests on pairs of randomly generated PSD matrices, and it failed to find a counterexample. If I think of anything more, I will edit my answer.