A Dual and Interior Point Approach to Solve Convex Min-Max Problems

Jos F. Sturm and Shuzhong Zhang

In this paper we propose an interior point method for solving the dual form of min-max type problems. The dual variables are updated by means of a scaling supergradient method. The boundary of the dual feasible region is avoided by the use of a logarithmic barrier function. A major difference with other interior point methods is the nonsmoothness of the objective function. As a consequence, we no longer require smoothness conditions on the original problem. Convergence of the proposed method is established.

Contact: sturm@opres.few.eur.nl, zhang@opres.few.eur.nl