On the entropic regularization method for solving min-max problems with applications

Consider a min-max problem in the form of min<Subscript> xεX </Subscript>max<Subscript>1≤i≤m </Subscript>{f <Subscript> i </Subscript>(x)}. It is well-known that the non-differentiability of the max functionF(x) ≡ max<Subscript>1≤i≤m </Subscript>{f <Subscript> i </Subscript>(x)} presents difficulty in finding an optimal solution. An entropic regularization procedure provides a smooth approximationF <Subscript>p</Subscript>(x) that uniformly converges toF(x) overX with a difference bounded by ln(m)/p, forp > 0. In this way, withp being sufficiently large, minimizing the smooth functionF <Subscript>p</Subscript>(x) overX provides a very accurate solution to the min-max problem. The same procedure can be applied to solve systems of inequalities, linear programming problems, and constrained min-max problems. Copyright Physica-Verlag 1997