Implementation Question in Newton's Method for QPs

[Vivek Periaraj]

Hello Group,

I have been working on the Newton's method for solving QP and to get first
order optimal solutions (a KKT point) when the hessian of the QP is not
positive definite.

I am facing an issue which affects less than 5% of cases where the method
does not converge to the optimal solution. To summarize the approach:

To find the Newtons iterates, I solve the following (non) linear system of
equations. One of them becomes non-linear because of the complementary
slackness of the KKT condition.

f''(x,l,s) * d(x,l,s) = -f'(x,l,s).

This d(x,l,s) is used as a direction vector to find the next feasible point
in the sequence by finding a positive steplength(a). I am ensuring the non-
negativity of x and s at each iteration.

x(k+1) = x(k) + a * dx(k)
l(k+1) = l(k) + a * dl(k)
s(k+1) = s(k) + a * ds(k)

The issue happens when at some iteration, x(i) is zero and the corresponding
d(i) is negative. So there is no positive step length that would ensure non-
negativity of x. So the sequence arising out of this situation leads to sub-
optimal solutions.

If I remove the variable that's causing the above condition, I am able to
solve the model to optimality. Maybe there is a better way to handle this
case. Any thoughts?

Regards,
Vivek.

--- Posted via news://freenews.netfront.net/ - Complaints to ne...@netfront.net ---

[Paul]

If you perturb x a small amount in a feasible direction and recompute, do you still get jammed?

Paul

[Vivek Periaraj]

Hi Paul,

Yes. Even when I perturb x by a very small amount (that is, by setting 'a'
close to zero), the algorithm does not converge. I had to remove such
variables from the model.

There are some cases when "x(i) is zero and d(i) is negative", the model
does seem to come out of the jam and converge to optimality. So the logic of
removing variables does not work in these cases. This makes arriving at a
generic logic to handle this situation bit difficult.

Thanks,
Vivek.

[Paul]

I did not have in mind perturbing x by tweaking a. Let's assume that you can identify some point y in the interior of the feasible region (regardless of objective value). When you run into trouble at some x, change it to x' = x + epsilon(y-x). That point will be in the interior, so any direction will be feasible. (I'm assuming, perhaps rashly, that your feasible region is convex.) Try generating a new direction d at x' and see if the next step lands you someplace where you don't get jammed again.

Paul

[Vivek Periaraj]

Hi Paul,

Got you! I tried this method with all possible epsilon. But no luck. I had
initially tried something similiar. I have a simple heuristic to get me a
good initial solution and I had tweaked the parameters to it to find
different solutions and all of them resulted in the same issue.

A generic approach I have got so far, is to converge to a solution. Check
for negative values, eliminate them and start again from that solution
after ensuring feasibility. This logic achieves optimality for all of my
test cases.

I have to study a bit more as to why such variables are an issue. My Q
matrix is positive semi-definite. Maybe we can eliminate them in the
presolve itself.

Regards,
Vivek.

[Paul]

A couple of other possibilities that come to mind are using a barrier method (stick with Newton's method, add a barrier function to the objective, start from a known interior point) or switching to a gradient projection method (something like GRG2).

Paul

[Vivek Periaraj]

Hi Paul,

The barrier function for the Newton's formulation I have translates to the
perturbed complementarity. So we gradually reduce the barrier parameter to
0. But in my current Newton formulation, I am ensuring both primal
feasibility and complementarity at each iteration. So my barrier parameter
is always 0. I have to play with different values for the barrier parameter.

This issue however, seem to happen when one of the variables tend to become
0 in the optimal solution, in which case, the Newton's direction vector
corresponding to that variable becomes negative. I am not sure if the
barrier function can force such variables as well as the corresponding
element in the direction vector to zero. By eliminating such variables from
the model, I have done exactly that!

Thanks,

[Paul]

Seems to me the barrier function should prevent the primal variable from ever reaching zero. (You included the sign restrictions in the definition of the barrier function, right?)

Paul

[Vivek Periaraj]

Hi Paul,

Thanks for the tip!

Two things that fixed the problem to me. I wasn't using 'x >= 0' type
constraints in my model. I added that and this fixed many of the issues. But
in some cases, the model was still hitting <= 0 because of the condition
described earlier in the thread. For these cases, adding barrier function
helped a lot. What didn't work out for me initially was the monotonic
updates to the barrier parameter. I tried the Mehrotra's predictor-corrector
barrier update strategy and this worked for almost all cases. Thanks again!

Also, I had been using a dual solution which was on the vertex. But now I
had to use a dual solution which is in the interior. Should this be true? If
so, do you know any strategies to get a dual solution which is in the
interior?

Regards,

[Paul]

Sorry, I didn't really follow the bit about the dual solution. Maybe someone else knows.

[Vivek Periaraj]

Paul wrote:

> Sorry, I didn't really follow the bit about the dual solution. Maybe
> someone else knows.

IPOPT uses least square estimates to find out the initial dual solution to
the problem. I guess my problem was that in using a dual solution that was
on the vertex. I changed this to non-vertex solution and this has fixed the
problem.