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

 
 

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

Submitter:  deego <deego>
Submitted:  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
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group 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>
Group Member
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>
Group 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
  •  

    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 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 -email is unavailable-

    Back to the top

    Powered by Savane 3.13-3230.
    Corresponding source code