Skip to content

[BUG] incorrect "optimal" solution on nonconvex qcqp #1434

@mlubin

Description

@mlubin

Describe the bug

Claude-generated LP file is below. The comments describe how cuOpt returns an answer that is incorrectly declared optimal.

\     maximize  x0 + x1
\     subject to  x0 + x1     <= 100            (trivial slack row)
\                 2 x0 * x1   <= 0.5            (binding indefinite quadratic)
\                -1 <= x0, x1 <= 1
\
\ True optimum: 1.25  at (x0, x1) = (1, 0.25) (or (0.25, 1)).
\   max x0 + x1 s.t. x0*x1 <= 0.25, bounds [-1,1]
\   --> on x0*x1 = 0.25 with x0 in [0.25, 1], obj = x0 + 0.25/x0; convex U-shape
\       minimized at x0 = 0.5 (obj 1.0), maximized at the endpoints x0 = 1
\       and x0 = 0.25 (obj 1.25). The bound x0 <= 1 is the binding side.
\
\ With cuOpt's general-path LDLT silently dropping indefinite blocks, the
\ quadratic constraint is lost and the solver reports obj = 2 at (1, 1) --
\ violating x0*x1 = 1 > 0.25.
\
\ Path:
\   LP parser splits "2 x0 * x1" into the symmetric COO pair (0,1,1)+(1,0,1)
\   via lp_parser.cpp build_symmetric_q_coo.
\   Nonzero rhs (0.5) sets has_nonzero_rhs in the SOC dispatcher
\   (translate_soc.hpp:264, 277), forcing the general convex-quadratic path.
\   That builds symmetric H = [[0,2],[2,0]] -- indefinite with zero diagonals.
\   right_looking_ldlt's diagonal-only Markowitz cannot pivot, breaks at
\   rank=0 with no INDEFINITE_MATRIX_RETURN sentinel, and the rotated/SOC
\   construction emits a trivially-feasible 2D cone -- the quadratic
\   constraint is silently dropped.
\
\ Choosing rhs = 0.5 (not -0.5) keeps the dropped cone's downstream
\ s_0 = alpha + 0.5 = 1, s_{r+1} = alpha - 0.5 = 0 feasible (||0|| <= 1),
\ so the barrier converges cleanly to the wrong answer instead of bailing
\ with a numerical error.
Maximize
 obj: x0 + x1
Subject To
 c0: x0 + x1 <= 100
 q0: [ 2 x0 * x1 ] <= 0.5
Bounds
 -1 <= x0 <= 1
 -1 <= x1 <= 1
End

Steps/Code to reproduce bug
Run cuopt_cli with the above LP file as input.

Expected behavior
An explicit error rejecting the nonconvex QCQP, or a generic numerical error.

Environment details (please complete the following information):
Local build of cuOpt 26.06

Metadata

Metadata

Labels

awaiting responseThis expects a response from maintainer or contributor depending on who requested in last comment.bugSomething isn't working

Type

No type
No fields configured for issues without a type.

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions