search

darnstrom / DAQP.jl

Julia interface for the Quadratic Programming solver DAQP
MIT License
8 stars 2 forks source link

Absolute value of dual #4

Closed blegat closed 2 years ago

blegat commented 2 years ago

I am a bit surprised by this line: https://github.com/darnstrom/DAQP.jl/blob/5505e4b373dbcd7ed701c3b4682fac79b9cadfb1/src/MOI_wrapper/MOI_wrapper.jl#L202 It seems to pass all MOI tests so I might be missing something but I don't see how that works for MOI.LessThan and MOI.Nonpositives. For these sets, the dual is expected to be nonnegative so taking an absolute value shouldn't work.

darnstrom commented 2 years ago

Do you mean that the dual is expected to be negative for LessThan/Nonpositives? (otherwise I don't see your point since the cited line ensures nonnegativity) Internally, dual variables are negative for lower bounds in DAQP, but when running the MOI tests I got a sign error, so I thought that the convention used in MOI was nonnegative dual variables (hence the absolute value).

odow commented 2 years ago

Do you mean that the dual is expected to be negative for LessThan/Nonpositives?

Yes. https://jump.dev/MathOptInterface.jl/dev/background/duality/

It seems to pass all MOI tests so I might be missing something

Yeah, surprising. Unless it's skipping the relevant tests for some other reason?

Ah. It's probably this:

https://github.com/darnstrom/DAQP.jl/blob/5505e4b373dbcd7ed701c3b4682fac79b9cadfb1/src/MOI_wrapper/MOI_wrapper.jl#L260-L266

We don't have an objective bridge from variable to affine, and affine to quadratic, so this is probably skipping all tests in which a non-quadratic objective is set!

darnstrom commented 2 years ago

Thanks for bringing this to attention @blegat and for the clarification @odow . The main error was that MOI uses the opposite sign convention (in DAQP dual variables for upper bounds are positive, and for lower bounds they are negative), and, with a bit of "luck" (or rather bad luck), all dual variables that were tested were positive, leading to the abs() slipping through the tests. This sign error is addressed in #6, where also support for LPs is stable enough to uncomment line 263 mentioned above, allowing for more MOI tests to run.

odow commented 2 years ago

in DAQP dual variables for upper bounds are positive, and for lower bounds they are negative

Where does that convention come from???

For the bad luck: MOI v1.7.0 adds a new bridge that converts from affine to quadratic objectives, which would have prevented this bug.

darnstrom commented 2 years ago

Where does that convention come from???

It is used in, for example, Convex Optimization by Boyd & Vandenberghe