bugGNU Octave - Bugs: bug #57986, qp() reports full convergence...

 
 

bug #57986: qp() reports full convergence while actually vioalating lbound/ubound:

Submitted by:  deego <deego>
Submitted on:  Wed 11 Mar 2020 07:53:57 PM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  None
Status:  Works For Me Assigned to:  None
Originator Name:  deego Open/Closed:  Closed
Release:  5.2.0 Operating System:  GNU/Linux

Add a New Comment (Rich Markup)
   

You are not logged in

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

 

( Jump to the original submission)

Tue 23 Jun 2020 08:20:23 PM UTC, comment #11: 

Seems to be something specific to the reporter's machine, rather than a general Octave bug.  Closing report.

Rik <rik5>
Project Administrator
Thu 12 Mar 2020 06:15:12 PM UTC, comment #10: 

I can't reproduce, I get the same as jwe, with either OpenBLAS or netlib BLAS, it reaches the maximum number of iterations, and all X values appear to be between -1e-33 and 1/3.

Mike Miller <mtmiller>
Project Administrator
Wed 11 Mar 2020 09:05:12 PM UTC, comment #9: 

and no match for grep atlas.

deego <deego>
Wed 11 Mar 2020 09:04:23 PM UTC, comment #8: 

Dmitri,

Thanks.

These are the results for grep blas and grep lapack:

libopenblas.so.0 => /usr/lib/x86_64-linux-gnu/libopenblas.so.0 (0x00007f26b02ea000)
libblas.so.3 => /usr/lib/x86_64-linux-gnu/libblas.so.3 (0x00007f26ad3d1000)
liblapack.so.3 => /usr/lib/x86_64-linux-gnu/liblapack.so.3 (0x00007fcbd84df000)

(This is debian 10 buster stable.)

deego <deego>
Wed 11 Mar 2020 08:58:43 PM UTC, comment #7: 

No, you running ldd on wrong binary. try "octave-cli" rather than
"octave"

Dmitri.

Dmitri A. Sergatskov <dasergatskov>
Wed 11 Mar 2020 08:56:51 PM UTC, comment #6: 

Oh, hm, I don't even see any blas/lapack linked to my compiled octave.
Did I screw up the install?

linux-vdso.so.1 (0x00007ffe173a3000)
libX11.so.6 => /usr/lib/x86_64-linux-gnu/libX11.so.6 ()
libutil.so.1 => /lib/x86_64-linux-gnu/libutil.so.1 ()
libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 ()
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 ()
libgomp.so.1 => /usr/lib/x86_64-linux-gnu/libgomp.so.1 ()
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 ()
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 ()
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 ()
libxcb.so.1 => /usr/lib/x86_64-linux-gnu/libxcb.so.1 ()
libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 ()
/lib64/ld-linux-x86-64.so.2 (0x00007fb149205000)
libXau.so.6 => /usr/lib/x86_64-linux-gnu/libXau.so.6 ()
libXdmcp.so.6 => /usr/lib/x86_64-linux-gnu/libXdmcp.so.6 ()
libbsd.so.0 => /usr/lib/x86_64-linux-gnu/libbsd.so.0 ()
librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 ()

deego <deego>
Wed 11 Mar 2020 08:47:22 PM UTC, comment #5: 

You have those blas/lapack libraries installed, but most likely
are using either openblas or atlas. What do those

ldd /usr/bin/octave-cli | grep blas
ldd /usr/bin/octave-cli | grep atlas

return?

(adjust path to octave appropriately)

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 11 Mar 2020 08:42:35 PM UTC, comment #4: 

Attaching the full file this time. Note that the problem is reproduced  only when you use precisely these numerical values (That 1 in the 18th decimal place makes a difference!)

(file #48583)

deego <deego>
Wed 11 Mar 2020 08:34:17 PM UTC, comment #3: 

Ah, found the attach link at the bottom. Will attach in future.

liblapack3:
  Installed: 3.8.0-2

libblas3:
  Installed: 3.8.0-2

deego <deego>
Wed 11 Mar 2020 08:31:01 PM UTC, comment #2: 

For the Hessian in the attached file, some kind of rich-markup garbled it. It's not even square as it appears.

All the initial entries 1., 2. are actually simply 0's

deego <deego>
Wed 11 Mar 2020 08:22:36 PM UTC, comment #1: 

It's usually better to attach code and data files or use a verbatim block to avoid the bug tracker comment processing.  For example, the first column of zeros in your H matrix were transformed to 1., 2., etc. (an enumerated list).

I'm attaching a single file that I think has the inputs the way you intended.

For me, with Octave 5.2.0 and a copy built from the current development sources, it stops at the max number of iterations (200) with the result

INFO =

  scalar structure containing the fields:

    solveiter =  200
    info =  3

ans =

   0.33333
   0.33333

octave:2> X
X =

   0.00000
   0.00000
   0.33333
  -0.00000
   0.00000
   0.33333
   0.29246
   0.00000
   0.00000
   0.00000
   0.00000
  -0.00000
   0.04087
   0.00000
   0.00000

What lapack and blas libraries (and versions) are you using?

As we discussed on IRC, I think this is a bad problem because there are decision variables that have no effect on the objective function.  I haven't tried to trace the iterations, but I suspect QP is cycling around the solution it has found until it hits the iteration limit.  Maybe we could do a better job of detecting problems like this and issue a meaningful warning?

(file #48582)

John W. Eaton <jwe>
Project Administrator
Wed 11 Mar 2020 07:53:57 PM UTC, original submission:  

##  We will report a case where qp's output  violates lbound/ubound, by some good margin!. Yet, it reports full convergence. It also reports a feasible and convex problem.

## (I have seen numerous such cases. This is just one of them.)

## I have also seen cases where I supply it a non-singular matrix, and it reports full convergence while actually violating lbound/ubound.

## We ask qp to minimize x'Hx where constraints: sum(x)=1, and each x should lie in [0,1/3], giving each x_i plenty of room to bounce around.

## Since the results are very sensitive to minor numerical variations in input arguments, I saved them carefully in a file which I am attaching.

## NOTE that the initial X is in fact qp's own prior result. (In other words, we didn't hand-construct it to violate any constraint.)
## And, in fact, it does sum to 1.

## Also note that we supplied a singular Hessian in this case. Yet, qp reported feasibily, full convergence, while actually violating lbound/ubound.

load("/tmp/argcell.octave");

[X, OBJ, INFO, LAMBDA] = qp (argcell{:});

INFO
X([3,6])

## INFO reports a full convergence on a feasible, convex solution!
## INFO =
##   scalar structure containing the fields:
##     solveiter =  33
##     info = 0

## These X's violate lbound and ubound.
## ans =
##    1.907459701005344e+00
##   -9.074597010053456e-01

## On octave 5.2.0 (compiled from source), debian 10.


Save this file to /tmp/argcell.octave

# Created by Octave 5.2.0, Wed Mar 11 15:41:44 2020 EDT <deego@jupiter>
# name: argcell
# type: cell
# rows: 1
# columns: 7
# name: <cell-element>
# type: matrix
# rows: 15
# columns: 1
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671
 0.066666656666666671

# name: <cell-element>
# type: matrix
# rows: 15
# columns: 15

  1. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  2. 50231 0 0 -1396 0 0 -1665 8060 -2224 0 0 0 17185 0
  3. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  4. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  5. -1396 0 0 85865 0 0 12652 4505 6800 0 0 0 13149 0
  6. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  7. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  8. -1665 0 0 12652 0 0 47064 12319 8069 0 0 0 10705 0
  9. 8060 0 0 4505 0 0 12319 129832 12332 0 0 0 38968 0
  10. -2224 0 0 6800 0 0 8069 12332 35004 0 0 0 7337 0
  11. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  12. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  13. 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  14. 17185 0 0 13149 0 0 10705 38968 7337 0 0 0 347070 0
  15. 0 0 0 0 0 0 0 0 0 0 0 0 0 0

# name: <cell-element>
# type: matrix
# rows: 15
# columns: 1
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0

# name: <cell-element>
# type: range
# base, length, increment
1 15 0

# name: <cell-element>
# type: scalar
1

# name: <cell-element>
# type: matrix
# rows: 15
# columns: 1
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0

# name: <cell-element>
# type: matrix
# rows: 15
# columns: 1
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331
 0.33333333333333331

deego <deego>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #48583:  argcell.octave added by deego (2KiB - application/octet-stream)
file #48582:  qptst.m added by jwe (2KiB - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by deego (Submitted the item)
  • -email is unavailable- added by deego
  •  

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

    Only project members can vote.

     

     

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-06-23 rik5 Open/ClosedOpen => Closed
    2020-03-16 mtmiller StatusNone => Works For Me
    2020-03-11 deego Attached File- => Added argcell.octave, #48583
    2020-03-11 jwe Attached File- => Added qptst.m, #48582
    2020-03-11 deego Carbon-Copy- => Added deego3@gmail.com

    Back to the top


    Powered by Savane 3.5