bugGNU Octave - Bugs: bug #38353, qp() fails on a feasible problem

 
 

bug #38353: qp() fails on a feasible problem

Submitter:  asherikov <asherikov>
Submitted:  Tue 19 Feb 2013 10:54:50 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 22 Nov 2021 04:38:40 AM UTC, comment #11: 

There seems to be a bug in glpk in which the return value FMIN is fed forward into component 1 of the return value XOPT.  I added an explicit workaround for this which resolves this bug.  See changeset http://hg.savannah.gnu.org/hgweb/octave/rev/c08c73d96985.

Marking as Fixed.

Rik <rik5>
Group administrator
Mon 15 Nov 2021 06:23:30 PM UTC, comment #10: 

In Octave 6.4.0, the problem in comment #0 no longer produces the error described in any of the previous comments (the most recent being 5 years and two major Octave versions ago). The two outputs of that code do differ significantly, however I cannot say that whether this is a failure:



>> load qp_debug.dat;
>> [X1, OBJ1, INFO1, LAMBDA1] = qp ([], H, q, Ge, ge, [], [], [], G, G_ub)
X1 =

   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0
   0

OBJ1 = 0
INFO1 =

  scalar structure containing the fields:

    solveiter = 0
    info = 6

LAMBDA1 = [](0x0)

>> [X2, OBJ2, INFO2, LAMBDA2] = qp (solution, H, q, Ge, ge, [], [], [], G, G_ub)
X2 =

   6.5643e-01
  -7.3860e+00
   4.6316e-01
   3.9893e+00
   3.2680e-01
   1.1984e+00
   2.3058e-01
  -2.1841e-01
   1.6269e-01
  -1.3960e-01
   1.1479e-01
   2.4953e-03
   8.0989e-02
   1.3326e-02
   5.7141e-02
   1.4720e-03
   4.0313e-02
  -1.0534e-03
   2.8438e-02
  -2.7244e-04
   2.0056e-02
   6.3237e-05
   1.4139e-02
   3.9361e-05
   9.9580e-03
   7.9299e-06
   7.0010e-03
  -5.3793e-05
   4.9041e-03
  -1.7213e-04
   3.9578e-03
   3.0603e-04

OBJ2 = -0.8400
INFO2 =

  scalar structure containing the fields:

    solveiter = 1
    info = 0

LAMBDA2 =

   0.0000
   0.0000
   0.4666
        0
   0.3095
        0
   0.2044
        0
   0.1344
        0
   0.0879
        0
   0.0571
        0
   0.0368
        0
   0.0235
        0
   0.0149
        0
   0.0093
        0
   0.0057
        0
   0.0034
        0
   0.0019
        0
   0.0010
        0
   0.0005
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0
        0


Since matlab doesn't have a matching qp function, hard to point to exactly whether this behavior is compatible, expected, correct, etc.   Since the bug has been Need Info for 5 years, closing as Won't Fix. If someone confirms that the issue is still problematic, it can be reopened then.

Nicholas Jankowski <nrjank>
Group Member
Sun 13 Nov 2016 07:23:54 AM UTC, comment #9: 

Is the problem well-formed?  I just tried the original file and code from comment #1 with the development version of Octave (4.3) and it throws the followig error.


error: glpk: A must be 64 by 96, not 64 by 94
error: called from
    glpk at line 506 column 5
    qp at line 380 column 27
    bad_qp_call at line 3 column 21



Rik <rik5>
Group administrator
Thu 04 Jun 2015 12:31:19 AM UTC, comment #8: 

I can confirm this old bug is still present on the current development version. Tested on a Debian testing 64-bit with gcc 5.1 and glpk 4.55.

Mike Miller <mtmiller>
Group Member
Thu 28 Feb 2013 09:21:42 PM UTC, comment #7: 

I've reproduced the problem in Octave 3.6.3 / glpk 4.48 on FreeBSD 9.1 amd64.

Note that some default tolerances used by glpk() function are bigger than 8e-8. If I change 'tolbnd' to a smaller value, qp() finds the solution.

asherikov <asherikov>
Tue 26 Feb 2013 04:59:46 PM UTC, comment #6: 

Linux-x86_64 and Windows 32 bits.

Michael Goffioul <goffioul>
Tue 26 Feb 2013 04:53:14 PM UTC, comment #5: 

The problem is clear--that first element which is 0 in my case and 8e-8 in yours.  I compiled a very vanilla glpk-4.47 with just -O2 as an option and similarly compiled Octave with the same vanilla -O2 but I don't see this problem.  I'm running x86_64.  Is your Linux 32-bit or 64-bit?

I think someone else will have to debug this as I can't reproduce it.

Rik <rik5>
Group administrator
Sat 23 Feb 2013 01:46:16 AM UTC, comment #4: 

The result on my computer:

abs (P(n-n_eq+1:end)) is a column vector of 0, except the first element that is: 8.08849339009994e-08
rtol =  1.49011611938477e-08
norm (btmp) = 9.61423041688342e-01

Also the secondary outputs of the glpk call are:

dummy = -8.08849339009994e-08
status = 180

Michael Goffioul <goffioul>
Sat 23 Feb 2013 01:29:48 AM UTC, comment #3: 

I upgraded to glpk-4.47 and am running the default branch (3.7.2+) under Linux and still can't reproduce this.

I set a breakpoint at line 366 of qp.m (the call to glpk) and executed the call to qp that results in "The problem is infeasible".  On my computer the status code is 180.  The results for the other variables, for comparison on the failing computer, are:


abs (P(n-n_eq+1:end)) is a column vector of all 0's.
rtol = 1.49011611938477e-08
norm (btmp) = 0.961423041688342



Rik <rik5>
Group administrator
Fri 22 Feb 2013 09:08:59 PM UTC, comment #2: 

I can reproduce the issue on the default branch (3.7.2+): under Linux with glpk-4.47 and under Windows/VS2010 with glpk-4.45.

Michael Goffioul <goffioul>
Fri 22 Feb 2013 08:57:18 PM UTC, comment #1: 

This works fine for me with version 3.6.1 on a Linux (not BSD) system.  It is possible that the particular library versions of qp and glpk that you have are the source of the problem.  I have glpk 4.38-1.

Rik <rik5>
Group administrator
Tue 19 Feb 2013 10:54:50 PM UTC, original submission:  

All matrices, which are used below, are saved in the attached file.

When qp() is called in the following way

[X, OBJ, INFO, LAMBDA] = qp ([], H, q, Ge, ge, [], [], [], G, G_ub)

it fails with status 6 'The problem is infeasible.'

However, when the known solution is given as initial guess

[X, OBJ, INFO, LAMBDA] = qp (solution, H, q, Ge, ge, [], [], [], G, G_ub)

the function finishes successfully.


I've made a quick check and found out that the last part of this condition in qp.m fails

            if ((status == 180 || status == 181 || status == 151)
                && all (abs (P(n-n_eq+1:end)) < rtol * (1 + norm (btmp))))

I suspect that the problem is related to tolerances used in qp() and glpk().

asherikov <asherikov>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #27483:  qp_debug.dat.gz added by asherikov (4KiB - 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 mtmiller (Updated the item)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by asherikov (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 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-11-22 rik5 StatusWont Fix Fixed
    2021-11-15 nrjank StatusNeed Info Wont Fix
        Open/ClosedOpen Closed
    2016-11-13 rik5 StatusConfirmed Need Info
    2015-06-04 mtmiller StatusWorks For Me Confirmed
        Release3.6.1 dev
        Operating SystemBSD Any
    2013-10-28 mtmiller CategoryNone Octave Function
    2013-02-22 rik5 StatusNone Works For Me
    2013-02-19 asherikov Attached File- Added qp_debug.dat.gz, #27483

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code