Conditional subgradient optimization — Theory and applications |
| |
Authors: | Torbjö rn Larsson,Michael PatrikssonAnn-Brith Strö mberg |
| |
Affiliation: | Department of Mathematics, Linköping Institute of Technology, S-581 83 Linköping, Sweden |
| |
Abstract: | We generalize the subgradient optimization method for nondifferentiable convex programming to utilize conditional subgradients. Firstly, we derive the new method and establish its convergence by generalizing convergence results for traditional subgradient optimization. Secondly, we consider a particular choice of conditional subgradients, obtained by projections, which leads to an easily implementable modification of traditional subgradient optimization schemes. To evaluate the subgradient projection method we consider its use in three applications: uncapacitated facility location, two-person zero-sum matrix games, and multicommodity network flows. Computational experiments show that the subgradient projection method performs better than traditional subgradient optimization; in some cases the difference is considerable. These results suggest that our simply modification may improve subgradient optimization schemes significantly. This finding is important as such schemes are very popular, especially in the context of Lagrangean relaxation. |
| |
Keywords: | Convex programming Nonsmooth optimization Subgradient methods Conditional subgradients Lagrangean relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|