bugGNU Octave - Bugs: bug #32717, sqp returns an error when the...

 
 

bug #32717: sqp returns an error when the local qp is infeasible

Submitter:  Gabriele Pannocchia <gpannocchia>
Submitted:  Tue 08 Mar 2011 04:31:47 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Need Info Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 30 Jul 2021 04:48:24 PM UTC, comment #9: 

also maybe worth noting that matlab does not have a sqp function to compare against to determine what behavior is 'good enough' for compatibility.  not clear from julien's test script, but if the goal is for y_opt2 to equal y_opt1, then it seems to not quite be there yet, at least for the 5th element of y_opt2. it would be useful to have an 'it works now' goal.

Nicholas Jankowski <nrjank>
Group Member
Fri 30 Jul 2021 04:32:31 PM UTC, comment #8: 

the status of this bug is unclear in octave v6.3.0. the comment #5 patch breaks out of the solver for the 'just error out if infeasible' short term fix suggested in comment #2.  but this appears to have been superseded by the patch for bug #36015, which added a lambda=old_lambda to line 429 to allow the program to complete with the warning so that the user knows the output is not to be trusted. 

Junien's comment #6 test script now produces:


>> RUN_ME
y_opt1 =

   7.8407e+02   1.2103e-02   5.4724e-01   1.9963e-01   3.6529e-04

warning: sqp: QP subproblem is infeasible
warning: called from
    sqp at line 441 column 9
    RUN_ME at line 30 column 8

warning: sqp: QP subproblem is infeasible
warning: called from
    sqp at line 441 column 9
    RUN_ME at line 30 column 8

warning: sqp: QP subproblem is infeasible
warning: called from
    sqp at line 441 column 9
    RUN_ME at line 30 column 8

x_opt2 =

   1.0000
   0.9879

y_opt2 =

   7.8400e+02   1.2147e-02   5.4725e-01   2.0000e-01  -3.5854e-07


the 'long term' fix suggested in comment #2 was to "make it possible to recover from an infeasible QP."  I do not understand the algorithm enough to know if the current fix does that, but from the discussion on that bug report it seems the answer is no.

BUT, it no longer returns an error.   Maybe the bug should be retitled to "sqp: enable recovery from an infeasible qp", and then it can sit until someone ventures down the nonlinear algorithms rabbit hole.

Nicholas Jankowski <nrjank>
Group Member
Sat 19 Nov 2016 02:02:22 PM UTC, comment #7: 

This issue is still present in Octave 4.2.0.

Hartmut <hardy>
Tue 13 Oct 2015 03:17:36 PM UTC, comment #6: 

Please consider the attached example (sqpInfeasibleQPsubprogram.zip) of a feasible NLP problem where sqp fails because of an infeasible qp subprogram.


(file #35180)

Julien Bect <jbect>
Mon 13 Oct 2014 12:04:34 PM UTC, comment #5: 

Thank you Carlo, I posted a changeset here in the bug page.

Federico Bonelli <fedechicco>
Mon 13 Oct 2014 09:10:05 AM UTC, comment #4: 

Federico,

If you have a patch the best way to submit it is in the
form of a mercurial changeset.

thanks,
c.

Carlo de Falco <cdf>
Group Member
Mon 13 Oct 2014 09:02:40 AM UTC, comment #3: 

I have a fix for this problem but I'm new to savannah. Should I post a .diff here, or maybe the whole sqp file?

The fix basically adds an exit condition with a new info return code when a QP subproblem is detected unfeasable.

Federico Bonelli <fedechicco>
Mon 11 Nov 2013 07:38:45 AM UTC, comment #2: 

Ok, it turns out that this bug report is not related to the same problem that bug #38875.

Short term plan: I will propose a patch to exit sqp cleanly when an infeasible QP is met, as proposed below.

Long term goal: make it possible to recover from an infeasible QP. This is redundant with item 3 in bug #32008. Not that it would be nice to exhibit a feasible NLP problem where this happens (because the example given below is not feasible at all).

Julien Bect <jbect>
Fri 08 Nov 2013 09:16:25 PM UTC, comment #1: 

The same problem (or so it seems) is discussed here:

https://savannah.gnu.org/bugs/?38875

Julien Bect <jbect>
Tue 08 Mar 2011 04:31:47 PM UTC, original submission:  

Dear Octave Developers,

The nonlinear optimization routine "sqp" seems to not deal properly with the case where the qp subproblem turns out to be infeasible (either because the actual nonlinear program is infeasible or because the local constraint linearization gave rise to an infeasible problem).

To show the error, you may execute the following lines of code (to which I am attaching two necessary .m files, which defines the equality constraints and the objective function).

x0 = zeros(2,1);
xmin = [-1;-1];
xmax = [ 0;0];

[xopt, obj, info, iter] = sqp (x0, "objfun", "eqcon", [], xmin, xmax);

Specifically, the chosen example is infeasible. The routine sqp returns an error at the following lines:

      if (! isempty (A))
t = ((A_new - A)'*lambda);
y -= t;
      endif

because lambda is an empty vector due to the fact the qp subproblem was infeasible.

I briefly skimmed the relevant chapter of Nocedal and Wright optimization book, which maybe was used as a reference for writing the code, and the solution does not seem trivial and may involve using slack variables and large linear penalties to ensure that the qp sub-problems are always feasible at each iteration.

I may try to explore this path if the Team thinks it is useful. In the short term I would suggest adding a check, right after the qp call, to detect if it was infeasible and in such case exist sqp and return a code for infeasible problem.

Thanks and please let me know if I can be of any help with this.

Gabriele Pannocchia



Gabriele Pannocchia <gpannocchia>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #35180:  sqpInfeasibleQPsubprogram.zip added by jbect (83KiB - application/zip)
file #32266:  sqp-changeset added by fedechicco (947B - application/octet-stream - Proposing changeset which adds a return code for infeasable QP subproblems)
file #22857:  objfun.m added by gpannocchia (58B - application/octet-stream)
file #22858:  eqcon.m added by gpannocchia (81B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by cdf (Posted a comment)
  • -email is unavailable- added by fedechicco (Posted a comment)
  • -email is unavailable- added by fedechicco
  • -email is unavailable- added by jbect (Posted a comment)
  • -email is unavailable- added by mtmiller (Updated the item)
  • -email is unavailable- added by gpannocchia
  • -email is unavailable- added by gpannocchia (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 12 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-08-09 nrjank StatusConfirmed Need Info
    2015-10-13 jbect Attached File- Added sqpInfeasibleQPsubprogram.zip, #35180
    2014-10-13 fedechicco Attached File- Added sqp-changeset, #32266
    2014-10-13 fedechicco Carbon-Copy- Added -email is unavailable-
    2013-10-28 mtmiller CategoryNone Octave Function
        Item GroupSegfault, Bus Error, etc. Incorrect Result
        StatusNone Confirmed
        Release3.2.4 dev
        Operating SystemMac OS Any
    2011-03-08 gpannocchia Attached File- Added eqcon.m, #22858
        Carbon-Copy- Added gpannocchia
    2011-03-08 gpannocchia Attached File- Added objfun.m, #22857

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code