bugGNU Octave - Bugs: bug #64346, qp (quadratic programming) is...

 
 

bug #64346: qp (quadratic programming) is restricted to positive definite matrices

Submitter:  Julien Bect <jbect>
Submitted:  Mon 26 Jun 2023 07:19:41 AM UTC
   
 
Category:  Documentation Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Documentation
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * stable Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Thu 04 Jan 2024 02:44:24 PM UTC, comment #5: 

the behaviour of _qp_, I mean

Julien Bect <jbect>
Thu 04 Jan 2024 02:43:34 PM UTC, comment #4: 

Hello Arun,

Sorry for the long silence.

As reported here: https://savannah.gnu.org/bugs/?61762, it turns out that the behaviour of qp, as it is, is not reliable when H is not positive definite.

As long as a better QP solver is not used, checking for positive definiteness before calling qp is therefore the safest choice.

Regarding your patch, it means I think that:

1) "quadratic program" -> "convex quadratic program" is ok, you could even call it a "strictly convex" quadratic program

2) the matrix is expected to be positive definite (semidefinite is not enough)

3) The test for positive definiteness should stay.

Julien Bect <jbect>
Fri 17 Nov 2023 02:43:09 PM UTC, comment #3: 

There has been no response from Olaf. I'm attaching a tentative patch for this in light of this bug and bug #64901, generally following comment #1. Please check the effect of this patch as widely as you can, especially because qp() is being called as an inner optimization routine by many other optimization functions like sqp() etc.



(file #55335)

Arun Giridhar <arungiridhar>
Group Member
Mon 26 Jun 2023 10:22:05 PM UTC, comment #2: 

Julien, could you check against the bug reported in 61762:  https://savannah.gnu.org/bugs/?61762

It seems allowing non-positive definite matrices caused a crash in qp?

Copying Olaf in either case.

Arun Giridhar <arungiridhar>
Group Member
Mon 26 Jun 2023 08:58:25 PM UTC, comment #1: 

After further investigation, it turns out that this is more than a simple documentation issue.

Indeed, previously qp was able to deal with symmetric positive semi-definite matrices but, with the recent introduction of a test for positive definiteness (https://hg.savannah.gnu.org/hgweb/octave/rev/2f1fae9dd79d), these problems can no longer be addressed with qp (error code 102).

Therefore I reformulate my suggestion:

1) Rebrand this ticket as a regression issue.

2) Remove the test for positive definiteness from qp.m, or replace it with a test for positive semi-definiteness if needed (but perhaps looking at the error returned by _qp_ is enough?).

3) in the doc, quadratic program -> convex quadratic program.

4) in the doc, indicate somewhere explicitely that H is expected to be symmetric and positive semi-definite.

Julien Bect <jbect>
Mon 26 Jun 2023 07:19:41 AM UTC, original submission:  

The documentation of qp does not indicate that the matrix H is expected to be (symmetric) positive definite.  If it's not, the function fails with error code 102.

There is nothing obvious about it, since the "quadratic programming" framework allows in general, mathematically speaking, H to be any symmetric matrix.

I suggest the following fixes:

1) quadratic program -> convex quadratic program

2) indicate somewhere explicitely that H is expected to be symmetric positive definite

Julien Bect <jbect>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #55335:  qp.patch added by arungiridhar (1KiB - text/x-patch)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by arungiridhar (Posted a comment)
  • -email is unavailable- added by arungiridhar (qp positive definite or not)
  • -email is unavailable- added by jbect (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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2023-11-17 arungiridhar Attached File- Added qp.patch, #55335
    2023-11-16 arungiridhar Dependencies- bugs #64901 is dependent
    2023-06-26 arungiridhar Carbon-Copy- Added i7tiol

    Back to the top

    Powered by Savane 3.13-c373.
    Corresponding source code