Solving a nonlinear optimisation problem

Question

I have the following nonlinear optimisation problem arising in my model.

$$\min \sum_{k=0}^{N-1} (\tau-t_k)^+\quad \text{ s.t. } {\mathbf{x}^\top\mathbf{w}\le W,\ \mathbf{x}\ge0}, t_k=t_{k-1}+x_k \text{ and } t_0=0.$$

I tried to simplify this problem by setting $\lambda_k=(\tau-t_k)^+$. I get the condition that $\rho w_i=\frac{N-i}{K_i}+\mu_i $, for all $i$, where $\rho$ and $\mu_i$ are appropriate Lagrange multipliers. How do I use this to find the optimal solution?

Answer 1

Your problem is a linear problem: introducing auxiliary variables $z_k$ for $k=0,\ldots,,N-1$, you obtain

$$ \begin{align} &\min \sum_{k=0}^{N-1}z_k \\ &t_0 = 0\\ &t_{k} = t_{k-1} + x_k, \quad k=0,\ldots,N-1\\ &w^T x \leq W \\ &z_k\geq 0, \quad k=0,\ldots,N-1\\ &z_k\geq \tau - t_k, \quad k=0,\ldots,N-1\\ &x\geq 0 \end{align} $$

Any LP solver will do.