# How to optimize a utility function that contains step function?

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.

Thanks

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$$.
• Yes, $y_i=0$ forces only a redundant constraint. As long as the “reward” $r_i\ge 0$, this big-M constraint is sufficient. – RobPratt Jul 25 at 13:28