[proofplan]
The proof translates optimality into a subgradient condition. First, Fermat's rule for convex functions identifies minimizers of $F$ with the inclusion $0 \in \partial F(x^*)$. The relative-interior qualification permits the exact subdifferential formula $\partial F(x^*)=\partial f(x^*)+A^\top\partial g(Ax^*)$. The desired multiplier $y^*$ is exactly the element of $\partial g(Ax^*)$ whose image under $A^\top$ cancels a subgradient of $f$.
[/proofplan]
[step:Translate minimization into the zero subgradient condition]
Let $x^* \in \mathbb{R}^n$. Since $f$ and $g$ are proper convex functions and the qualification condition gives a point $\bar{x} \in \operatorname{dom} f$ with $A\bar{x} \in \operatorname{dom} g$, the function $F$ is proper convex. By Fermat's rule for convex subdifferentials, $x^*$ minimizes $F$ over $\mathbb{R}^n$ if and only if
\begin{align*}
0 \in \partial F(x^*).
\end{align*}
Indeed, if $0 \in \partial F(x^*)$, then the definition of the convex subdifferential gives, for every $x \in \mathbb{R}^n$,
\begin{align*}
F(x) \geq F(x^*) + 0\cdot (x-x^*) = F(x^*),
\end{align*}
so $x^*$ minimizes $F$. Conversely, if $x^*$ minimizes $F$, then $F(x) \geq F(x^*)$ for every $x \in \mathbb{R}^n$, which is precisely the subgradient inequality for $0 \in \partial F(x^*)$.
[guided]
We first reduce the theorem to a statement about subgradients. The function
\begin{align*}
F: \mathbb{R}^n \to (-\infty,\infty]
\end{align*}
is defined by $F(x)=f(x)+g(Ax)$. Because $f$ and $g$ are convex and $A$ is linear, the composition $g\circ A$ is convex, and hence $F$ is convex. The qualification condition gives a point $\bar{x} \in \operatorname{ri}(\operatorname{dom} f)$ such that $A\bar{x} \in \operatorname{ri}(\operatorname{dom} g)$; in particular, $\bar{x}\in\operatorname{dom} f$ and $A\bar{x}\in\operatorname{dom} g$, so $F(\bar{x})<\infty$. Thus $F$ is proper.
For a proper convex function $h:\mathbb{R}^n\to(-\infty,\infty]$, Fermat's rule says that $x^*$ minimizes $h$ if and only if $0\in\partial h(x^*)$. Here this rule is immediate from the definition of the subdifferential. Applying the definition to $h=F$, the inclusion $0\in\partial F(x^*)$ means that for every $x\in\mathbb{R}^n$,
\begin{align*}
F(x)\geq F(x^*)+0\cdot (x-x^*)=F(x^*).
\end{align*}
This is exactly the assertion that $x^*$ is a global minimizer of $F$.
Conversely, if $x^*$ minimizes $F$, then $F(x)\geq F(x^*)$ for every $x\in\mathbb{R}^n$. Rewriting this as
\begin{align*}
F(x)\geq F(x^*)+0\cdot (x-x^*)
\end{align*}
shows that $0$ satisfies the subgradient inequality at $x^*$. Hence $0\in\partial F(x^*)$.
[/guided]
[/step]
[step:Compute the subdifferential of the composite sum]
The relative-interior qualification
\begin{align*}
\operatorname{ri}(\operatorname{dom} f)\cap A^{-1}\bigl(\operatorname{ri}(\operatorname{dom} g)\bigr)\neq \varnothing
\end{align*}
is exactly the standard constraint qualification for the convex subdifferential sum and linear-chain rule (citing a result not yet in the wiki: Convex Subdifferential Sum and Linear-Chain Rule). Therefore, for every $x \in \mathbb{R}^n$ with $F(x)<\infty$,
\begin{align*}
\partial F(x)=\partial f(x)+A^\top\partial g(Ax),
\end{align*}
where
\begin{align*}
A^\top\partial g(Ax)=\{A^\top y : y\in\partial g(Ax)\}.
\end{align*}
In particular, at the candidate minimizer $x^*$,
\begin{align*}
0\in\partial F(x^*)
\end{align*}
if and only if there exist $s^*\in\partial f(x^*)$ and $y^*\in\partial g(Ax^*)$ such that
\begin{align*}
0=s^*+A^\top y^*.
\end{align*}
[/step]
[step:Read the zero subgradient condition as the multiplier inclusions]
From the previous step,
\begin{align*}
0\in\partial F(x^*)
\end{align*}
holds if and only if there exist $s^*\in\partial f(x^*)$ and $y^*\in\partial g(Ax^*)$ satisfying
\begin{align*}
s^*=-A^\top y^*.
\end{align*}
Substituting this equality into the condition $s^*\in\partial f(x^*)$ gives
\begin{align*}
-A^\top y^*\in\partial f(x^*),
\end{align*}
while the second condition remains
\begin{align*}
y^*\in\partial g(Ax^*).
\end{align*}
Combining this equivalence with the Fermat reduction proves that $x^*$ minimizes $F$ if and only if there exists $y^*\in\mathbb{R}^m$ satisfying the two stated inclusions.
[/step]
