Society for Industrial and Applied Mathematics, 1974, -85 pp.
Several books have recently been published describing applications of the theory of conjugate convex functions to duality in problems of optimization. The finite-dimensional case has been treated by Stoer and Witzgall [25] and Rockafellar [13] and the infinite-dimensional case by Ekeland and Temam [3] and Laurent [9]. However, these are long works conceed also with many other issues.
The purpose of these lecture notes is to provide a relatively brief introduction to conjugate duality in both finite- and infinite-dimensional problems. The material is essentially to be regarded as a supplement to the book Convex Analysis [13]; the same approach and results are presented, but in a broader formulation and more selectively. However, the order of presentation differs from [13]. I have emphasized more from the very beginning the fundamental importance of the concepts of Lagrangian function, saddle-point and saddle-value. Instead of first outlining everything relevant about conjugate convex functions and then deriving its consequences for optimization, I have tried to introduce areas of basic theory only as they became needed and their significance for the study of dual problems more apparent. In particular, general results on the calculation of conjugate functions have been postponed nearly to the end, making it possible to deduce more complete versions of the formulas by means of the duality theory itself. I have also attempted to show just where it is that convexity is needed, and what remains true if certain convexity or lower-semicontinuity assumptions are dropped.
The notation and terminology of [13] have been changed somewhat to make an easier introduction to the subject. Thus the concepts of "bifunction" and "convex process" have been omitted, even though they are needed in the larger picture to see how the results on optimization problems fit in with other aspects of duality that have long been a mainstay in mathematical analysis. The duality theorem for linear programming problems, for instance, tus out to be an analogue of an algebraic identity relating a linear transformation and its adjoint. For more on this point of view and its possible fertility for applications such as to mathematical economics, see [24].
A number of general examples drawn from nonlinear (including nonconvex) programming, approximation, stochastic programming, the calculus of variations and optimal control, are discussed in tandem with the theory. These examples are obviously not meant to cover in a representative manner all the possible areas of application of conjugate duality, but rather to illustrate and motivate the main lines of thought. They underline especially the fact that, as soon as one admits stochastic or dynamic elements into a model, one is likely to arrive at a problem in infinite dimensions. Moreover, such problems typically involve so- called integral functionals (even in "discrete" models, since an infinite series can be viewed as an integral over a discrete space of indices). For this reason, I have devoted some of the theoretical discussion specifically to convex integral functionals and their special properties.
The role of convexity and duality.
Examples of convex optimization problems.
Conjugate convex functions in paired spaces.
Dual problems and Lagrangians.
Examples of duality schemes.
Continuity and derivatives of convex functions.
Solutions to optimization problems.
Some applications.
Calculating conjugates and subgradients; integral functionals.
More applications.
Several books have recently been published describing applications of the theory of conjugate convex functions to duality in problems of optimization. The finite-dimensional case has been treated by Stoer and Witzgall [25] and Rockafellar [13] and the infinite-dimensional case by Ekeland and Temam [3] and Laurent [9]. However, these are long works conceed also with many other issues.
The purpose of these lecture notes is to provide a relatively brief introduction to conjugate duality in both finite- and infinite-dimensional problems. The material is essentially to be regarded as a supplement to the book Convex Analysis [13]; the same approach and results are presented, but in a broader formulation and more selectively. However, the order of presentation differs from [13]. I have emphasized more from the very beginning the fundamental importance of the concepts of Lagrangian function, saddle-point and saddle-value. Instead of first outlining everything relevant about conjugate convex functions and then deriving its consequences for optimization, I have tried to introduce areas of basic theory only as they became needed and their significance for the study of dual problems more apparent. In particular, general results on the calculation of conjugate functions have been postponed nearly to the end, making it possible to deduce more complete versions of the formulas by means of the duality theory itself. I have also attempted to show just where it is that convexity is needed, and what remains true if certain convexity or lower-semicontinuity assumptions are dropped.
The notation and terminology of [13] have been changed somewhat to make an easier introduction to the subject. Thus the concepts of "bifunction" and "convex process" have been omitted, even though they are needed in the larger picture to see how the results on optimization problems fit in with other aspects of duality that have long been a mainstay in mathematical analysis. The duality theorem for linear programming problems, for instance, tus out to be an analogue of an algebraic identity relating a linear transformation and its adjoint. For more on this point of view and its possible fertility for applications such as to mathematical economics, see [24].
A number of general examples drawn from nonlinear (including nonconvex) programming, approximation, stochastic programming, the calculus of variations and optimal control, are discussed in tandem with the theory. These examples are obviously not meant to cover in a representative manner all the possible areas of application of conjugate duality, but rather to illustrate and motivate the main lines of thought. They underline especially the fact that, as soon as one admits stochastic or dynamic elements into a model, one is likely to arrive at a problem in infinite dimensions. Moreover, such problems typically involve so- called integral functionals (even in "discrete" models, since an infinite series can be viewed as an integral over a discrete space of indices). For this reason, I have devoted some of the theoretical discussion specifically to convex integral functionals and their special properties.
The role of convexity and duality.
Examples of convex optimization problems.
Conjugate convex functions in paired spaces.
Dual problems and Lagrangians.
Examples of duality schemes.
Continuity and derivatives of convex functions.
Solutions to optimization problems.
Some applications.
Calculating conjugates and subgradients; integral functionals.
More applications.