Equality constrained smooth optimization problem:

\begin{align} \min_{x}\quad & f\qty(x) \\ \textrm{s.t.} \quad & 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 & A^{T}\\ A & 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 > 0\).
• equivalently: \(P + A^{T}A > 0\)

newton’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) & A^{T} \\ A & 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 & 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 & A\qty(x+v)= b \end{align}

this is an explicit version

infeasible newton’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 “primal-dual residual.” We hope to minimize this (i.e. we want to “minimize the 2-norm of these”.)

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) & A^{T} \\ A & 0) \mqty(\Delta x_{nt} \\ \Delta v_{nt}) = -\mqty(\nabla f\qty(x) + A^{T}v \\ Ax -b) \end{align}