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
  • 1
    $\begingroup$ Bad news, no this is not possible to reformulate as a convex program. $\endgroup$ Commented Oct 19, 2017 at 18:59

1 Answer 1

Reset to default
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$
7
  • $\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$ Commented Oct 22, 2017 at 17:30
  • $\begingroup$ What is "much bigger" and what are your requirements on global vs local solution, and certificate on optimality? $\endgroup$ Commented Oct 22, 2017 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$ Commented Oct 23, 2017 at 9:59
  • $\begingroup$ and the dimension of $y$? $\endgroup$ Commented Oct 23, 2017 at 18:20
  • $\begingroup$ and are you really saying $x$ is binary (because then the whole thing is MILP-representable if needed) $\endgroup$ Commented Oct 23, 2017 at 18:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.