Accessing the piecewise-linear approximation of a nonconvex quadratic optimization problem

Answered

Shuvomoy Das Gupta

October 22, 2021 15:18 Edited

• 
• 
• 

I am trying to solve a nonconvex quadratic optimization problem of the form:

$$
p^{\star}=\left(\begin{array}{ll} \textrm{minimize} & c^{\top}x\\ \textrm{subject to} & a_{i}^{\top}x+x^{\top}Q_{i}x-b_{i}\leq0,\quad i\in[1:m], \end{array}\right)\quad(1)
$$

where `x` is the decision variable, and the matrices `Q_1, ..., Q_m` are not positive-semidefinite. In https://www.gurobi.com/documentation/9.1/refman/constraints.html, I see that Gurobi converts these nonconvex quadratic constraints into piecewise-linear constraints. If I set FuncPieceRatio to 1.0, these piecewise-linear constraints will provide overestimators of the nonconvex constraints. In such a case, if `a_i^T x+x^T Q_i x - b_i` has the piecewise-linear overestimate `f_i(x)`, then we have

$$
a_{i}^{\top}x+x^{\top}Q_{i}x-b_{i}\leq f_{i}(x),
$$

and the corresponding problem

$$
\underline{p}^{\star}=\left(\begin{array}{ll} \textrm{minimize} & c^{\top}x\\ \textrm{subject to} & f_{i}(x)\leq0,\quad i\in[1:m], \end{array}\right)\quad(2)
$$

will provide a lower-bound on the original nonconvex problem, as

$$
f_{i}(x)\leq0
$$

implies

$$
a_{i}^{\top}x+x^{\top}Q_{i}x-b_{i}\leq0.
$$

For my specific problem, if a solution to (2) can be obtained, then I can construct a good enough solution to (1) which suffices for my purpose.

Is there a way we can access model (2) or a solution to it?

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:45 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  October 25, 2021 07:51

  Strictly speaking, Gurobi does not construct piecewise-linear constraints but rather adds linear constraints only to construct a linear (convex) relaxation of the nonconvex quadratic problem. These linear constraint cannot be controlled by parameters like FuncPieceRatio unless you are explicitly using general constraints.

  In particular, Gurobi will not construct an overestimator to your constraints but an underestimator to obtain a lower bound on the original nonconvex problem. If one would use the overestimator, it is possible to cut off feasible solutions of the original problem and ultimately cut off the optimal solution of the original problem.

  You can find more details in the Non-Convex Quadratic Optimization webinar and books on global optimization such as Horst & Tuy 1999 and/or Locatelli & Schön 2013.

  Is there a way we can access model (2) or a solution to it?

  Currently, there is no way to access model (2). However, you can access the solution of it via callbacks. For example, you could access the solution point of the relaxation of the rootnode via

  if where == GRB.Callback.MIPNODE:
    # check for root node
    if model.cbGet(GRB.Callback.MIPNODE_NODCNT) == 0:
      # check for optimization status of the relaxation LP
      if model.cbGet(Grb.Callback.MIPNODE_STATUS) == GRB.OPTIMAL:
        # get relaxation solution point
        rel_sol_pt = model.cbGetNodeRel(model.getVars())

  Best regards,
  Jaromił

  0
• 

  Shuvomoy Das Gupta

  October 25, 2021 10:29

  • 
  • 
  • 

  Hi Jaromił,

   

  Thanks for your very clear answer, accessing the solution point of the relaxation of the root node works fine for my purpose. 

  0

Post is closed for comments.