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

[Joshua Redstone]

'help qp' in octave defines returning INFO=0 as "The problem is feasible and
convex.  Global solution found."which suggests it is returning the global
minimum.
qp() optimizes x'*H*x + x'*q, which I think is convex if the matrix H is
positive semi-definite (which it is in this case), but my math is a bit weak
in this area.
Josh

On Thu, Jun 5, 2008 at 8:52 AM, Ben Abbott <bpabbott at mac.com> wrote:

> 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
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.cae.wisc.edu/pipermail/bug-octave/attachments/20080605/963e7c95/attachment.html