I am trying to understand how to use a Newton type method to minimise a nonlinear function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, subject to $Ax=b$ and $x \geq 0$. Here $x\in\mathbb{R}^{n}$, $b\in\mathbb{R}^{m}$ and $A\in\mathbb{R}^{m\times n}$.
I enforce the equality constraint using the following Newton step: $$ \begin{pmatrix} \nabla^{2}f(x) && A^{T} \\ A && 0 \end{pmatrix}\begin{pmatrix} \Delta x \\ \Delta y \end{pmatrix} = - \begin{pmatrix} \nabla f(x)+ A^{T}y \\ Ax - b \end{pmatrix}. $$ The primal and dual variables are then updated by $x \leftarrow x + \alpha\Delta x$ and $y \leftarrow y + \alpha\Delta y$, where the step size $\alpha$ is determined using a backtracking rule. This method converges very quickly and correctly gives me a solution $x$ that minimises my function $f$ and satisfies $Ax=b$, however I am unsure how to enforce $x\geq 0$.
I attempted to use the method given on page 609 of this book by Boyd. It describes a Newton method to minimise a function $f$ subject to $Ax=b$ and $g(x)<0$. To enforce non-negativity, I set $g(x)=-x$ and, if I worked this out correctly, the Newton step is then:
$$ \begin{pmatrix} \nabla^{2}f(x) && -I && A^{T} \\ \mathrm{diag}(\lambda) && \mathrm{diag}(x) && 0 \\ A && 0 && 0 \end{pmatrix}\begin{pmatrix} \Delta x \\ \Delta \lambda \\ \Delta y \end{pmatrix}=-\begin{pmatrix} \nabla f(x) + A^{T}y - \lambda \\ \lambda x - (1/\alpha)\mathbf{1} \\ Ax - b \end{pmatrix}. $$
However, this does not seem to give me the correct solution, and the condition number of the matrix blows up as the iterations progress. Also, the right hand side involves a factor of $1/\alpha$ which also blows up as my step sise $\alpha$ decreases. I am unsure whether I have simply implemented it incorrectly, or computed the matrix incorrectly or if the method is even suitable for my problem at all.
So my question is, is there a simple way to enforce the non-negativity constraint? Am I on the right track?
A lot of the nonlinear optimisation literature that I have looked at seems to discuss either equality or inequality constraints, but not both. The text book I mentioned above does discuss both, but I think it might be more complicated than I require for the simple constraint of $x\geq 0$.
The key issue here is that you want to enforce an inequality constraint $x \geq 0$. In primal-dual interior point methods, this is typically done by introducing Lagrange multipliers $z_{i}$ for the nonnegativity constraints and then enforcing $x > 0$ and $z > 0$ in the line step by picking $\alpha_{p}$ and $\alpha_{d}$ so that
$x+\alpha_{p} \Delta x > 0$
$z+\alpha_{d} \Delta z > 0$
These conditions further restrict the step length.
In primal-dual interior point methods, a barrier term is also added to the objective function to keep the $x$ and $z$ variables away from 0.