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?


  • $\begingroup$ You say your problem is a relaxation: can you include the original problem you are relaxing in this way, and why you choose such a relaxation? I don't know any conditions for global minima for nonconvex programming, but maybe your original problem can be relaxed to a convex program. $\endgroup$ – Cristóbal Guzmán Apr 28 '14 at 22:20
  • $\begingroup$ Thanks Cristobal. Actually the initial problem is not very easy to explain (I will email you the details). I already have a convex relaxation to that problem. The problem above is a better approximation (than the convex form) that under some conditions on the $\alpha_i$ values becomes equivalent to the combinatorial cost. The ultimate goal is to use this program as an intermediate program to show the convex formulation and the combinatorial form coincide under certain criteria. $\endgroup$ – Ali Apr 28 '14 at 23:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.