equality constrained minimization — Jemoka Knowledge Base

Equality constrained smooth optimization problem:

\begin{align} \min_{x}\quad & f\left(x\right) \\ \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\left(x\right) = \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} \left\{x \mid Ax = b\right\} \end{align}

\begin{align} \mqty(F z + \hat{x} \mid z \in\mathbb{R}^{n-p}) \end{align}

where for F \in \mathbb{R}^{n \times \left(n-p\right)} we have \text{range}\ F = \text{null}\ A (rank F = n-p and AF = 0).

\begin{align} \min \left(Fz+\hat{x}\right) \end{align}

newton step preserving equality constraints \begin{align} \mqty(\nabla^{2}f\left(x\right) & A^{T} \ A & 0) \mqty(v \w) = \mqty(-\nabla f\left(x\right) \ 0) \end{align} this is actually a second-order approximation of the original function:

\begin{align} \min_{v}\quad & f\left(x+v\right) = f\left(x\right) + \nabla f\left(x\right)^{T}v + \left(\frac{1}{2}\right)v^{T} \nabla^{2}f\left(x\right) v \\ \textrm{s.t.} \quad & A\left(x+v\right)= b \end{align}

this is an explicit version infeasible newton’s method With y\left(x,v\right), we write optimality as:

\begin{align} r\left(y\right) = \left(\nabla f\left(x\right) + A^{T} v, Ax -b \right) \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}\left(f\right), and Ax \neq b, such that x is infeasible. If we linearize r=0 at r\left(y+\Delta y\right) \approx r\left(y\right) + D r\left(y\right) \Delta y = 0:

\begin{align} \mqty(\nabla^{2}f\left(x\right) & A^{T} \\ A & 0) \mqty(\Delta x_{nt} \\ \Delta v_{nt}) = -\mqty(\nabla f\left(x\right) + A^{T}v \\ Ax -b) \end{align}