1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Bad news, no this is not possible to reformulate as a convex program. $\endgroup$ – Johan Löfberg Oct 19 '17 at 18:59
2
$\begingroup$

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'))
$\endgroup$
  • $\begingroup$ Thanks Johan! However, the problem I posted is just an example. I would actually implement much bigger problems that would take very long to be solved with a global solver. Do you have any advice or guidance on a convex relaxation that I could try? As I mentioned, I came across a similar problem 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. $\endgroup$ – luisba Oct 22 '17 at 17:30
  • $\begingroup$ What is "much bigger" and what are your requirements on global vs local solution, and certificate on optimality? $\endgroup$ – Johan Löfberg Oct 22 '17 at 20:34
  • $\begingroup$ By "much bigger" I mean several hundred binary decision variables in vector "x" (although variables in vector "y" will still be continuous). I need global optimality, or at least a lower bound given by a non-tight convex relaxation in which I have a measure of the gap $\endgroup$ – luisba Oct 23 '17 at 9:59
  • $\begingroup$ and the dimension of $y$? $\endgroup$ – Johan Löfberg Oct 23 '17 at 18:20
  • $\begingroup$ and are you really saying $x$ is binary (because then the whole thing is MILP-representable if needed) $\endgroup$ – Johan Löfberg Oct 23 '17 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.