qp() in Octave 3.0.0 returns result egregiously violating input constraints

[Joshua Redstone]

Hi Ben,
The INFO field returns a value indicating if the problem is convex or not,
and returns a local minimum if it is not convex.
In any case, we know for the example problem that feasible solutions exist,
so according to the current spec for qp() it must return one of them, even
if it's not the global optimum.  One could change the spec to say it may not
return feasible solutions, but it's probably better/easier to find the root
problem - I hope.
Josh

On Sun, Apr 6, 2008 at 11:08 AM, Ben Abbott <bpabbott at mac.com> wrote:

>
> On Apr 6, 2008, at 1:29 PM, Gabriele Pannocchia wrote:
>
> > Hi,
> >
> > I ran the example and got a result that is feasible with respect to
> > equality constraits:
> > octave:8> norm(A*X-B)
> > ans =  2.5177e-15
> > octave:19> tol = 10*eps; all(A_IN*X < A_UB + tol) & all(A_IN*X > A_LB -
> > tol)
> > ans =  1
> > octave:20> tol = 10*eps; all(X < UB + tol) & all(X > LB - tol)
> > ans =  1
> >
> > However, the solver did not converge as it reached the maximum number of
> > iterations:
> > INFO =
> > {
> >  solveiter =  200
> >  info =  3
> > }
> >
> > One reason for not reaching convergence could be the fact that the
> > Hessian of the objective function is NOT positive definite (it actually
> > INDEFINITE because it has at least a negative eigenvalue):
> > octave:23> min(eig(H))
> > ans = -0.0011912
> >
> > Even the projected Hessian is not positive definite (we can say that it
> > is semi-definite):
> > octave:26> Z = null(A);min(eig(Z'*H*Z))
> > ans = -5.0136e-122
> >
> >  octave:7> result = X'*H*X + X'*Q
> > > result =  5.0743e-06
> > >
> >
> > You can see the objective function in the variable OBJ, and please
> > notice that it is: 0.5*X'*H*X + X'*Q
> > octave:25> OBJ
> > OBJ =  2.5372e-06
> >
> > There is no guarantee that qp converges for non convex QPs, and indeed
> > convergence of indefinite (or semi-definite) programs is a large topic
> > in optimization.
> >
> > Cheers,
> >        Gabriele
> >
>
> Thanks Gabriel,
>
> Might it make sense to add a check to qp and warn in the event the problem
> is non-convex?
>
> If so, what would be appropriate?
>
> Ben
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www.cae.wisc.edu/pipermail/bug-octave/attachments/20080406/dc6b8e4e/attachment.html