Variational Principles

The term ‘variational principle’, which was formerly attached to laws of nature asserting that some quantity is minimized, is now used to describe any procedure in which a property of interest is shown to imply that some quantity is minimized. Variational principles, taken to mean ‘some function is minimized’, make sense even if the function is not differentiable, and the part they play in nonsmooth analysis is not then all that surprising. This chapter brings together a number of variational principles that feature prominently in nonsmooth analysis and its applications. It also introduces a regularization procedure ‘quadratic inf convolution’ that is frequently used hand-in-hand with variational principles to reproduce, in a nonsmooth setting, formerly known properties of smooth functions. The first variational principle is the exact penalization theorem. It tells us that if a point minimizes a Lipschitz function over a closed set, then the point remains a minimizer of an unconstrained problem, in which the constraint is accommodated by nonsmooth penalty function (the distance function to the set scaled by the Lipschitz constant of the objective function). A lower semi-continuous function with domain a topological space may fail to have a minimizer if the domain is not compact. It is however possible to assure existence of a minimizer if we add to the function a suitable perturbation term. The remaining variational principles provide different procedures for constructing a perturbation term to ensure this property. The oldest of these, Ekeland’s theorem, features a nonsmooth perturbation. It not only ensures existence of a minimizer, but locates that minimizer near an approximate minimizer for the original problem and tells us we can control the size of the perturbation according to the accuracy of the approximation. For some problems the presence of a nonsmooth perturbed term (obtained after applying a variational principle) can be inconvenient. The Borwein/Preiss theorem can be regarded as a variant of Ekeland’s theorem, in which restrictions are placed on the class of functions to which it applies, but the perturbation term is smooth. Stegall’s theorem gives conditions under which we choose a linear perturbation term, but gives no information about the location of the minimizer for the perturbed problem. The chapter ends with a section on mini-max theory. This area is of interest in its own right, in large part, because of its relevance to game theory. But it is included in this chapter because it also has important applications to optimization, for example in the derivation of Lagrange multiplier rules for constrained optimization problems, where the Lagrange multipliers are interpreted as secondary player in some two player game.