Minimum of a sum of nonnegative monomials

Question

Let $c,d\in\mathbb R$ and $f:[c,d]\rightarrow\mathbb R$ such that

$$ f(x)=\sum^N_{i=1}\max(a_i+b_ix,0),\text{for}\ a_i,b_i\in\mathbb R, i=1,...,N $$

How to find $x$ on a closed subset of $\mathbb R$ (i.e. $x\in[c,d]$) such that $f$ is minimized ?

i.e. How to determine $$ \min_{x\in[c,d]} f(x)=\min_{x\in[c,d]}\left (\sum^N_{i=1}\max(a_i+b_ix,0)\right ),\text{for}\ a_i,b_i\in\mathbb R, i=1,...,N $$ ?

• Is there a general way to do it ? or is it on a case-by-case ?

• In this case : Does $x$ need (at most) to belong to the frontier of $[c,d]$ i.e. $x\in\{c,d\}$ since they are monomials ?

Answer 1

Your function is convex. A simple method is bisection search. Start with the interval $[c,d]$, consider the midpoint $m=(c+d)/2)$ and compute the subdifferential at $m$. The subdifferential is an interval $[l,u]$ where $$ l = \sum_{i : a_i+b_ix > 0 } b_i \\ u = \sum_{i : a_i+b_ix \geq 0} b_i $$ if 0 is in the subdifferential, you have found the optimum. If $u < 0$, the optimum is to the right of $m$, so you continue on the interval $[m,d]$. Otherwise, you continue on $[c,m]$. Repeat the procedure until the interval is sufficiently small.

Answer 2

In the case, the numerical approach suffices, you can formulate the problem as a convex-concave saddle point problem.

First, notice that $\max(t, 0) = \max_{u\in [0,1]} ut$. With this, you can rewrite the problem as

$$ \min_{x\in [c,d]}\max_{y\in [0,1]^N} \langle Bx,y\rangle + \langle a,y\rangle, $$ where $a = (a_1,\dots, a_N)$ and $Bx = (b_1x,\dots, b_Nx)$.

Now you can apply any method suitable for solving saddle point problems (the primal-dual hybrid gradient, ADMM, variational inequalities methods, etc.)

Here is how iterations generated by the primal-dual hybrid gradient will look like: \begin{align*} x^{k+1} & = P_{[c,d]}(x^k - \tau B^Ty^k)\\ y^{k+1} & = P_{[0,1]^N}(y^k + \sigma (B(2x^{k+1}-x^k)+a)), \end{align*} where $x^0\in [c,d]$, $y^0\in [0,1]^N$, and steps $\tau>0$, $\sigma >0$ satisfy $\tau \sigma < \frac{1}{\|B\|_2^2} = \frac{1}{b_1^2+\dots b_N^2}$.

Note that the original problem was non-smooth, hence direct methods (e.g. subgradient ones) would not be efficient.