qp() in octave-3.0.0 gets stuck on wrong answer to convex problem

[Ben Abbott]

On Thursday, June 05, 2008, at 10:56AM, "Joshua Redstone" <redstone at gmail.com> wrote:
>Hi all,I think I've come across a bug in qp() in which qp() gets stuck
>(empirically converges to the wrong answer) when it shouldn't.
>I've found a problem instance for which, depending on the initial X0
>provided, qp() either
>declares the problem convex and returns the global optimum solution in 120
>iterations, or
>gets stuck on a particular suboptimal solution regardless of how many
>iterations it executes for.
>I think either qp() is erroneously reporting the problem is convex, or more
>likely, it is somehow getting stuck.
>I've attached an octave file, qpprob.dat, with which to reproduce the
>problem (generated on OSX 10.5.2).  It contains the full problem instance
>including an initial x_bad and x_good which
>causes qp() to either get stuck or quickly find the optimum.
>Below is the output of a session exhibiting the problem.  In the following
>session, I've modified qp() so that it takes an extra argument specifying
>the maximum number of iterations to execute for (the default without the
>extra arg is 200, I think):
>
>octave-3.0.0:1> format long
>
>octave-3.0.0:2> load "qpprob.dat"
>
>octave-3.0.0:3> [X, OBJ, INFO, LAMBDA] = qp(x_bad, H, Q, A, B, LB, UB, A_LB,
>A_IN, A_UB, 200);
>
>octave-3.0.0:4> OBJ
>
>OBJ =  0.00763280553660678
>
>octave-3.0.0:5> INFO
>
>INFO =
>
>{
>
>  solveiter =  200
>
>  info =  3
>
>}
>
>
>octave-3.0.0:6> [X, OBJ, INFO, LAMBDA] = qp(x_bad, H, Q, A, B, LB, UB, A_LB,
>A_IN, A_UB, 1000);
>
>octave-3.0.0:7> OBJ
>
>OBJ =  0.00763280553660678
>
>octave-3.0.0:8> INFO
>
>INFO =
>
>{
>
>  solveiter =  1000
>
>  info =  3
>
>}
>
>
>octave-3.0.0:9> [X, OBJ, INFO, LAMBDA] = qp(x_good, H, Q, A, B, LB, UB,
>A_LB, A_IN, A_UB, 200);
>
>octave-3.0.0:10> OBJ
>
>OBJ =  1.57898325754824e-05
>
>octave-3.0.0:11> INFO
>
>INFO =
>
>{
>
>  solveiter =  121
>
>  info = 0
>
>}
>
>
>As you can see, with x_bad, qp() has converged to a suboptimal solution
>which doesn't change as I increase the number of iterations.When I try
>x_good, it returns INFO=0, which means the problem is convex and it has
>found the global solution, which is two orders of magnitude
>smaller in the objective.....
>
>Does anyone have suggestions of a workaround or ways to track down the bug?
>Thanks,
>Josh
>

This may not be of any help, but I hope to at least satisfy my curiosity.

It is my understanding that there is no assurance of finding the global minimum for nonlinear optimization problems ... is there something special about the qp algorithm and/or its application that changes this?

Also, to qualify as "convex" does the problem need to be globally convex or does qp simply determine the problem is locally convex. If the latter, is it possible that qp has converged upon a local minimum?

Ben