We consider the problem to minimize the sum of piecewise-linear convex functions under both linear and nonnegative constraints. We convert the piecewise-linear convex problem into a standard form linear programming problem (LP) and apply a primal-dual interior-point method for the LP. From the solution of the converted problem, we can obtain the solution of the original problem. We establish polynomial convergence of the interior-point method for the converted problem and devise the computaion of the Newton direction.
Citation
The Department of Industrial and Management Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan