Use the sign convention
$$
\mathcal L(x,z)=f(x)-z^T(Ax-b)
$$
for the <Lagrangian function in constrained optimization>. The <Lagrangian dual problem> is
$$
\boxed{
\max_{z\in\mathbb R^m}q(z),
\qquad
q(z)=\inf_x\mathcal L(x,z)
=b^Tz-f^*(A^Tz),}
$$
where $f^*$ is the <convex conjugate>. For this convex problem with affine equality constraints, the stationarity and feasibility parts of the <Karush-Kuhn-Tucker conditions> are
$$
\nabla f(x)-A^Tz=0,
\qquad Ax-b=0.
$$
They say exactly that the displayed operator satisfies
$$
\boxed{
F\binom{x}{z}
=\binom{\nabla f(x)-A^Tz}{Ax-b}=0.}
$$
Thus its zeros are precisely the <primal-dual optimal points>, subject to the usual attainment assumptions.

For $u=(x,z)$ and $\widetilde u=(y,s)$, the <inner product>[Euclidean inner product] gives
$$
\begin{aligned}
\langle F(u)-F(\widetilde u),u-\widetilde u\rangle
={}&\langle\nabla f(x)-\nabla f(y),x-y\rangle\\
&-\langle A^T(z-s),x-y\rangle
+\langle A(x-y),z-s\rangle.
\end{aligned}
$$
The last two terms cancel by the defining property of the <matrix transpose>, and the first is nonnegative by part a. Hence $F$ is a <monotone operator>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 339 / 2 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-339/2/c/solution