The result of relaxing to an integer program is the following optimization problem: $$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$ where $\textbf{x}=(x_1,\cdots, x_n)^T$, $\alpha_i \in \mathbb{R}$, $A\in\mathbb{R}^{m\times n}$ with $m<n$ ($A$ is a fat random Gaussian matrix). The function $h$ is the Heaviside function $$ h(x) = \left\{ \begin{array}{lr} 1 & x \geq 0\\ 0 & x <0 \end{array}. \right. $$ Given a point $\textbf{x}^*$, what is a rather general sufficient condition (in terms of $A$ and $\alpha_i$) for $\textbf{x}^*$ to be a global minimizer to the program above? For instance when $\textbf{x}^*$ is in the feasible subspace and $sign(x_i^*)= - sign(\alpha_i)$, then $\textbf{x}^*$ is a global minimizer. What happens when there are components of $\mathbf{x}$ for which $sign(x_i^*)\neq - sign(\alpha_i)$?
In case there is no immediate response to this, are there any well-known techniques (e.g., formulating everything in terms of a convex problem) to handle this? Are there any useful literature that I can refer to?
-Thanks
