# reduced system: primal-dual interior point method for nonconvex constrained problem

When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method?

For example, following notation from NW, if the original nonlinear system is like (19.12) \begin{align} \begin{bmatrix} \nabla_{xx}^2 L & 0 & A_E(x)^T & A_I(x)^T \\ 0 & \Sigma & 0 & -I \\ A_E(x) & 0 & 0 & 0 \\ A_I(x) & -I & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} p_x \\ p_s \\ -p_y \\ -p_z \end{bmatrix} = -\begin{bmatrix} \nabla f(x) - A_E(x)^Ty - A_I(x)^T z \\ z - \mu S^{-1}e \\ c_E(x) \\ c_I(x) - s \end{bmatrix}, \end{align}

then I see how a solution gives us a way to update $x,s,y,z$. However, if we solve a reduced system of the form

\begin{align} \begin{bmatrix} \nabla_{xx}^2 L + A_I(x)^T\Sigma A_I(x) & A_E(x)^T \\ A_E(x) & 0 \end{bmatrix} \begin{bmatrix} p_x \\ -p_y \end{bmatrix} = \text{?} \end{align}

then (1) what is the RHS; and (2) how do we update $s,z$?

EDIT: Can I have some help on the details for how we eliminate variables in moving from the larger system to the smaller system?

Once you have $p_x,p_y$, you can use the second and fourth of the block system you show in your question to compute the updates $p_s,p_z$. They satisfy the equations \begin{align} \begin{bmatrix} \Sigma & -I \\ -I & 0 \\ \end{bmatrix} \begin{bmatrix} p_s \\ -p_z \end{bmatrix} = \begin{bmatrix} z - \mu S^{-1}e \\ c_I(x) - s - A_I(x)p_x \end{bmatrix}. \end{align}
• Thanks! And to confirm, I can use the same approach for calculating step size as if I solved the full system outright? Btw -- I made a typo on the last line of my large system, so I believe the lower left $I$ of your program should be $-I$? Mar 12, 2018 at 14:43
• And yes, once you have all of the updates $p_\ast$ computed as above, you can do a linear search. Mar 13, 2018 at 2:59
• Thanks -- as a follow up, when I computed $p^*$ under the full and reduced systems of my original formulation (using the $\Sigma, -I...$ submatrix to get $p^*_s, p^*_y$), I was getting different results (this was for $dim(x) = 10$ so I don't think numerical issues were present). I believe the RHS is wrong for my reduced system? Mar 13, 2018 at 3:19