The all-entry graphical-lasso objective has a unique KKT optimizer

By the all-entry objective definition [F1] and the nonnegative-operator factorization [F2], write $S=R^{T}R$. Thus $\mathrm{tr}(S\mathrm{\Theta })=\mathrm{tr}(R\mathrm{\Theta }{R}^T)\ge 0$ for $\mathrm{\Theta }\succ 0$. Also $\mathrm{\parallel }\mathrm{\Theta }{\mathrm{\parallel }}_1={\sum }_{i,j}\mathrm{\mid }{\mathrm{\Theta }}_{ij}\mathrm{\mid }\ge {\sum }_i{\mathrm{\Theta }}_{ii}=\mathrm{tr}\mathrm{\Theta }$, since positive-definite matrices have positive diagonal entries.

The cone ${\mathbb{S}}_{++}^p$ is open and convex: positive quadratic forms remain positive under sufficiently small symmetric perturbations, and convex combinations of positive quadratic forms remain positive. For symmetric $H$, determinant expansion gives ${\frac{d}{dt}\log \det (\mathrm{\Theta }+tH)\mid }_{t=0}=\mathrm{tr}({\mathrm{\Theta }}^{-1}H)$. Differentiating $(\mathrm{\Theta }+tH)(\mathrm{\Theta }+tH{)}^{-1}=I$ gives ${\frac{d}{dt}(\mathrm{\Theta }+tH{)}^{-1}\mid }_{t=0}=-{\mathrm{\Theta }}^{-1}H{\mathrm{\Theta }}^{-1}$, so the second directional derivative is $-\mathrm{tr}({\mathrm{\Theta }}^{-1}H{\mathrm{\Theta }}^{-1}H)$.

By [F3], the eigenvalues $t_1,\dots ,t_p$ of $\mathrm{\Theta }\succ 0$ are positive and $\log \det \mathrm{\Theta }={\sum }_k\log t_k$, $\mathrm{tr}\mathrm{\Theta }={\sum }_k{t}_k$. Hence $F_{S,\lambda }(\mathrm{\Theta })\le {\sum }_{k=1}^{p}h(t_k)$ for $h(t)=\log t-\lambda t$. The function $h$ is bounded above and tends to $-\mathrm{\infty }$ as $t\downarrow 0$ or $t\to \mathrm{\infty }$. For any $c$, the upper level set $F_{S,\lambda }(\mathrm{\Theta })\ge c$ therefore forces each eigenvalue into a compact interval $[a_c,b_c]\subset (0,\mathrm{\infty })$: if $M={\sup }_{t>0}h(t)$, then each $h(t_k)\ge c-(p-1)M$. These matrices form a closed bounded set of symmetric matrices contained in ${\mathbb{S}}_{++}^p$, hence a compact set. Taking $c=F_{S,\lambda }(I)$ gives a nonempty compact upper level set, and continuity of $F$ yields a maximizer.

Let $B={\mathrm{\Theta }}^{-1\mathrm{/}2}H{\mathrm{\Theta }}^{-1\mathrm{/}2}$, using the positive square root from the orthonormal eigenbasis [F3]. Then $B$ is symmetric and $\mathrm{tr}({\mathrm{\Theta }}^{-1}H{\mathrm{\Theta }}^{-1}H)=\mathrm{tr}(B^2)=\mathrm{\parallel }B{\mathrm{\parallel }}_F^2$, strictly positive when $H\mathrm{\ne }0$. Thus the second derivative of $\log \det$ along every nonconstant segment is strictly negative, giving its strict chord inequality. The Hessian of $-\log \det$ is positive semidefinite by step 1.2, so [F4] gives convexity in the chord sense of [F5]. The trace term is linear and the entrywise ${\mathrm{\ell }}^1$ norm is convex by the triangle inequality, so its negative is concave; adding these terms preserves the strict chord inequality. Hence $F_{S,\lambda }$ is strictly concave on its open convex domain.

