Editing Openai/693e3ce6-229c-8008-97dc-ab720cb1f95a (section)

==== Paste the following exactly where the stationarity lemma used to be: ====

<syntaxhighlight lang="latex">\begin{lemma}[Absolute-value improvement and nonnegativity]\label{lem:abs_improvement_nonneg}
Assume $v\in C$ so that $b_C\ge 0$ and $b_{\bar C}=0$.
Then for every $x$ with $x_{\bar C}=0$, the componentwise absolute value $|x|$ satisfies
\[
F(|x|)\le F(x).
\]
Consequently, the restricted minimizer $\hat x$ satisfies $\hat x_C\ge 0$ componentwise.
\end{lemma}

\begin{proof}
Fix any $x$ with $x_{\bar C}=0$ and set $y:=|x|$ (so $y_{\bar C}=0$).
Write
\[
F(x)=\frac12 x^\top Qx - b^\top x + \sum_{i=1}^n \lambda_i|x_i|.
\]

\emph{Quadratic term.}
Since $Q=\frac{1+\alpha}{2}I-\frac{1-\alpha}{2}D^{-1/2}AD^{-1/2}$, we have $Q_{ij}\le 0$ for $i\neq j$.
Expand
\[
x^\top Qx = \sum_i Q_{ii}x_i^2 + 2\sum_{i<j}Q_{ij}x_i x_j.
\]
For each $i<j$, $x_i x_j\le |x_i||x_j|=y_i y_j$, and since $Q_{ij}\le 0$ this implies
$Q_{ij}x_i x_j \ge Q_{ij}y_i y_j$.
Hence $x^\top Qx \ge y^\top Qy$.

\emph{Linear term.}
Since $b\ge 0$ (here $b=\alpha D^{-1/2}s$ with $s=e_v$) and $y_i=|x_i|\ge x_i$ for all $i$,
we have $-b^\top y \le -b^\top x$.

\emph{$\ell_1$ term.}
$\sum_i \lambda_i|y_i|=\sum_i\lambda_i|x_i|$ by definition.

Combining the three comparisons gives $F(y)\le F(x)$.
Now let $\hat x$ be the unique restricted minimizer. Then $F(|\hat x|)\le F(\hat x)$, so $|\hat x|$ is also a minimizer.
By uniqueness, $|\hat x|=\hat x$, hence $\hat x_C\ge 0$.
\end{proof}

\begin{lemma}[Restricted KKT on $C$]\label{lem:restricted_KKT_on_C}
There exists a vector $z_C\in\mathbb{R}^{|C|}$ such that
\begin{equation}\label{eq:restricted_KKT_on_C}
Q_{CC}\hat x_C - b_C + z_C = 0,
\end{equation}
and for every $i\in C$,
\begin{equation}\label{eq:zC_in_subdiff}
z_{C,i}\in \lambda_i\,\partial|\hat x_i| \subseteq [-\lambda_i,\lambda_i].
\end{equation}
In particular, $\|z_C\|_2 \le \|\lambda_C\|_2 = \rho\alpha\sqrt{\mathrm{vol}(C)}$.
\end{lemma}

\begin{proof}
The restricted objective over $x_C$ is strongly convex because $Q_{CC}\succ 0$ and the $\ell_1$ term is convex,
so $\hat x_C$ is unique. First-order optimality yields
\[
0\in Q_{CC}\hat x_C - b_C + \partial\!\Big(\sum_{i\in C}\lambda_i|\hat x_i|\Big),
\]
which is exactly the existence of $z_C$ satisfying \eqref{eq:restricted_KKT_on_C}--\eqref{eq:zC_in_subdiff}.
The norm bound follows from $|z_{C,i}|\le \lambda_i$ and
$\|\lambda_C\|_2^2=\sum_{i\in C}(\rho\alpha\sqrt{d_i})^2=(\rho\alpha)^2\mathrm{vol}(C)$.
\end{proof}

</syntaxhighlight>