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

Operations Research Asked on January 5, 2022

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 1000×50 "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$$.

Answered by RobPratt on January 5, 2022

## Related Questions

### Conditions required for strong duality to hold for SDPs

1  Asked on August 19, 2021

### Relationship between extreme points and optimal solutions of SDPs

1  Asked on August 19, 2021

### How to parallelize metaheuristics algorithms (Island Model)?

1  Asked on August 19, 2021 by antarctica

### Can we get closed form solution for such a problem?

1  Asked on August 19, 2021

### Can we use reinforcement learning and convex optimization to solve an optimization problem?

2  Asked on August 19, 2021 by qinqinxiaoguai

### Nonlinear integer (0/1) programming solver

6  Asked on March 1, 2021 by rajya

### How can I find the shortest path for all nodes in a graph from a source $s$?

1  Asked on March 1, 2021 by windbreeze

### Free solver for MINP problems

1  Asked on February 18, 2021 by dspinfinity

### Where I can study some job shop scheduling by course (video )?

0  Asked on February 18, 2021 by yue-chao

### Linear objective function with power term in constraint

1  Asked on February 15, 2021 by user152503

### Formulating these logical constraint in an ILP

1  Asked on January 18, 2021

### Modeling the multiplication of two binary decision variables in undirected graph in python

0  Asked on January 18, 2021 by amedeo

### Flexible Job Shop with Preemption

0  Asked on January 15, 2021 by robert-hildebrand

### How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?

3  Asked on January 11, 2021 by stevgates

### What is the difference between min- cut formulation and (bi) partitioning formulation?

1  Asked on January 8, 2021 by fathese

### Logical constraint in ILP

1  Asked on December 22, 2020 by che

### Quasi-convex function must be “partially monotonic”?

1  Asked on December 13, 2020 by high-gpa

### Constraint programming resources

3  Asked on November 28, 2020 by joffrey-l

### Pyomo variable creation dilemma

1  Asked on October 31, 2020 by ethan-deakins

### Convexity of the variance of a mixture distribution

1  Asked on September 25, 2020 by independentvariable