Mixed Integer Formulation of Nonconvex program

71 Views Asked by At

I have the following optimization problem:

\begin{align} \min_{x,s,\lambda,\gamma} \quad J(x)\\ f(x)=0\\ h(x,\gamma,s)\leq0\\ \lambda^\top Gx \leq s\\ \lambda^\top e=1\\ \lambda\geq 0\\ \|G^\top \lambda\|\leq \gamma \end{align}

where $x \in \mathcal{X} \subset \mathbb{R}^n$, $s \in \mathbb{R}$, $\mathcal{X}$ is a convex set, $f(x)$ and $h(x)$ are affine functions, $J(x)$ is a quadratic function, $e$ is a vector consisting of all ones.

I know that the second constraint is a bilinear one. Is there any method to reformulate this problem into a mixed integer program? I know that constraints (3)-(5) could be reformulated into constraint on pointwise minimum, if there was no last constraint.

1

There are 1 best solutions below

0
On

There are at least a couple of ways to approximate the bilinear constraint with linear constraints, possibly using some binary variables in the process. I can't think of any way to linearize it exactly.