Inequality constraints of convex relaxation with McCormick envelope

171 Views Asked by At

I have a nonconvex optimization problem for which I am calculating a lower bound using the McCormick envelope. Each bilinear term is replaced with an auxiliary variable which has the following constraints defined: $$w_{ij} \ge x_i^L * x_j + x_i * x_j^L - x_i^L * x_j^L$$ $$w_{ij} \ge x_i^U * x_j + x_i * x_j^U - x_i^U * x_j^U$$ $$w_{ij} \le x_i^U * x_j + x_i * x_j^L - x_i^U * x_j^L$$ $$w_{ij} \le x_i^L * x_j + x_i * x_j^U - x_i^L * x_j^U$$ where $$x_U <= x <= x_L$$

I am given a function taking in several arguments:

def convex_bounds(n,m,c,H,Q,A,b,lb,ub):
    #   n is the number of optimization variables
    #   m is the number of eq constraints
    #   H = positive, semidefinite matrix from objetcive function (n x n)
    #   Q is (mxn) x n 
    #   A is m x n
    #   b is RHS of non linear eq constraints (m x 1)
    #   c,lb,ub are vectors size (n x 1)
    ......................................
    # Create matrix B & b_ineq for inequality constraints
    # where B*x <= b_ineq
    B = np.eye(3)
    b_ineq = np.array((10,10,10))
    ## these values would work in a scenario with no bilinear terms

My problem is that I don't know how to specify the inequality constraints matrix B and vector $b_ineq$. For this particular exercise my variables are x1, x2 and x3 with bounds 0 $(x_L)$ and 10 $(x_U)$. My bilinear terms are $x_{12}$ and $x_{23}$ (which will lead to auxiliary variables $w_{12}$ and $w_{23}$). How can I specify the known bounds (0 and 10) for x1,x2 and x3 and the calculated ones (as in the theory pasted above) in B and b_ineq?

I don't actually know how to proceed with this.