Conditional Subgradient Optimization --- Theory and Applications

Torbjörn Larsson, Michael Patriksson, and Ann-Brith Strömberg 
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 simple modification may improve subgradient
optimization schemes significantly.
This finding is important as such schemes are very popular, especially in the
context of Lagrangean relaxation.

KWY WORDS: Convex Programming, Nonsmooth Optimization, Subgradient
Methods, Conditional Subgradients, Lagrangean Relaxation