How does Gurobi handle 'convex-quadratic' variables in nonconvex optimization?
Answered
I am planning to implement an algorithm that solves multiple subproblems of the form
\[\begin{align} \underset{\boldsymbol{x},\boldsymbol{y}^i,\boldsymbol{z}^i,t}{\min} &&f(\boldsymbol{x}) & \\
\text{s.t. } &&g(\boldsymbol{x})+t &\leq 0 \\
&&A^i\boldsymbol{y}^i+B^i\boldsymbol{z}^i &= \boldsymbol{h}(\boldsymbol{x}) \quad \forall i \in \{1,...n\} \\
&&(\boldsymbol{y}^{i})^T\boldsymbol{y}^i &\leq t \quad \forall i \in \{1,...n\} \\
&&0 &\leq t
\end{align}\]
where only a few variables \(\boldsymbol{x} \) appear in a nonconvex way.
I am fairly certain that most global optimizers, including Gurobi, will not branch on the 'linear' variables \(\boldsymbol{z} \).
However, I wonder how Gurobi handles the "convex-quadratic" variables \(\boldsymbol{y} \).
Does Gurobi avoid branching on them by:
a) adding cuts in the corresponding convex constraints instead of branching on them,
b) solving QCQP-based relaxations instead of the usual LP-based relaxation?
Knowing this would help me decide if adding Gurobi as a subsolver is worth it. The documentation talks about 'outer approximation', which often refers to gradient-based cuts added in 'convex' MINLP, but it seems that the documentation uses it to describe all (for example McCormick-based) linear relaxations.
If a) is false, is Gurobi adding cuts generated from the convex quadratic constraints at the root node? Is there an option (like OutGrid in Baron) that would control the number of such cuts being generated?
-
Hi Aron,
I am fairly certain that most global optimizers, including Gurobi, will not branch on the 'linear' variables \(z\).
This is correct.
However, I wonder how Gurobi handles the "convex-quadratic" variables \(y\).
Just for completeness as it may not be standard across the optimization field. By a "convex-quadratic" variable, we mean a variable that participates only in linear and convex-quadratic constraints.
If a continuous variable participates only in linear or convex quadratic constraints, Gurobi will not branch on this variable.
adding cuts in the corresponding convex constraints instead of branching on them,
Gurobi handles convex quadratic constraints separately from nonconvex quadratic ones. Gurobi will generate appropriate cuts for convex quadratic constraints. These cuts are generated also outside of the root node. No branching on such constraints will be performed (unless some of the variables participate in nonconvex constraints).
Gurobi may solve continuous convex QCQP relaxations. This is chosen automatically or can be controlled by the MIQCPMethod parameter.
Is there an option (like OutGrid in Baron) that would control the number of such cuts being generated?
There is no parameter to control the number of generated cuts in Gurobi.
In general, it should be worth it to at least try Gurobi for your subproblems.
Best regards,
Jaromił1 -
Thank you Jaromił,
> By a "convex-quadratic" variable, we mean a variable that participates only in linear and convex-quadratic constraints.
I did not define it properly, but you seem to have gotten my meaning. Just to clarify, \(\boldsymbol{y} \) technically also appears in non-convex constraints, but only linearly, but I guess that should not be a problem. Similar to 'linear' variables, Gurobi should be able to detect it. Otherwise, I can anyways reformulate with additional 'linear' variables.
With this information, it sounds very promising to use Gurobi as a subsolver.
> Gurobi may solve continuous convex QCQP relaxations. This is chosen automatically or can be controlled by the MIQCPMethod parameter.
In my case, the function \(\boldsymbol{h} \) might be a polynomial (not necessarily quadratic). Does MIQCPMethod still enable QCQP relaxations, or only if it is a nonconvex QCQP?0 -
In my case, the function \(h\) might be a polynomial (not necessarily quadratic). Does MIQCPMethod still enable QCQP relaxations, or only if it is a nonconvex QCQP?
The parameter only works for quadratic models. However, you can reformulate your polynomial into a quadratic model via auxiliary variables. Karia et al. have shown that this reformulation is quite promising, in particular with Gurobi.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments