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

 
 

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

Submitted by:  Gabriele Pannocchia <gpannocchia>
Submitted on:  Tue 08 Mar 2011 04:31:47 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Incorrect Result
Status: ConfirmedAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating System: Any

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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 File(s):
   
   
Comment:
   

Attached Files
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
  • -unavailable- added by jbect (Posted a comment)
  • -unavailable- added by mtmiller (Updated the item)
  • -unavailable- added by gpannocchia
  • -unavailable- added by gpannocchia (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 8 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 28 Oct 2013 02:27:29 AM UTCmtmillerCategoryNone=>Octave Function
      Item GroupCrash=>Incorrect Result
      StatusNone=>Confirmed
      Release3.2.4=>dev
      Operating SystemMac OS=>Any
    Tue 08 Mar 2011 04:31:48 PM UTCgpannocchiaAttached File-=>Added eqcon.m, #22858
      Carbon-Copy-=>Added gpannocchia
    Tue 08 Mar 2011 04:31:47 PM UTCgpannocchiaAttached File-=>Added objfun.m, #22857

    Back to the top


    Powered by Savane 3.1-cleanup