Optimization Online


A polynomial-time descent method for separable convex optimization problems with linear constraints

Sergei Chubanov (sergei.chubanov***at***uni-siegen.de)

Abstract: 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 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.

Keywords: Convex optimization, polynomial algorithm

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 03/21/2015
Entry Accepted: 03/21/2015
Entry Last Modified: 01/28/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society