Linear program with several non-convex constraints

Question

I have an optimization problem in which the objective function and most constraints are linear, but I also have several nonlinear (and nonconvex) constraints. I am wondering if my problem can be reformulated as a convex one, or if you have some advice on how to approach it.

This is the problem I have:

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & c^{\textrm{T}} x \\ & \text{subject to} & & x\geq 0\\ & & & x_i \leq \textrm{UpperBound}_i\\ & & & \textrm{A}x\leq \textrm{b}\\ \end{aligned} \end{equation*}

Up to now I just have a linear program, but I also have several quadratic constraints on auxiliary variables $y$: \begin{equation*} \begin{aligned} & \text{subject to} & & \textrm{D}x + \textrm{e}= y\\ & & & \textrm{if}\ \ (y_{12}\leq y_{11})\\ & & & \qquad y_1\cdot y_2 \geq y_3^2 -y_3\cdot y_4\\ & & & \textrm{if}\ \ (y_{13}\leq y_{11})\\ & & & \qquad y_5\cdot y_6 \geq y_7^2 -y_7\cdot y_4\\ & & & \textrm{if}\ \ (y_{14}\leq y_{11})\\ & & & \qquad y_8\cdot y_9 \geq y_{10}^2 -y_{10}\cdot y_4\\ \end{aligned} \end{equation*}

The auxiliary variables $y$ are defined by the equality constraints $\textrm{D}x= y$ (although I think it is possible to define them as $\textrm{D}x\leq y$ and it would still hold). The last 3 constraints in the problem are quadratic.

Note that these quadratic constraints are also conditional (I implement these conditional constraints by using big-M's). At least one of the quadratic constraints is always enforced, but two or all three might be enforced.

I know that they are non-convex constraints, because matrix $Q$ is indefinite in this equivalent formulation of the quadratic constraint:

$$ [y_1, y_2, y_3, y_4]\ \textrm{Q}\ [y_1, y_2, y_3, y_4]^\textrm{T}\leq 0 $$ where \begin{equation*} Q= \begin{bmatrix} 0&-1/2&0&0\\ -1/2&0&0&0\\ 0&0&1&-1/2\\ 0&0&-1/2&0\\ \end{bmatrix} \end{equation*}

Do you have any advice on how to tackle this problem? I have found something similar in Appendix B1 of Stephen's Boyd book, but I think it doesn't hold for my problem since I have more than one quadratic constraint.

Thanks for your help!

Answer 1

As a follow up on my comment, this is intrinsically nonconvex. However, it appears to be reasonably easy to solve with a global mixed-integer nonlinear solver.

In this code, I experiment with the very basic built-in global solver in the MATLAB Toolbox YALMIP (disclaimer, developed by me). These problem instances are solved in a couple of seconds to global optimality (for performance a good LP solver is required (Gurobi, Mosek, Cplex) and a local nonlinear solver is required, fmincon was used in the experiments)

n = 15; 
m = 25;   
A = randn(m,n);b = 5*rand(m,1);
c = randn(n,1);
e = randn(14,1);
D = randn(14,n);

x = sdpvar(n,1);
y = sdpvar(14,1);

p1 = y(1)*y(2)-(y(3)^2-y(3)*y(4));
p2 = y(5)*y(6)-(y(7)^2-y(7)*y(4));
p3 = y(8)*y(9)-(y(10)^2-y(10)*y(4));

Model = [0 <= x <= 5, A*x <= b, y == D*x + e,
         implies(y(12)<=y(11), p1 >=0)
         implies(y(13)<=y(11), p2 >=0)
         implies(y(14)<=y(11), p3 >=0)];
Objective = c'*x;

optimize(Model,Objective,sdpsettings('solver','bmibnb'))