Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I have this problem:
\begin{align} \min_{\mathbf{w}} & \sum_{i=1}^N c_i P_i(w_i)\\ s.t & \notag\\ & \sum_{i =1 }^N w_i = w \\ & 0 \leq w_i \leq w_{max},~~\forall i \in 1, ..., N \end{align}
where $P_i(w)$ is a piecewise linear convex function. Is there a closed formula to solve this? If not, what is the most relevant algorithm?
If $P_i(w)$ is a piecewise linear, convex function, then it can be written as the maximum of a number of linear functions, $P_i(w)=\max \{L_{i1}(w),\ldots,L_{iJ_i}(w)\}$. Then, the optimization problem allows for the reformulation $$ \min_{\mathbf w,\mathbf x} \sum_{i=1}^N c_ix_i = \mathbf c^T \mathbf x, \\ \sum_{i=1}^N w_i = w \\ 0\le w_i \le w_{max}, \qquad i=1,\ldots,N \\ x_i \ge L_{ij}(w) \qquad j=1,\ldots,J_i. $$ This is a linear program with linear constraints that can be solved using, for example, the simplex algorithm. There is, in general, no closed-form solution, however.
