A POLYNOMIAL-TIME DESCENT METHOD FOR SEPARABLE CONVEX OPTIMIZATION PROBLEMS WITH LINEAR CONSTRAINTS

摘要

We propose a polynomial algorithm for a separable convex optimization problem with linear constraints. We do not make any additional assumptions about the structure of the objective function except for polynomial computability. That is, the objective function can be non-differentiable. The running time of our algorithm is polynomial in the size of the input consisting of an instance of the problem and the accuracy with which the problem is to be solved. Our algorithm uses an oracle for solving auxiliary systems of linear inequalities. This oracle can be any polynomial algorithm for linear programming.