2
$\begingroup$

I am wondering if there is a well-known transformation allowing one to solve convex optimization problems of the form

$$\begin{array}{ll} \underset{x}{\text{maximize}} & r^T x\\ \text{subject to} & \mathbf{1}^T x + \displaystyle\sum_i f_i\left(x_i\right) \leq 0\end{array}$$

where the penalty consists of convex losses

$$f_i\left(x\right) := c_i \max\left(x, 0\right)$$

Many thanks for pointers!

$\endgroup$
5
$\begingroup$

Because you say the losses are convex, I will presume that all $c_i \ge 0$, which means that max is used in a convex fashion. Given that, this problem can be formulated as a Linear Programming problem (LP).

Define additional optimization variables, $y_i$. Replace $f_i(x_i)$ with $c_iy_i$, and add the constraints $y_i \ge x_i, y_i \ge 0$. The result is an LP.

$$\max_{x,y}\quad r^Tx\\\text{subject to }\mathbf{1}^T x + \sum_i c_iy_i \leq 0$$ $$y\ge x$$ $$y \ge 0$$ where the latter two inequalities are interpreted as applying to each element of the vector.

Many optimization modeling tools, and even Linear Programming solvers, allow entry of max, and will do this transformation for you. When max is used in a non-convex fashion, these systems would create a Mixed-Integer Linear Programming problem (MILP).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.