Put $G={\mathrm{\Theta }}^{-1}-S$. At a maximizer every feasible one-coordinate directional derivative is at most zero, and when the objective is differentiable in both directions its derivative is zero. Since ${\mathrm{\Theta }}_{ii}>0$, the diagonal penalty is locally differentiable with slope $1$, so the diagonal equation is $G_{ii}-\lambda =0$ and ${\mathrm{\Gamma }}_{ii}=1$. For $i<j$, a symmetric perturbation by $t(E_{ij}+E_{ji})$ has smooth derivative $2G_{ij}t$ and changes the penalty by $2\lambda (\mathrm{\mid }{\mathrm{\Theta }}_{ij}+t\mathrm{\mid }-\mathrm{\mid }{\mathrm{\Theta }}_{ij}\mathrm{\mid })$. If ${\mathrm{\Theta }}_{ij}\mathrm{\ne }0$, testing both signs of small $t$ gives $G_{ij}=\lambda \mathrm{sign}({\mathrm{\Theta }}_{ij})$. If ${\mathrm{\Theta }}_{ij}=0$, taking $t>0$ gives $G_{ij}\le \lambda$ and taking $t<0$ gives $G_{ij}\ge -\lambda$. Defining ${\mathrm{\Gamma }}_{ij}={\mathrm{\Gamma }}_{ji}=G_{ij}\mathrm{/}\lambda$ at zero and the sign otherwise yields the stated KKT equation for the all-entry penalty [F1].

Conversely, suppose $\mathrm{\Theta }\succ 0$ and a symmetric $\mathrm{\Gamma }$ satisfies the stated entrywise conditions and ${\mathrm{\Theta }}^{-1}-S-\lambda \mathrm{\Gamma }=0$. Put $T={\mathrm{\Theta }}^{-1\mathrm{/}2}{\mathrm{\Theta }}^{\mathrm{\prime }}{\mathrm{\Theta }}^{-1\mathrm{/}2}$ for any ${\mathrm{\Theta }}^{\mathrm{\prime }}\succ 0$; its eigenvalues $t_r$ are positive. Since $\log t\le t-1$ for $t>0$ (the function $t-1-\log t$ has its minimum $0$ at $t=1$), $\log \det {\mathrm{\Theta }}^{\mathrm{\prime }}-\log \det \mathrm{\Theta }={\sum }_r\log t_r\le \mathrm{tr}(T)-p=\mathrm{tr}({\mathrm{\Theta }}^{-1}({\mathrm{\Theta }}^{\mathrm{\prime }}-\mathrm{\Theta }))$. For each scalar $x$ and each allowed subgradient $\gamma$ of $\mathrm{\mid }x\mathrm{\mid }$, $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{\mid }x\mathrm{\mid }+\gamma (y-x)$: if $x\mathrm{\ne }0$, this follows from $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{sign}(x)y$, while for $x=0$ it follows from $\mathrm{\mid }\gamma \mathrm{\mid }\le 1$. Summing gives $\mathrm{\parallel }{\mathrm{\Theta }}^{\mathrm{\prime }}{\mathrm{\parallel }}_1\ge \mathrm{\parallel }\mathrm{\Theta }{\mathrm{\parallel }}_1+{\sum }_{i,j}{\mathrm{\Gamma }}_{ij}({\mathrm{\Theta }}_{ij}^{\mathrm{\prime }}-{\mathrm{\Theta }}_{ij})$ for the all-entry objective [F1]. Combining these bounds with the linear trace term and the KKT equation yields $F_{S,\lambda }({\mathrm{\Theta }}^{\mathrm{\prime }})-F_{S,\lambda }(\mathrm{\Theta })\le \mathrm{tr}(({\mathrm{\Theta }}^{-1}-S-\lambda \mathrm{\Gamma })({\mathrm{\Theta }}^{\mathrm{\prime }}-\mathrm{\Theta }))=0$. Thus every such KKT point is a maximizer. The maximizer exists by step 2.1 and is unique by strict concavity from step 2.2, so the KKT condition is both necessary and sufficient for that unique optimum.