I have a non-convex binary programming problem: \begin{align} \min_{x,y,z}~& A^\top z + x^\top H y \\ \text{s.t} &\quad z\in \mathbb{Z}^+,\\ &\quad 0\leq z\leq 1, \\ &\quad y_{min}z \leq y \leq y_{max}z,\\ &\quad Cy-Dx=0, \\ \end{align} where $x\in\Re^{n}$, $y\in\Re^{n}$, $C$ and $D$ are given full rank square matrices. Does anyone know how to deal non-convex term $x^\top H y$ in the objective function?
Linearize? or Change of variable? And how to do it?
Many Thanks!
It depends on the data. If $x$ is given uniquely by solving the system of equations, $x = Gy$, you can simply check if $G^TH+HG$ is positive semidefinite. If it is, you are done as you have a convex mixed-integer QP. If it is indefinite/negative definite, or your equation is underdetermined in $x$, you will not arrive at a convex MIQP, and you have to take another approach.
One possibility is to look at the problem as a bilevel program, where you look at the problem w.r.t $x$ and $y$ as an inner nonconvex QP with $z$ as a parameter, and then on the outer stage you optimize for $z$. When doing so, you can replace optimality of $x$ and $y$ with kkt conditions (a nonconvex QP can be solved by writing KKT conditions using binary variables, and then using the fact that the quadratic indefinite objective can be written as a linear function of the duals, and the "right-and-side" of the inequalities. The only remaining problem then is that the right-hand-side in the inner program involves $z$, so the normally linear objective will actually be bilinear in $z$ and the duals. However, as $z$ is binary, this expression can be linearized.)
Pretty involved perhaps, but here is an example using the MATLAB toolbox YALMIP just as a proof-of-concept.
% Generate random problem n = 3; m = 2; H = randn(m,n); A = randn(n,1); ymin = -rand(n,1); ymax = rand(n,1); x = sdpvar(m,1); y = sdpvar(n,1); z = binvar(n,1); Model = [ymin.*z <= y <= ymax.*z, x == randn(m,n)*y]; % Inner problem Objective = x'*H*y; % Derive KT conditions [KKTModel,details] = kkt(Model,Objective,z); % Express the indefinite quadratic using duals newObjective = (details.c'*details.primal-details.b'*details.dual)/2; % Big-M linearize since details.b involves binary parameters z [LinearObjective, cut] = binmodel(newObjective, [0 <= details.dual <= 1e4]); % Solve outer problem optimize([Model, KKTModel, cut], A'*z+LinearObjective) value([x;y;z]) % Compare with simply calling a global solver optimize(Model,A'*z + x'*H*y,sdpsettings('solver','bmibnb')) value([x;y;z]) 