Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add SOCtoQuad bridge #478

Closed
wants to merge 1 commit into from
Closed

Add SOCtoQuad bridge #478

wants to merge 1 commit into from

Conversation

blegat
Copy link
Member

@blegat blegat commented Aug 19, 2018

Adds a SOCtoQuad bridges which allows to use the

@constraint(model, [t, x, y] in SecondOrderCone())

with solvers expecting SOC constraint in quadratic form (e.g. LQOI solvers).

It also add missing methods in MOIU for quadratic functions.
While doing this, I noticed, that the _pair and _canonicalize functions of src/functions.jl were doing the same thing than MOIU.termindices and MOIU.coefficient. Hence I moved coefficient and termindices (rename term_indices following the style guide) to MOI and renamed and documented _pair into term_pair.
I also noticed that we have both MOI._constant and MOIU._constant hence I have removed MOIU._constant. We should still replace this by a function with a better name and doc but this will not be addressed in this PR.

Closes JuliaOpt/MathOptInterfaceBridges.jl#92

@codecov-io
Copy link

codecov-io commented Aug 19, 2018

Codecov Report

Merging #478 into master will decrease coverage by 0.58%.
The diff coverage is 83.78%.

Impacted file tree graph

@@            Coverage Diff            @@
##           master    #478      +/-   ##
=========================================
- Coverage   95.38%   94.8%   -0.59%     
=========================================
  Files          46      47       +1     
  Lines        4681    4715      +34     
=========================================
+ Hits         4465    4470       +5     
- Misses        216     245      +29
Impacted Files Coverage Δ
src/Bridges/Bridges.jl 100% <100%> (ø) ⬆️
src/Bridges/bridge.jl 100% <100%> (ø) ⬆️
src/Bridges/bridgeoptimizer.jl 97% <100%> (+0.06%) ⬆️
src/Bridges/soctoquadbridge.jl 80% <80%> (ø)
src/Bridges/squarepsdbridge.jl 68.33% <0%> (-28.34%) ⬇️
src/Bridges/soctopsdbridge.jl 89.09% <0%> (-10.91%) ⬇️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update c55e167...8e7809d. Read the comment docs.

t_nonneg::CI{G, MOI.GreaterThan{T}}
end
function SOCtoQuadBridge{T, F, G}(model::MOI.ModelLike,
f::MOI.AbstractVectorFunction,
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This transformation is recognized by Gurobi/Cplex/Xpress(?) only when f is a VectorOfVariables. They can't handle general affine expressions. That creates a tricky situation because we don't have a way to indicate this restriction in MOI afaik, so I'm questioning if bridges are the right place for this transformation to happen. Maybe the solvers need to support VectorOfVariables-in-SecondOrderCone and then let a bridge handle only the transformation from VectorAffineFunction-in-SecondOrderCone to VectorOfVariables-in-SecondOrderCone.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

They also support x^T Q x +q^T x <= b apparently: http://www.gurobi.com/documentation/8.0/refman/constraints.html#subsubsection:QuadraticConstraints
so if it is a VectorAffineFunction in SOC, it will be transformed into x^T Q x +q^T x <= b with Q PSD an Gurobi will also support it, won't it ?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This bridge does not generate a constraint of the form x^T Q x +q^T x <= b where Q is PSD (there's one negative eigenvalue).

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Indeed, good point. This bridge could create a vector of variables and constraint them to be equal to the affexpr and then use these auxiliary variables to create the quadratic function. This would not only make sense for Gurobi as taking the square of complicated affine expression may not result in a very simple quadratic function so it might be the right idea anyway.
Would that work ?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That works for Gurobi et al, but I think there's a larger design issue. Ipopt supports convex and non-convex quadratic constraints but not SOC constraints (there's no special detection for x^T x <= t^2). It this bridge is applied, Ipopt will treat the constraint as a nonconvex quadratic constraint without any guarantees of global optimality. Unless there are additional properties of this transformation that imply that a KKT point must be globally optimal (even though the problem is nonconvex), this means that the user could write down a convex problem using SOC and get a bad answer back from Ipopt.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We discussed about this issue with @mlubin and @ccoffrin. The approach would be to define this bridge in MOI but not add it in full_bridge_optimizer so that the user would have to add it manually with JuMP.add_bridge. By choosing which bridge to add, it would either allow VectorOfVariables-in-SOC or VectorAffineFunction-in-SOC to add so he is responsible to add the one with which the optimizer works.
IMO the optimizer could also simply apply the bridge automatically by itself with a SingleBridgeOptimizer. Choosing to build the API on top of quadratic functions instead of SOC constraints was a bad design choice and this is the reason this bridge seems weird because it destroys a structure that the optimizers try to recover afterwards.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since the three solvers support SOC´s as special quadratic constraints, the bridge could be very useful. Given Ipopt's problem, we could have it non-default, and add a note about the issue.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@joaquimg IMO the right solution for this is for Gurobi/Xpress/CPLEX to explicitly support VoV/VAF-in-SOC in their interfaces. We have no other way to know if a solver secretly supports SOC through quadratic constraints.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this means that the user could write down a convex problem using SOC and get a bad answer back from Ipopt.

Regarding this point. As I understand the theory, it does not matter in what form a convex constraint is given to a IPM solver. The KKT convergence guarantees will be the same; so I don't think this a major issue for the case of targeting NLP solvers.

@joaquimg
Copy link
Member

replaced by #1046

@joaquimg joaquimg closed this Jun 10, 2020
@odow odow deleted the bl/soctoquad branch June 22, 2020 02:57
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

VectorAffineFunction-in-SecondOrderCone -> ScalarQuadraticFunction-in-LessThan bridge
5 participants