I have an optimization problem with an uncommon utility: to find a $\beta$ that maximizes

$$ r^{T}\cdot H(X\cdot\beta) $$

where $H()$ is a Heaviside step function as in wiki

$r$ is a vector of size 1000

$X$ is a 1000x50 "tall" matrix

$\beta$ is a vector of size 50

I am familiar with gradient descent, which is how I usually solve an optimization problem. But Heaviside function does not work with gradient descent. So I am wondering if anyone here could shed some light on how to solve such optimization problem.



You can solve the problem via integer linear programming as follows, assuming $r_i \ge 0$ for all $i$. Let $M_i$ be a (small) upper bound on $-(X \cdot \beta)_i$. Let binary decision variable $y_i$ indicate whether $(X \cdot \beta)_i \ge 0$. The problem is to maximize $$\sum_{i=1}^{1000} r_i y_i$$ subject to $$-(X \cdot \beta)_i \le M_i(1 - y_i)$$ for all $i$. This "big-M" constraint enforces $y_i=1 \implies (X \cdot \beta)_i \ge 0$.

| improve this answer | |
  • $\begingroup$ HI Rob, thanks for answering this. but if y_{i} = 0, then X*beta>= - 1 * M_{i}; which at least overlaps with the case of y_{i} = 1 , right? $\endgroup$ – user152503 Jul 25 at 9:47
  • $\begingroup$ Yes, $y_i=0$ forces only a redundant constraint. As long as the “reward” $r_i\ge 0$, this big-M constraint is sufficient. $\endgroup$ – RobPratt Jul 25 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.