Name
Abstract | ||
|---|---|---|
We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function
whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there
exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number
of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the
simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special
case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves
the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational
study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a
polynomial of low order in the number of decision variables. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s11590-007-0073-2 | Optimization Letters |
Keywords | Field | DocType |
convex optimization · simplex method · nonlinear programming,nonlinear programming,convex function,convex optimization,simplex method,convex programming,objective function,linear program | Mathematical optimization,Mathematical analysis,Convex combination,Nonlinear programming,Convex set,Algorithm,Convex polytope,Linear programming,Proper convex function,Convex optimization,Mathematics,Convex analysis | Journal |
Volume | Issue | ISSN |
2 | 4 | 1862-4472 |
Citations | PageRank | References |
1 | 0.36 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas C. Sharkey | 1 | 101 | 11.80 |
| H. Edwin Romeijn | 2 | 769 | 83.88 |