Suggest edit — equality constrained minimization

Title

Name

Note

---
title: "equality constrained minimization"
type: concept
source: https://www.jemoka.com/posts/kbhequality_constrained_minimization/
confidence: high
status: active
---

Equality constrained smooth optimization problem:
\begin{align} \min_{x}\quad &amp; f\qty(x) \\ \textrm{s.t.} \quad &amp; Ax = b \end{align}
for \(f\) convex, and twice differentiable; for \(A \in \mathbb{R}^{p\times n}\), rank \(p\).
additional information equality constrained quadratic minimization say its a quadratic:
\begin{align} f\qty(x) = \frac{1}{2} x^{T}P x + q^{T} x + r \end{align}
for \(P \in \mathbb{S}^{n}_{+}\)
We can form optimality via the KKT Conditions in a block:
\begin{align} \mqty(P &amp; A^{T}\\ A &amp; 0) \mqty(x^{*}\\v^{*}) = \mqty(-q \\ b) \end{align}
recall that this matrix is nonsingular IFF \(Ax = 0, x\neq 0 \implies x^{T}Px &gt; 0\). equivalently: \(P + A^{T}A &gt; 0\) newton&rsquo;s method These two methods are identical.
eliminating equality conditions Recall we can write:
\begin{align} \qty {x \mid Ax = b} \end{align}
as
\begin{align} \mqty(F z + \hat{x} \mid z \in\mathbb{R}^{n-p}) \end{align}
where for \(F \in \mathbb{R}^{n \times \qty(n-p)}\) we have \(\text{range}\ F = \text{null}\ A\) (rank \(F = n-p\) and \(AF = 0\)).
\begin{align} \min \qty(Fz+\hat{x}) \end{align}
newton step preserving equality constraints \begin{align} \mqty(\nabla^{2}f\qty(x) &amp; A^{T} \\ A &amp; 0) \mqty(v \\w) = \mqty(-\nabla f\qty(x) \\ 0) \end{align}
this is actually a second-order approximation of the original function:
\begin{align} \min_{v}\quad &amp; f\qty(x+v) = f\qty(x) + \nabla f\qty(x)^{T}v + \qty(\frac{1}{2})v^{T} \nabla^{2}f\qty(x) v \\ \textrm{s.t.} \quad &amp; A\qty(x+v)= b \end{align}
this is an explicit version
infeasible newton&rsquo;s method With \(y\qty(x,v)\), we write optimality as:
\begin{align} r\qty(y) = \qty(\nabla f\qty(x) + A^{T} v, Ax -b ) \end{align}
is the &ldquo;primal-dual residual.&rdquo; We hope to minimize this (i.e. we want to &ldquo;minimize the 2-norm of these&rdquo;.)
Consider \(x \in \text{dom}\qty(f)\), and \(Ax \neq b\), such that \(x\) is infeasible. If we linearize \(r=0\) at \(r\qty(y+\Delta y) \approx r\qty(y) + D r\qty(y) \Delta y = 0\):
\begin{align} \mqty(\nabla^{2}f\qty(x) &amp; A^{T} \\ A &amp; 0) \mqty(\Delta x_{nt} \\ \Delta v_{nt}) = -\mqty(\nabla f\qty(x) + A^{T}v \\ Ax -b) \end{align}