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

[Joshua Redstone]

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

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Ben Abbott]

On Thursday, June 05, 2008, at 10:56AM, "Joshua Redstone" <redstone@...> 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



_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[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@...> wrote:

On Thursday, June 05, 2008, at 10:56AM, "Joshua Redstone" <redstone@...> 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

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[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@...> 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@...> wrote:

On Thursday, June 05, 2008, at 10:56AM, "Joshua Redstone" <redstone@...> 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

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

I just tried octave 3.0.1 (osx) - the behavior is identical (i.e., it converges to the wrong answer).

Josh

On Thu, Jun 5, 2008 at 7:50 AM, Joshua Redstone <redstone@...> 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

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Gabriele Pannocchia]

Hi all,

I will look into Josh's example ASAP to see if I can reproduce the
problem and possibly understand why that happens.

> I just tried octave 3.0.1 (osx) - the behavior is identical (i.e., it
> converges to the wrong answer).

Just a clarification: if you get INFO=3, it means that the maximum
number of iterations has been reached. Thus, it is not correct to say
that it converges to the wrong answer.

Gabriele



_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

Hi Gabriele, 

Thanks for looking into this!

Yes, you're right, thanks for the clarification - I meant 'converge' in the sense that the value of OBJ does 

not seem to change as the maximum number of iterations increases.

If the data file I attached to the bug post doesn't work for you, I'll be back in front of a linux box next Tuesday and can 

generate a more linux-friendly example for you.

Thanks,

Josh

On Fri, Jun 6, 2008 at 2:43 PM, Gabriele Pannocchia <g.pannocchia@...> wrote:

Hi all,

I will look into Josh's example ASAP to see if I can reproduce the
problem and possibly understand why that happens.

> I just tried octave 3.0.1 (osx) - the behavior is identical (i.e., it
> converges to the wrong answer).

Just a clarification: if you get INFO=3, it means that the maximum
number of iterations has been reached. Thus, it is not correct to say
that it converges to the wrong answer.

Gabriele

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

Just checked, and the file I sent reproduces the problem on my Ubuntu 8.04 machine as well.
Josh

On Fri, Jun 6, 2008 at 4:03 PM, Joshua Redstone <redstone@...> wrote:

Hi Gabriele, 

Thanks for looking into this!

Yes, you're right, thanks for the clarification - I meant 'converge' in the sense that the value of OBJ does 

not seem to change as the maximum number of iterations increases.

If the data file I attached to the bug post doesn't work for you, I'll be back in front of a linux box next Tuesday and can 

generate a more linux-friendly example for you.

Thanks,

Josh

On Fri, Jun 6, 2008 at 2:43 PM, Gabriele Pannocchia <g.pannocchia@...> wrote:

Hi all,

I will look into Josh's example ASAP to see if I can reproduce the
problem and possibly understand why that happens.

> I just tried octave 3.0.1 (osx) - the behavior is identical (i.e., it
> converges to the wrong answer).

Just a clarification: if you get INFO=3, it means that the maximum
number of iterations has been reached. Thus, it is not correct to say
that it converges to the wrong answer.

Gabriele

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

I put a few printfs in the code and it looks like, after 18 iterations, it repeatedly enters the clause on line 443 with the comment

    // There are no blocking constraints.  Adding the whole step. 

In this clause, alpha = 1, and p alternates in value between +k and -k where k is a vector:

-0.000997019 -0.00297671 0.00197098 0.00200275 0.0335145 0.0424274 0.0343524 3.8161e-18 -6.72938e-18 0.0362161 0.0458195 0.0291282 0.00380536 0.0184418 0.0161607 -0.0338612 -0 -0.14143 -1.1093e-17 -0 -2.18072e-18 -0 -0 -0.000252608 -0 -0.0215625 -5.90882e-18 -0 -0.0543663 -0.034514 -0.0082697 -0 -0 -0.0727281 1.74693e-17 -2.13228e-18 -0.071406 0.0612498 0.0454769 1.58984e-17 1.37872e-17 0.0720697 2.35337e-17 0.166084 -4.04256e-17 0.0261761 3.58841e-18 -4.63691e-18 -0 -0.00228516 0.0265861 -0.0443588 1.21727e-17 -0.0594975 0.0186493 0.00538351 1.13094e-17 -0 -0 -0 -0 0.166227 2.79509e-17 -0 -1.92503e-17 -0 -0 0.165617 -2.82539e-18 0.132712 0.132843 -0 0.0804525 0.0710416 -0.000252608 -0.89828 -0 0.0126304

So it looks like it is bouncing back and forth between two points, which is consistent with the observation that it stops making progress.

Also, when it gets stuck as above, p is computed using the 'negative curvature' section of code earlier in the function.

Though I've no idea why it is doing this....

Hope this helps,

Josh

On Tue, Jun 10, 2008 at 7:35 AM, Joshua Redstone <redstone@...> wrote:

Just checked, and the file I sent reproduces the problem on my Ubuntu 8.04 machine as well.
Josh

On Fri, Jun 6, 2008 at 4:03 PM, Joshua Redstone <redstone@...> wrote:

Hi Gabriele, 

Thanks for looking into this!

Yes, you're right, thanks for the clarification - I meant 'converge' in the sense that the value of OBJ does 

not seem to change as the maximum number of iterations increases.

If the data file I attached to the bug post doesn't work for you, I'll be back in front of a linux box next Tuesday and can 

generate a more linux-friendly example for you.

Thanks,

Josh

On Fri, Jun 6, 2008 at 2:43 PM, Gabriele Pannocchia <g.pannocchia@...> wrote:

Hi all,

I will look into Josh's example ASAP to see if I can reproduce the
problem and possibly understand why that happens.

> I just tried octave 3.0.1 (osx) - the behavior is identical (i.e., it
> converges to the wrong answer).

Just a clarification: if you get INFO=3, it means that the maximum
number of iterations has been reached. Thus, it is not correct to say
that it converges to the wrong answer.

Gabriele

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www.cae.wisc.edu/mailman/listinfo/bug-octave

[John W. Eaton]

On  5-Jun-2008, Joshua Redstone 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

Are you sure it is positive semi-definite?  In the problem that you
sent, H has some negative eigenvalues.

jwe
_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

Hi John,
With respect to the bug I described, I don't think it matters if H is positive semi-definite or not.
It should be impossible for qp(), given a *single* quadratic programming problem and multiple starting points,
to return an answer claiming the problem is convex for some starting points, and for other starting points
return an answer indicating it has gotten stuck in a local minimum.  A single quadratic programming problem can not be both convex
and not-convex at the same time.  To put it another way, either the problem is convex, in which case all starting points should lead
to the global optimum, or the problem is not-convex, in which case qp() is in error claiming that it is convex.  Either way there is a bug in
either the qp() implementation or interface specification.
Does my reasoning seem reasonable?
Josh

On Fri, Aug 22, 2008 at 11:55 AM, John W. Eaton <jwe@...> wrote:

On  5-Jun-2008, Joshua Redstone 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

Are you sure it is positive semi-definite?  In the problem that you
sent, H has some negative eigenvalues.

jwe

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/bug-octave

[John W. Eaton]

On 22-Aug-2008, Joshua Redstone wrote:

| With respect to the bug I described, I don't think it matters if H is
| positive semi-definite or not.
| It should be impossible for qp(), given a *single* quadratic programming
| problem and multiple starting points,
| to return an answer claiming the problem is convex for some starting points,
| and for other starting points
| return an answer indicating it has gotten stuck in a local minimum.  A
| single quadratic programming problem can not be both convex
| and not-convex at the same time.  To put it another way, either the problem
| is convex, in which case all starting points should lead
| to the global optimum, or the problem is not-convex, in which case qp() is
| in error claiming that it is convex.  Either way there is a bug in
| either the qp() implementation or interface specification.
| Does my reasoning seem reasonable?

I probably missed some of the details of the discussion.  I was just
pointing out that your problem does not appear to have a positive
definite H.  If the qp function is sometimes saying that the problem
is convex and sometimes not, then that does seem to be a bug.  I'd be
happy to have a patch for that problem.

Thanks,

jwe
_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/bug-octave

[Joshua Redstone]

On Fri, Aug 22, 2008 at 3:18 PM, John W. Eaton <jwe@...> wrote:

On 22-Aug-2008, Joshua Redstone wrote:

| With respect to the bug I described, I don't think it matters if H is
| positive semi-definite or not.
| It should be impossible for qp(), given a *single* quadratic programming
| problem and multiple starting points,
| to return an answer claiming the problem is convex for some starting points,
| and for other starting points
| return an answer indicating it has gotten stuck in a local minimum.  A
| single quadratic programming problem can not be both convex
| and not-convex at the same time.  To put it another way, either the problem
| is convex, in which case all starting points should lead
| to the global optimum, or the problem is not-convex, in which case qp() is
| in error claiming that it is convex.  Either way there is a bug in
| either the qp() implementation or interface specification.
| Does my reasoning seem reasonable?

I probably missed some of the details of the discussion.  I was just
pointing out that your problem does not appear to have a positive
definite H.  If the qp function is sometimes saying that the problem
is convex and sometimes not, then that does seem to be a bug.  I'd be
happy to have a patch for that problem.

At the moment, I think the math in qp() is a bit over my head to know what a good fix would be.
(though I'm reading some stats/optimization books so maybe I'll catch up :) )
Anyone else?
Josh

Thanks,

jwe

_______________________________________________
Bug-octave mailing list
Bug-octave@...
https://www-old.cae.wisc.edu/mailman/listinfo/bug-octave