Linear Optimization under piecewise linear constraints

Question

I have the following optimization problem.

For given $r \in \mathbb{R}$, $y \in \mathbb{R}^{n \times K}$, $p \in [0,1]^K$ and $b>0$ and writing $c_{i} = \sum_{k=1}^{K}p_{k}y_{ik}$ :

$$\max_{(x,\alpha) \in \mathbb{R}^{n} \times \mathbb{R}} \; \sum_{i=1}^{n}x_{i}c_{i}$$

under the constraints

1. $x \ge 0$
2. $\sum_{i=1}^{n}x_{i}=1$
3. $\alpha + b \cdot \sum_{k=1}^{K}p_{k} \cdot \max(-\sum_{i=1}^{n}x_{i}y_{ik}-\alpha,0\big) \le r$

Due to the third constraint, this is only piecewise linear in $(x,\alpha)$ and not differentiable. However, I need an efficient algorithm to solve this this for large integer values of $n,K$. What is a good approach?

Answer 1

You can add an auxiliary variable $z$: $$\max_{(x,z,\alpha) \in \mathbb{R}^{n} \times \mathbb{R}^K_+ \times \mathbb{R}} \; \sum_{i=1}^{n}x_{i}c_{i}$$

under the constraints

1. $x \ge 0$
2. $\sum_{i=1}^{n}x_{i}=1$
3. $\alpha + b \cdot \sum_{k=1}^{K}p_{k} \cdot z_k \le r$
4. $z_k \geq -\sum_{i=1}^{n}x_{i}y_{ik}-\alpha$