A Survey of Algorithms for Separable Convex Optimization with Linear Ascending Constraints

The paper considers the minimization of a separable convex function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios, and is a special case of an optimization of a separable convex function over the bases of a polymatroid w...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-08
Main Authors: Akhil, P T, Sundaresan, Rajesh
Format: Article
Language:English
Subjects:
Algorithms
Computational geometry
Convexity
Economic models
Optimization
Resource allocation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The paper considers the minimization of a separable convex function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios, and is a special case of an optimization of a separable convex function over the bases of a polymatroid with a certain structure. The paper presents a survey of state-of-the-art algorithms that solve this optimization problem. The algorithms are applicable to the class of separable convex objective functions that need not be smooth or strictly convex. When the objective function is a so-called \(d\)-separable function, a simpler linear time algorithm solves the problem.
ISSN:2331-8422