Borwein, Lewis - Convex Analysis and Non Linear Optimization Theory and Examples.pdf

(1264 KB) Pobierz
book.dvi
CONVEX ANALYSIS AND NONLINEAR
OPTIMIZATION
Theory and Examples
JONATHAN M. BORWEIN
Centre for Experimental and Constructive Mathematics
Department of Mathematics and Statistics
Simon Fraser University, Burnaby, B.C., Canada V5A 1S6
jborwein@cecm.sfu.ca
http://www.cecm.sfu.ca/ ∼ jborwein
and
ADRIAN S. LEWIS
Department of Combinatorics and Optimization
University of Waterloo, Waterloo, Ont., Canada N2L 3G1
aslewis@orion.uwaterloo.ca
http://orion.uwaterloo.ca/ ∼ aslewis
To our families
2
Contents
0.1 Preface............................... 5
1 Background 7
1.1 Euclideanspaces ......................... 7
1.2 Symmetricmatrices........................ 16
2 Inequality constraints 22
2.1 Optimalityconditions....................... 22
2.2 Theoremsofthealternative ................... 30
2.3 Max-functionsandfirstorderconditions ............ 36
3 Fenchel duality 42
3.1 Subgradients and convex functions ............... 42
3.2 Thevaluefunction ........................ 54
3.3 TheFenchelconjugate ...................... 61
4Convexanaly s 78
4.1 Continuityofconvexfunctions.................. 78
4.2 Fenchelbiconjugation....................... 90
4.3 Lagrangianduality ........................103
5 Special cases 113
5.1 Polyhedralconvexsetsandfunctions ..............113
5.2 Functionsofeigenvalues .....................120
5.3 Dualityforlinearandsemidefiniteprogramming........126
5.4 Convexprocessduality......................132
6 Nonsmooth optimization 143
6.1 Generalizedderivatives......................143
3
6.2 Nonsmooth regularity and strict differentiability . . . .....151
6.3 Tangentcones...........................158
6.4 Thelimitingsubdifferential ...................167
7 The Karush-Kuhn-Tucker theorem 176
7.1 Anintroductiontometricregularity ..............176
7.2 The Karush-Kuhn-Tucker theorem ...............184
7.3 Metricregularityandthelimitingsubdifferential........191
7.4 Secondorderconditions .....................197
8 Fixed points 204
8.1 Brouwer’sfixedpointtheorem..................204
8.2 Selection results and the Kakutani-Fan fixed point theorem . . 216
8.3 Variationalinequalities......................227
9 Postscript: infinite versus finite dimensions 238
9.1 Introduction............................238
9.2 Finitedimensionality.......................240
9.3 Counterexamplesandexercises..................243
9.4 Notesonpreviouschapters....................249
9.4.1 Chapter1:Background..................249
9.4.2 Chapter2:Inequalityconstraints ............249
9.4.3 Chapter3:Fenchelduality................249
9.4.4 Chapter4:Convexanalysis ...............250
9.4.5 Chapter5:Specialcases .................250
9.4.6 Chapter6:Nonsmoothoptimization ..........250
9.4.7 Chapter 7: The Karush-Kuhn-Tucker theorem .....251
9.4.8 Chapter8:Fixedpoints .................251
10 List of results and notation 252
10.1Namedresultsandexercises ...................252
10.2Notation..............................267
Bibliography
276
Index
290
4
0.1 Preface
Optimization is a rich and thriving mathematical discipline. Properties of
minimizers and maximizers of functions rely intimately on a wealth of tech-
niques from mathematical analysis, including tools from calculus and its
generalizations, topological notions, and more geometric ideas. The the-
ory underlying current computational optimization techniques grows ever
more sophisticated – duality-based algorithms, interior point methods, and
control-theoretic applications are typical examples. The powerful and elegant
language of convex analysis unifies much of this theory. Hence our aim of
writing a concise, accessible account of convex analysis and its applications
and extensions, for a broad audience.
For students of optimization and analysis, there is great benefit to blur-
ring the distinction between the two disciplines. Many important analytic
problems have illuminating optimization formulations and hence can be ap-
proached through our main variational tools: subgradients and optimality
conditions, the many guises of duality, metric regularity and so forth. More
generally, the idea of convexity is central to the transition from classical
analysis to various branches of modern analysis: from linear to nonlinear
analysis, from smooth to nonsmooth, and from the study of functions to
multifunctions. Thus although we use certain optimization models repeat-
edly to illustrate the main results (models such as linear and semidefinite
programming duality and cone polarity), we constantly emphasize the power
of abstract models and notation.
Good reference works on finite-dimensional convex analysis already exist.
Rockafellar’s classic Convex Analysis [149] has been indispensable and ubiq-
uitous since the 1970’s, and a more general sequel with Wets, Variational
Analysis [150], appeared recently. Hiriart-Urruty and Lemarechal’s Convex
Analysis and Minimization Algorithms [86] is a comprehensive but gentler
introduction. Our goal is not to supplant these works, but on the contrary
to promote them, and thereby to motivate future researchers. This book
aims to make converts.
We try to be succinct rather than systematic, avoiding becoming bogged
down in technical details. Our style is relatively informal: for example, the
text of each section sets the context for many of the result statements. We
value the variety of independent, self-contained approaches over a single,
unified, sequential development. We hope to showcase a few memorable
principles rather than to develop the theory to its limits. We discuss no
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin