Convex Analysis and Minimization Algorithms I_ Fundamentals [Hiriart-Urruty & Lemaréchal 2011-05-26].pdf

(20153 KB) Pobierz
Grundlehren der
mathematischen Wissenschaften 305
A Series of Comprehensive Studies in Mathematics
Editors
M. Artin
s.
S. Chern J. Coates
1.
M. Frohlich
H. Hironaka
F.
Hirzebruch
L.
Hormander
C.
C.
Moore J.
K.
Moser M. Nagata
W.
Schmidt
D.S. Scott Ya.G. Sinai J. Tits M.Waldschmidt
S.Watanabe
Managing Editors
M. Berger
B.
Eckmann S.
R.
S. Varadhan
Jean-Baptiste Hiriart-Urruty
Claude Lemarechal
Convex Analysis
and Minimization
Algorithms I
Fundamentals
With 113 Figures
Springer-Verlag Berlin Heidelberg GmbH
Jean-Baptiste Hiriart-Urruty
Departement de Mathematiques
Universite Paul Sabatier
118, route de Narbonne
F-31062 Toulouse, France
Claude Lemarechal
INRIA, Rocquencourt
Domaine de Voluceau
B.P.105
F-78153
Le
Chesnay, France
Second Corrected Printing 1996
Llbrarv of Congress CatalogIng-In-PublIcatIon Data
Hlriart-Urruty. Jean-Baptiste. 1949-
Convex analysis and minimlzation algorithms
I
Jean-Baptiste
Hirlart-Urruty, Claude Lernarachal.
p.
cm. -- (Grundlehren der .athematlschen Wissenschaften
305-306)
"Second corrected prlnting"--T.p. verso.
Includes bibliographical references (p.
) and index.
Contents, 1. Fundamentals -- 2. Advanced theory and bundle
methods.
1. Convex functions. 2. Convex sets.
1944-
II. Title. III. Serles.
OA331.5.H57 1993b
515'.8--dc20
I. Lemarechal, Claude,
96-31946
CIP
Mathematics Subject Classification (1991):
26-01, 26B05, 52A41, 26A, 49K, 49M, 49-01, 93B60, 90C
ISSN 0072-7830
ISBN 978-3-642-08161-3
ISBN 978-3-662-02796-7 (eBook)
DOl 10.1007/978-3-662-02796-7
This work is subject to copyright. All rights are reserved, whether the whole or part
of the material is concerned, specifically the rights of translation, reprinting, reuse of
illustrations, recitation, broadcasting, reproduction on microfilm or in any other way,
and storage in data banks. Duplication of this publication or parts thereof is permitted
only under the provisions of the German Copyright Law of September 9, 1965, in its
current version, and permission for use must always
be
obtained from Springer-
Verlag. Violations are liable for prosecution under the German Copyright Law.
© Springer-Verlag Berlin Heidelberg 1993
Originally published by Springer-Verlag Berlin Heidelberg New York in 1993.
Softcover reprint of the hardcover 2nd edition 1993
Typesetting: Editing and reformatting of the authors' input files using a Springer TEX
macro package
4113111-5432 Printed on acid-free paper
SPIN: 11326120
Table of Contents Part I
Introduction . . . . . . . . . . . . . . . . .
I.
Convex Functions of One Real Variable
Basic Definitions and Examples . . .
1.1 First Definitions of a Convex Function
1.2 Inequalities with More Than Two Points
1.3 Modem Definition of Convexity . . .
First Properties . . . . . . . . . . . . . .
2.1 Stability Under Functional Operations
2.2 Limits of Convex Functions .
2.3 Behaviour at Infinity .. . . . . . . .
Continuity Properties . . . . . . . . . . .
3.1 Continuity on the Interior of the Domain
3.2 Lower Semi-Continuity: Closed Convex Functions
3.3 Properties of Closed Convex Functions . . . . .
First-Order Differentiation . . . . . . . . . . . . .
4.1 One-Sided Differentiability of Convex Functions
4.2 Basic Properties of Subderivatives
4.3 Calculus Rules . . . . . . . . . . . . . . .
Second-Order Differentiation . . . . . . . . . .
5.1 The Second Derivative of a Convex Function
5.2 One-Sided Second Derivatives . . . . . . .
5.3 How to Recognize a Convex Function. . . .
First Steps into the Theory of Conjugate Functions
6.1 Basic Properties of the Conjugate.
6.2 Differentiation of the Conjugate.
6.3 Calculus Rules with Conjugacy . .
xv
1
2
6
8
9
9
11
14
16
16
17
19
20
21
24
27
29
30
32
33
36
38
2
3
4
5
6
40
43
II.
Introduction to Optimization Algorithms
1 Generalities . . . . . . . . . . . . . .
1.1 The Problem . . . . . . . . . . .
1.2 General Structure of Optimization Schemes
1.3 General Structure of Optimization Algorithms
2 Defining the Direction. . . . . . . . . . . . . . .
47
47
47
50
52
54
VI
Table of Contents Part I
2.1 Descent and Steepest-Descent Directions .
2.2 First-Order Methods . . . . .
- One Coordinate at a Time . .
- Euclidean Steepest Descent .
- General Normings. . . . .
2.3 Newtonian Methods . . . . . .
2.4 Conjugate-Gradient Methods .
- Linear Conjugate-Gradient Method .
- Nonlinear Extensions . . . . . .
3 Line-Searches . . . . . . . . . . . . .
3.1 General Structure of a Line-Search
3.2 Designing the Test (0),
(R),
(L)
3.3 The Wolfe Line-Search ..
3.4 Updating the Trial Stepsize
III. Convex Sets . . . . . . . . . . .
1 Generalities . . . . . . . . . .
1.1 Definition and First Examples .
1.2 Convexity-Preserving Operations on Sets.
1.3 Convex Combinations and Convex Hulls
1.4 Closed Convex Sets and Hulls ..
2 Convex Sets Attached to a Convex Set
2.1 The Relative Interior .
2.2 The Asymptotic Cone .
2.3 Extreme Points . . . .
2.4 Exposed Faces . . . .
3 Projection onto Closed Convex Sets .
3.1 The Projection Operator . . . . .
3.2 Projection onto a Closed Convex Cone
4 Separation and Applications. . . . . . . .
4.1 Separation Between Convex Sets . . .
4.2 First Consequences of the Separation Properties
- Existence of Supporting Hyperplanes . . .
- Outer Description of Closed Convex Sets .
- Proof of Minkowski's Theorem .
- Bipolar of a Convex Cone . . . . .
4.3 The Lemma ofMinkowski-Farkas .
5 Conical Approximations of Convex Sets
5.1 Convenient Definitions of Tangent Cones .
5.2 The Tangent and Normal Cones to a Convex Set
5.3 Some Properties of Tangent and Normal Cones.
54
56
56
58
58
61
65
66
68
70
71
74
77
81
87
87
87
90
94
99
102
102
108
110
113
116
116
118
121
121
124
124
126
128
128
129
132
133
136
139

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin