some sqp problems (was: Re: [bug #31742] sqp: incorrect order of removal of Inf bounds)

[Olaf Till]

On Mon, Dec 13, 2010 at 07:28:29PM +0000, Rik wrote:
> 
> Follow-up Comment #7, bug #31742 (project octave):

I'm posting to the list instead, since the issue seems unrelated to
the above bug (I think the bug should be closed --- may be you would
like to file a separate bug for the current issue).

> While testing your patch with the example in the documentation I found a few
> more problems with sqp (not your patch).  First, it doesn't always respect
> bounds if only one bound is specified, such as -1,[]. 

For the record: you mean the test problem in sqp.m, supplied with
these additional bound constraints.

> It seems that in this
> case the algorithm converges on a value for x(1) near -1.7 and the algorithm
> stops because the stepsize becomes too small.  The return value for this case
> is still 101, success, which it clearly isn't.  Perhaps we should use a
> different return value to indicate this sort of stopping condition?  Secondly,
> the problem seems to be with the magnitude of the upper bound in this case. 
> If I use a smaller upper bound such as 10, rather than +realmax, then sqp
> works.  In the same vein, if I use a vector of all Infs, then sqp also works
> because the constraint is removed with your new code.  Perhaps, if the bound
> is unspecified, the code should reduce to using +/-Inf rather than +/-realmax
> so that the bound is never tested?

There are 5 parameters and 3 equality constraints, and now
additionally 10 inequality constraints (bounds). There does not
necessarily exist an x which satisfies all of these. If you check the
value of g for the result, you see that in cases the lower bound on
x(1) is not met, g is nearer to zero. And if the bound is met, sqp has
also stopped because the stepsize became too small. So sqp seems to
find, depending on the course of optimization, one of two
possibilities which differently violate the constraints --- since
their full satisfaction is probably not possible. The return code 101
means "Either all constraints meet the requested tolerance, or the
stepsize ... is less than ...", so 101 should not be wrong here. As
you say, one might use separate return codes for the two
conditions. But probably both conditions are a bit arbitrary and the
user has to assess the result himself.

Taken together: With both results the algorithm has made no mistake
(it has only taken a different course and has come to different,
equally (in)valid, results), so I see no reason to replace "realmax"
bounds with "unspecified" bounds because of this. A separate return
code for "small step size" seems reasonable, but I would not overvalue
it.

> The second problem is a little more serious.  If I run the demo code and set
> a smallish upper bound then the function crashes because lambda is empty.
> 
> [x, obj, info, iter, nf, lambda] = sqp (x0, @phi, @g, [], -10, 1)
> error: sqp: operator *: nonconformant arguments (op1 is 5x13, op2 is 0x0)
> error: called from:
> error:   /home/rik/wip/Projects_Mine/octave-doc/scripts/optimization/sqp.m at
> line 481, column 9

According to the comments in qp.m, it returns an empty lambda if it
can't solve the qp problem. Whether such qp problems occur can depend
on the course of optimization in sqp, which explains that the error is
seen only under certain conditions. What sqp should do is to check
whether lambda is empty, and if it is, stop with a special return
code. There is already a comment line in sqp.m at the respective
position:

    ## Check QP solution and attempt to recover if it has failed.

But there is no code as yet belonging to this comment, and how to
attempt to recover (i.e. continue optimization) I do not know.

Olaf