0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Barth Feb 22 '15 at 15:02
  • $\begingroup$ 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) $\endgroup$ – Linh Huynh Feb 22 '15 at 15:24
  • $\begingroup$ @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. $\endgroup$ – Geoff Oxberry Feb 23 '15 at 20:43
2
$\begingroup$

Unlike barrier methods, the affine scaling method doesn't use a barrier to push the iterates away from the boundaries of the feasible region. As a result, the iterates can very quickly approach the boundary of the feasible reason. Furthermore (and this can be a problem) the method can easily get "stuck" taking very short steps along the boundary of the feasible region.

It's not surprising at all that you're seeing this behavior. If you switched to a barrier method you would likely see faster and more robust convergence.

$\endgroup$
  • $\begingroup$ Thank you! May you share with me some references where the affine scaling interior point methods result in active iterates (i.e. the iterates are on the boundary)? This sounds interesting and it would be great if I could learn more. $\endgroup$ – Linh Huynh Feb 22 '15 at 17:23
  • $\begingroup$ One thing that confuses me is that the algorithm I used does involve projection that ensures strict feasibility. However, I am not sure why the elements can still be on the boundary. Based on your experiences, do you have any feeling about the cause of this? I am thinking of rounding off errors/floating point but I am not sure. $\endgroup$ – Linh Huynh Feb 22 '15 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Feb 22 '15 at 17:46
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Feb 22 '15 at 17:50
  • 4
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Feb 22 '15 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.