How to optimize a utility function that contains step function?

Question

I have an optimization problem with an uncommon utility: to find a $beta$ that maximizes
$$
r^{T}cdot H(Xcdotbeta)
$$
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.

RobPratt · Answer

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$.

How to optimize a utility function that contains step function?

One Answer

Add your own answers!

Ask a Question