# Minimize sum of ReLU

I am trying to minimize a function of the following form $$f(\vec{x}) = \sum_{i = 1}^n\operatorname{ReLU}(\vec{v}_i \cdot \vec{x} + b_i)$$

$$x \in \mathbb{R}^m$$ with $$m$$ around $$100$$ to $$1000$$ and $$n$$ around $$10^5$$ to $$10^7$$. I wish to get to the global minimum as soon as possible. What are some methods I should try?

Things I tried:

a) gradient descent with line search, but it seems to get stuck and not progress due to all the discontinuous derivatives.

b) When doing line search, optimum occurs at a pivot (where derivative jumps). Thus by sorting the pivots and doing cumsum to get derivatives around the pivots, I can just choose the lowest pivot point. But this has the same issue of derivative being chosen in the direction where I can't make any more progress.

Introduce nonnegative variables $$y_i$$ and minimize $$\sum_i y_i$$ subject to linear constraints $$y_i \ge v_i \cdot x + b_i$$
• I provided the exact derivative. But it was still very slow. I used linprog. But by creating slack variables, I now have around $10^7$ variables and $10^7$ constraints. I think the problem becomes too massive.
• @JEK Are you using a sparse constraint matrix? Can you share the raw input data ($v$ and $b$)? Jul 28, 2022 at 12:53