Infeasible Start Newton's Method

Definition

Algorithm

Solve the minimization problem with the equality condition $\min f(\mathbf{x})$ subject to $A\mathbf{x}=\mathbf{b}$

Use a Newton’s Method to find the optimal point ${\mathbf{x}}^{\ast }$ satisfying above conditions

The quadratic Taylor approximation of $f(\mathbf{x}+(\Delta \mathbf{x}))$ at the point $\mathbf{x}$ is $f(\mathbf{x}+(\Delta \mathbf{x}))\simeq f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})$

The minimization problem is $\min f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})$ subject to $A((\Delta \mathbf{x})+\mathbf{x})=\mathbf{b}$

The Lagrangian function is $\mathcal{L}(\mathbf{x},\mathbf{w})=f(\mathbf{x})+\nabla f(\mathbf{x})(\Delta \mathbf{x})+\frac{1}{2}(\Delta \mathbf{x}{)}^{⊺}{\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})+{\mathbf{w}}^{⊺}(A(\Delta \mathbf{x})+A\mathbf{x}-\mathbf{b})$ where $\mathbf{w}$ is a Lagrangian multiplier

The optimality condition is ${\nabla }_{(\Delta \mathbf{x})}\mathcal{L}(\mathbf{x},(\Delta \mathbf{w}))={\nabla }^{2}f(\mathbf{x})(\Delta \mathbf{x})+\nabla f(\mathbf{x})+{\mathbf{w}}^{⊺}A=0,A(\Delta \mathbf{x})=-(A\mathbf{x}-\mathbf{b})$

In a matrix form, $\left[\begin{array}{cc}{\nabla }^{2}f(\mathbf{x})& A^{⊺}\\ A& 0\end{array}\right]\left[\begin{array}{c}(\Delta \mathbf{x})\\ \mathbf{w}\end{array}\right]=-\left[\begin{array}{c}\nabla f(\mathbf{x})\\ A\mathbf{x}-\mathbf{b}\end{array}\right]$

we solve this linear equation to find the Newton direction $(\Delta \mathbf{x})$