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

[Joshua Redstone]

oh, and I'm pretty sure 'convex' usually refers to convexity over the whole
domain ('global convexity').Josh

On Thu, Jun 5, 2008 at 9:12 AM, Joshua Redstone <redstone at gmail.com> wrote:

> '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/1caf83f9/attachment.html