# Strict Feasibility in Interior Point Methods

As we know, in the interior point methods, all the iterates have to be strictly feasible. I implemented an affine scaling interior point for nonlinear objective functions. For small examples (2D), it works as expected. However, for large examples (e.g. optimal control problems), after a finite number of steps, some elements of the iterates start to be on the boundaries. I don't know the exact solutions of those optimal control problems, so I compared the results with the other methods (i.e. same problems, different methods). The numerical solutions obtained from this interior point method have the same number of active elements as the solutions obtained from the other methods. The solutions have the same plots as well as objective function values. The issue here is why the iterates are not strictly feasible. (they are for small examples but not for examples with large numbers of variables).

In short, the method of interest (i.e. interior point method) produces the same numerical solutions as the other methods but the iterates are not strictly feasible. Could you please help me?

• I don't understand your question. If a bunch of methods all agree on the answer, that's probably the answer. Is your question "how could an interior point method end up with a solution on the boundary?", or is it something else? If optimum is on the boundary, IP methods are going to get very, very close to it. – Bill Barth Feb 22 '15 at 15:02
• Sorry for the vague questions. Yes, my question is how can the iterates in my interior point method be on the boundary? (while the method still seems to produce correct result) – Linh Huynh Feb 22 '15 at 15:24
• @LinhHuynh: You're talking about primal methods, right? Primal-dual interior point methods allow (primal or dual) infeasible iterates, and tend to be the methods implemented in production nonlinear programming solvers. – Geoff Oxberry Feb 23 '15 at 20:43

• What exactly do you mean by "on the boundary"? It would be unsurprising to see values of $x_{i}$ that were tiny (say $1.0 \times 10^{-30}$.) It would be surprising to see values of exactly 0 since the algorithm is conventionally implemented in such a way as to prevent this from happening- if it did, then the affine scaling would result in division by 0. – Brian Borchers Feb 22 '15 at 17:46
• Here I'm assuming that your feasible region is defined by equations $Ax=b$ and inequalities $x \geq 0$. The same general ideas apply if you inequality constraints and slack variables that are constrained to be nonnegative or if you have variables with upper bounds. – Brian Borchers Feb 22 '15 at 17:50
• The algorithm that your using apparently doesn't protect against round-off errors that cause your iterates to hit the actual bounds. In most interior point algorithms for LP, the constraints are written in terms of variables that are constrained to be greater than 0- these can be made smaller and smaller in each iteration without underflowing to 0 until you get to values smaller than $10^{-300}$. You might consider rewriting your algorithm using nonnegative variables to avoid this problem. – Brian Borchers Feb 22 '15 at 18:46