2 CONTENTS
2.3.3 Minimization methods for minimax problem . . . . . . . . . . . . . . 89
2.3.4 Optimization with Functional Constraints . . . . . . . . . . . . . . . 92
2.3.5 Constrained minimization process . . . . . . . . . . . . . . . . . . . . 96
3 Nonsmooth Convex Programming 103
3.1 General Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.1.1 Motivation and Definitions . . . . . . . . . . . . . . . . . . . . . . . . 103
3.1.2 Operations with convex functions . . . . . . . . . . . . . . . . . . . . 108
3.1.3 Continuity and Differentiability of Convex Functions . . . . . . . . . 112
3.1.4 Separation Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.1.5 Subgradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.1.6 Computing the subgradients . . . . . . . . . . . . . . . . . . . . . . . 119
3.2 Nonsmooth Minimization Methods . . . . . . . . . . . . . . . . . . . . . . . 124
3.2.1 General Lower Complexity Bounds . . . . . . . . . . . . . . . . . . . 124
3.2.2 Main lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
3.2.3 Subgradient Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.2.4 Minimization with functional constraints . . . . . . . . . . . . . . . . 131
3.2.5 Complexity Bounds in Finite Dimension . . . . . . . . . . . . . . . . 133
3.2.6 Cutting Plane Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.3 Methods with Complete Data . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3.3.1 Model of nonsmooth function . . . . . . . . . . . . . . . . . . . . . . 144
3.3.2 Kelly method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.3.3 Level Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.3.4 Constrained Minimization . . . . . . . . . . . . . . . . . . . . . . . . 151
4 Structural Programming 157
4.1 Self-Concordant Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.1.1 Black box concept in Convex Programming . . . . . . . . . . . . . . 157
4.1.2 What the Newton method actually does? . . . . . . . . . . . . . . . . 159
4.1.3 Definition of self-concordant function . . . . . . . . . . . . . . . . . . 160
4.1.4 Main inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.1.5 Minimizing the self-concordant function . . . . . . . . . . . . . . . . 169
4.2 Self-Concordant Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.2.2 Definition of self-concordant barriers . . . . . . . . . . . . . . . . . . 175
4.2.3 Main Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.2.4 Path-following Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 180
4.2.5 Finding the analytic center . . . . . . . . . . . . . . . . . . . . . . . . 183
4.2.6 Problems with functional constraints . . . . . . . . . . . . . . . . . . 186
4.3 Applications of Structural Programming . . . . . . . . . . . . . . . . . . . . 189
4.3.1 Bounds on the parameter of a self-concordant barrier . . . . . . . . . 189
4.3.2 Linear and Quadratic Programming . . . . . . . . . . . . . . . . . . . 192
4.3.3 Semidefinite Programming . . . . . . . . . . . . . . . . . . . . . . . . 194
评论0