Simple convex QP cannot be solved

[cvanaret]

Hi all,
I'm interfacing the HiGHS QP solver with my solver Uno, and while running a trust-region SQP method on the instance nlp-cvx-expr/110_010 from the MINLPTests.jl benchmark, I encountered a simple convex QP that cannot be solved:

using JuMP, HiGHS

model = Model(HiGHS.Optimizer)

@variable(model, -10 <= x <= 10)
@variable(model, -10 <= y <= 10)

@objective(model, Min, x^2/2 + x)
@constraint(model, 0*x + 0*y <= 1)

optimize!(model)

produces

Running HiGHS 1.11.0 (git hash: 364c83a51e): Copyright (c) 2025 HiGHS under MIT licence terms
QP   has 1 rows; 2 cols; 0 matrix nonzeros; 2 Hessian nonzeros
Coefficient ranges:
  Cost   [1e+00, 1e+00]
  Bound  [1e+01, 1e+01]
  RHS    [1e+00, 1e+00]
  Iteration        Objective     NullspaceDim
          0         40.00001                0      0.01s
        100      -0.49999495                1      0.01s
        200      -0.49999495                1      0.01s
        300      -0.49999495                1      0.01s
        400      -0.49999495                1      0.01s
        500      -0.49999495                1      0.01s
        600      -0.49999495                1      0.01s
        700      -0.49999495                1      0.01s
        800      -0.49999495                1      0.01s
        900      -0.49999495                1      0.01s
       1000      -0.49999495                1      0.01s
       2000      -0.49999495                1      0.01s
       3000      -0.49999495                1      0.01s
       4000      -0.49999495                1      0.01s
       5000      -0.49999495                1      0.01s
       6000      -0.49999495                1      0.01s
       7000      -0.49999495                1      0.02s
       8000      -0.49999495                1      0.02s
       9000      -0.49999495                1      0.02s
      10000      -0.49999495                1      0.02s
      20000      -0.49999495                1      0.03s
      30000      -0.49999495                1      0.03s
      40000      -0.49999495                1      0.04s
      50000      -0.49999495                1      0.05s
      60000      -0.49999495                1      0.05s
      70000      -0.49999495                1      0.06s
      80000      -0.49999495                1      0.07s
      90000      -0.49999495                1      0.08s
     100000      -0.49999495                1      0.08s
     200000      -0.49999495                1      0.16s
     300000      -0.49999495                1      0.23s
     400000      -0.49999495                1      0.31s
     500000      -0.49999495                1      0.39s
     600000      -0.49999495                1      0.46s
     700000      -0.49999495                1      0.54s
     800000      -0.49999495                1      0.61s
     900000      -0.49999495                1      0.69s
    1000000      -0.49999495                1      0.77s
    2000000      -0.49999495                1      1.52s
    3000000      -0.49999495                1      2.27s
    4000000      -0.49999495                1      3.01s
    5000000      -0.49999495                1      3.77s
    6000000      -0.49999495                1      4.51s
...

Obviously the QP looks a bit weird (the constraint is trivially satisfied and the y variable doesn't appear in the objective). But I assumed that, because y is bounded, the solver would return an arbitrary finite value for y.
Note that I'm using the HiGHS C++ interface. Hope you can figure this one out :)
Thank you,
Charlie

[odow]

I can reproduce this:

#include "interfaces/highs_c_api.h"
#include <stdlib.h>
#include <assert.h>

int main(int argc, char *argv[]) {
    void* highs = Highs_create();
    assert(Highs_addCol(highs, 1.0, -2.0, 2.0, 0, NULL, NULL) == 0);
    assert(Highs_addCol(highs, 0.0, -2.0, 2.0, 0, NULL, NULL) == 0);
    assert(Highs_addRow(highs, 0.0, 0.0, 0, NULL, NULL) == 0);
    int start[2] = {0, 1};
    int index[1] = {0};
    double value[1] = {1.0};
    int format = kHighsHessianFormatTriangular;
    assert(Highs_passHessian(highs, 2, 1, format, start, index, value) == 0);
    assert(Highs_run(highs) == 0);
    Highs_destroy(highs);
    return 0;
}

[jajhall]

Thanks @cvanaret

My C++ reproduces this, and triggers an assert with HiGHS compiled in debug

[jajhall]

So, the assert was a red herring, and I now reproduce the behaviour in debug.

It would appear to be doing in active set QP, the equivalent of cycling in simplex.

I've not got time to dig into the QP solver to identify how this can be avoided. Maybe the constraint coefficients being zero is a trigger.

[jajhall]

Added example as unit test 2489