Canadian Mathematical Society Société mathématique du Canada Editors-in-chief Rédacteurs-en-chef J.Borwein K.Dilcher Advisory Board Comité consultatif P.Borwein R.Kane S.Shen CMS Books in Mathematics Ouvrages de mathématiques de la SMC 1 HERMAN/KUCˇERA/SˇIMSˇA Equations and Inequalities 2 ARNOLD Abelian Groups and Representations of Finite Partially Ordered Sets 3 BORWEIN/LEWIS Convex Analysis and Nonlinear Optimization 4 LEVIN/LUBINSKY Orthogonal Polynomials for Exponential Weights 5 KANE Reflection Groups and Invariant Theory 6 PHILLIPS Two Millennia of Mathematics 7 DEUTSCH Best Approximation in Inner Product Spaces 8 FABIANETAL. Functional Analysis and Infinite-Dimensional Geometry 9 KRˇÍZˇEK/LUCA/SOMER 17 Lectures on Fermat Numbers 10 BORWEIN Computational Excursions in Analysis and Number Theory 11 REED/SALES (Editors) Recent Advances in Algorithms and Combinatorics 12 HERMAN/KUCˇERA/SˇIMSˇA Counting and Configurations 13 NAZARETH Differentiable Optimization and Equation Solving 14 PHILLIPS Interpolation and Approximation by Polynomials 15 BEN-ISRAEL/GREVILLE Generalized Inverses, Second Edition 16 ZHAO Dynamical Systems in Population Biology 17 GÖPFERTETAL. Variational Methods in Partially Ordered Spaces 18 AKIVIS/GOLDBERG Differential Geometry of Varieties with Degenerate Gauss Maps 19 MIKHALEV/SHPILRAIN/YU Combinatorial Methods 20 BORWEIN/ZHU Techniques of Variational Analysis 21 VANBRUMMELEN/KINYON Mathematics and the Historian’s Craft: The Kenneth O. May Lectures 22 LUCCHETTI Convexity and Well-Posed Problems 23 NICULESCU/PERSSON Convex Functions and Their Applications 24 SINGER Duality for Nonconvex Approximation and Optimization 25 HIGGINSON/PIMM/SINCLAIR Mathematics and the Aesthetic Constantin P.Niculescu Lars-Erik Persson Convex Functions and Their Applications A Contemporary Approach With 8 Illustrations Constantin P. Niculescu Lars-Erik Persson Department of Mathematics Department of Mathematics University of Craiova Luleå University of Technology Craiova 200585 Luleå 97187 Romania Sweden [email protected] [email protected] Editors-in-Chief Rédacteurs-en-chef Jonathan Borwein Karl Dilcher Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 3J5 Canada [email protected] Mathematics Subject Classification (2000): 26Axx, 26Bxx, 26Dxx, 46Axx, 52Axx Library of Congress Control Number: 2005932044 ISBN-10: 0-387-24300-3 ISBN-13: 978-0387-24300-9 Printed on acid-free paper. ©2006 Springer Science+Business Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, Inc., 233 Spring Street, New York, NY10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. (MVY) 9 8 7 6 5 4 3 2 1 springeronline.com To Liliana and Lena Preface It seems to me that the notion of convex function is just as fundamental as positive function or increasing function. If I am not mistaken in this, the notion ought to find its place in elementary expositions of the theory of real functions. J. L. W. V. Jensen Convexity is a simple and natural notion which can be traced back to Archimedes (circa 250 B.C.), in connection with his famous estimate of the value of π (by using inscribed and circumscribed regular polygons). He no- ticed the important fact that the perimeter of a convex figure is smaller than the perimeter of any other convex figure surrounding it. As a matter of fact, we experience convexity all the time and in many ways. The most prosaic example is our upright position, which is secured as long as the vertical projection of our center of gravity lies inside the convex envelope of our feet. Also, convexity has a great impact on our everyday life through numerous applications in industry, business, medicine, and art. So do the problems of optimum allocation of resources and equilibrium of non- cooperative games. The theory of convex functions is part of the general subject of convexity, since a convex function is one whose epigraph is a convex set. Nonetheless it is an important theory per se, which touches almost all branches of math- ematics. Graphical analysis is one of the first topics in mathematics which requires the concept of convexity. Calculus gives us a powerful tool in recog- nizing convexity, the second-derivative test. Miraculously, this has a natural generalization for the several variables case, the Hessian test. Motivated by some deep problems in optimization and control theory, convex function the- oryhasbeenextendedtotheframeworkofinfinitedimensionalBanachspaces (and even further). The recognition of the subject of convex functions as one that deserves to be studied in its own right is generally ascribed to J. L. W. V. Jensen [114], [115]. However he was not the first to deal with such functions. Among his predecessors we should recall here Ch. Hermite [102], O. H¨older [106] and O. Stolz [233]. During the twentieth century, there was intense research ac- tivity and significant results were obtained in geometric functional analysis, mathematicaleconomics,convexanalysis,andnonlinearoptimization.Aclas- VIII Preface sic book by G. H. Hardy, J. E. Littlewood and G. Po´lya [99] played a large role in the popularization of the subject of convex functions. Roughly speaking, there are two basic properties of convex functions that make them so widely used in theoretical and applied mathematics: • The maximum is attained at a boundary point. • Any local minimum is a global one. Moreover, a strictly convex function admits at most one minimum. The modern viewpoint on convex functions entails a powerful and elegant interaction between analysis and geometry. In a memorable paper dedicated to the Brunn–Minkowski inequality, R. J. Gardner [88, p. 358], described this reality in beautiful phrases: [convexity] “appears like an octopus, tentacles reachingfarandwide,itsshapeandcolorchangingasitroamsfromonearea to the next. It is quite clear that research opportunities abound.” Overtheyearsanumberofnotablebooksdedicatedtothetheoryandap- plicationsofconvexfunctionsappeared.Wementionhere:L.Ho¨rmander[108], M.A.Krasnosel’skiiandYa.B.Rutickii[132],J.E.Peˇcari´c,F.Proschanand Y. C. Tong [196], R. R. Phelps [199], [200] and A. W. Roberts and D. E. Var- berg [212]. The references at the end of this book include many other fine books dedicated to one aspect or another of the theory. The title of the book by L. Ho¨rmander, Notions of Convexity, is very suggestive for the present state of art. In fact, nowadays the study of convex functions has evolved into a larger theory about functions which are adapted to other geometries of the domain and/or obey other laws of comparison of means. Examples are log-convex functions, multiplicatively convex functions, subharmonic functions, and functions which are convex with respect to a subgroup of the linear group. Our book aims to be a thorough introduction to contemporary convex function theory. It covers a large variety of subjects, from the one real vari- ablecasetotheinfinitedimensionalcase,includingJensen’sinequalityandits ramifications, the Hardy–Littlewood–Po´lya theory of majorization, the the- ory of gamma and beta functions, the Borell–Brascamp–Lieb form of the Pr´ekopa–Leindler inequality (as well as the connection with isoperimetric in- equalities), Alexandrov’s well-known result on the second differentiability of convex functions, the highlights of Choquet’s theory, a brief account on the recent solution to Horn’s conjecture, and many more. It is certainly a book where inequalities play a central role but in no case a book on inequalities. Many results are new, and the whole book reflects our own experiences, both in teaching and research. This book may serve many purposes, ranging from a one-semester gradu- ate course on Convex Functions and Applications to additional bibliographic material. In a course for first year graduate students, we used the following route: • Background: Sections 1.1–1.3, 1.5, 1.7, 1.8, 1.10. • The beta and gamma functions: Section 2.2. Preface IX • Convex functions of several variables: Sections 3.1–3.12. • The variational approach of partial differential equations: Appendix C. The necessary background is advanced calculus and linear algebra. This can be covered from many sources, for example, from Analysis I and II by S. Lang [137], [138]. A thorough presentation of the fundamentals of measure theory is also available in L. C. Evans and R. F. Gariepy [74]. For further reading we recommend the classical texts by F. H. Clarke [56] and I. Ekeland and R. Temam [70]. Our book is not meant to be read from cover to cover. For example, Sec- tion 1.9, which deals with the Hermite–Hadamard inequality, offers a good startingpointforChoquet’stheory.ThenthereadermaycontinuewithChap- ter 4, where this theory is presented in a slightly more general form, to allow the presence of certain signed measures. We recommend this chapter to be studied in parallel with the Lectures on Choquet’s theory by R. R. Phelps [200]. For the reader’s convenience, we collected in Appendix A all the nec- essary material on the separation of convex sets in locally convex Hausdorff spaces (as well as a proof of the Krein–Milman theorem). AppendixBmaybeseenbothasanillustrationofconvexfunctiontheory and an introduction to an important topic in real algebraic geometry: the theory of semi-algebraic sets. Sections3.11and3.12offerallnecessarybackgroundonafurtherstudyof convexgeometricanalysis,afast-growingtopicwhichrelatesmanyimportant branches of mathematics. To help the reader in understanding the theory presented, each section ends with exercises (accompanied by hints). Also, each chapter ends with comments covering supplementary material and historical information. The primary sourceswehaverelied upon for thisbook arelisted in thereferences. In order to avoid any confusion relative to our notation, a symbol index was added for the convenience of the reader. Notice that our book deals only withreal linearspacesandallBorelmeasuresunderattentionareassumedto be regular. We wish to thank all our colleagues and friends who read and commented onvariousversionsandpartsofthemanuscript:MadalinaDeaconu,Andaluzia Matei,SorinMicu,FlorinPopovici,MirceaPreda,ThomasStro¨mberg,Andrei Vernescu, Peter Wall, Anna Wedestig and Tudor Zamfirescu. We also acknowledge the financial support of Wenner–Gren Foundations (Grant 25 12 2002), which made possible the cooperation of the two authors. In order to keep in touch with our readers, a web page for this book will be made available at http://www.inf.ucv.ro/∼niculescu/Convex Functions.html Craiova and Lule˚a Constantin P. Niculescu September 2004 Lars-Erik Persson Contents Preface ........................................................VII List of symbols ................................................XIII Introduction................................................... 1 1 Convex Functions on Intervals ............................. 7 1.1 Convex Functions at First Glance ......................... 7 1.2 Young’s Inequality and Its Consequences ................... 14 1.3 Smoothness Properties ................................... 20 1.4 An Upper Estimate of Jensen’s Inequality .................. 27 1.5 The Subdifferential ...................................... 29 1.6 Integral Representation of Convex Functions ................ 36 1.7 Conjugate Convex Functions.............................. 40 1.8 The Integral Form of Jensen’s Inequality ................... 44 1.9 The Hermite–Hadamard Inequality ........................ 50 1.10 Convexity and Majorization .............................. 53 1.11 Comments.............................................. 60 2 Comparative Convexity on Intervals ....................... 65 2.1 Algebraic Versions of Convexity ........................... 65 2.2 The Gamma and Beta Functions .......................... 68 2.3 Generalities on Multiplicatively Convex Functions ........... 77 2.4 Multiplicative Convexity of Special Functions ............... 83 2.5 An Estimate of the AM–GM Inequality.................... 85 2.6 (M,N)-Convex Functions ................................ 88 2.7 Relative Convexity ...................................... 91 2.8 Comments.............................................. 97 XII Contents 3 Convex Functions on a Normed Linear Space ..............101 3.1 Convex Sets ............................................101 3.2 The Orthogonal Projection ...............................106 3.3 Hyperplanes and Separation Theorems .....................109 3.4 Convex Functions in Higher Dimensions ....................112 3.5 Continuity of Convex Functions ...........................119 3.6 Positively Homogeneous Functions.........................123 3.7 The Subdifferential ......................................128 3.8 Differentiability of Convex Functions.......................135 3.9 Recognizing Convex Functions ............................141 3.10 The Convex Programming Problem........................145 3.11 Fine Properties of Differentiability.........................152 3.12 Pr´ekopa–Leindler Type Inequalities........................158 3.13 Mazur–Ulam Spaces and Convexity........................165 3.14 Comments..............................................171 4 Choquet’s Theory and Beyond.............................177 4.1 Steffensen–Popoviciu Measures ............................177 4.2 The Jensen–Steffensen Inequality and Majorization ..........184 4.3 Steffensen’s Inequalities ..................................190 4.4 Choquet’s Theorem......................................192 4.5 Comments..............................................199 A Background on Convex Sets ...............................203 A.1 The Hahn–Banach Extension Theorem .....................203 A.2 Separation of Convex Sets ................................207 A.3 The Krein–Milman Theorem..............................210 B Elementary Symmetric Functions..........................213 B.1 Newton’s Inequalities ....................................213 B.2 More Newton Inequalities ................................217 B.3 A Result of H. F. Bohnenblust ............................219 C The Variational Approach of PDE .........................223 C.1 The Minimum of Convex Functionals ......................223 C.2 Preliminaries on Sobolev Spaces...........................226 C.3 Applications to Elliptic Boundary-Value Problems ...........228 C.4 The Galerkin Method ....................................231 D Horn’s Conjecture .........................................233 D.1 Weyl’s Inequalities.......................................234 D.2 The Case n=2 .........................................237 D.3 Majorization Inequalities and the Case n=3 ...............238 References.....................................................241 Index..........................................................253