On the Convergence of Conditional Epsilon-Subgradient Methods for
Convex Programs and Convex--Concave Saddle-Point Problems 

Torbjörn Larsson, Michael Patriksson, and Ann-Brith Strömberg 
Division of Optimization
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

ABSTRACT:

The paper provides two contributions.  First, we present new
convergence results for conditional epsilon-subgradient algorithms for
general convex programs.  The results obtained here extend the
classical ones by Polyak \cite{Pol67,Pol69,Pol87} as well as the
recent ones in \cite{CoL93,LPS96,AIS98} to a broader framework.
Secondly, we establish the application of this technique to solve
nonstrictly convex--concave saddle point problems, such as primal-dual
formulations of linear programs.  Contrary to several previous
solution algorithms for such problems, a saddle-point is generated by
a very simple scheme in which one component is constructed by means of
a conditional $\varepsilon$-subgradient algorithm, while the other is
constructed by means of a weighted average of the (inexact) subproblem
solutions generated within the subgradient method.  The convergence
result extends those of \cite{Sho85,ShC96,LPS99} for Lagrangian
saddle-point problems in linear and convex programming, and of
\cite{PeP97} for a linear--quadratic saddle-point problem arising in
topology optimization in contact mechanics.