Introduction to Nonlinear Optimization – Theory, Algorithms, and Applications With Matlab
Amir Beck
Contents
Preface Xl.
1 Mathematical Preliminaries 1
1.1 The Space Rn 1
1.2 The Space Rmxn 2
1.3 Inner Products and Norms . 2
1.4 Eigenvalues and Eigenvectors 5
1.5 Basic Topological Concepts . 6
Exercises 10
2 Optimality Conditions for Unconstrained Optimization 13
2.1 Global and Local Optima 13
2.2 Classification of Matrices 17
2.3 Second Order Optimality Conditions 23
2.4 Global Optimality Conditions . 30
2.5 Quadratic Functions . 32
Exercises 34
3 Least Squares 37
3.1 “Solution” of Overdetermined Systems . 37
3.2 Data Fitting . 39
3.3 Regularized Least Squares 41
3.4 Deno1smg 42
3.5 Nonlinear Least Squares . 45
3.6 Circle Fitting 45
Exercises 47
4 The Gradient Method 49
4.1 Descent Directions Methods 49
4.2 The Gradient Method 52
4.3 The Condition Number . 58
4.4 Diagonal Scaling 63
4.5 The Gauss-Newton Method 67
4.6 The Fermat-Weber Problem 68
4.7 Convergence Analysis of the Gradient Method 73
Exercises 79
5 Newton’s Method 83
5.1 Pure Newton’s Method 83
viiviii Contents
5.2 Damped Newton’s Method .
5.3 The Cholesky Factorization
Exercises .
6 Convex Sets 97
6.1 Definition and Examples . 97
6.2 Algebraic Operations with Convex Sets . 100
6.3 The Convex Hull . 101
6.4 Convex Cones . 104
6.5 Topological Properties of Convex Sets 108
6.6 Extreme Points . 111
Exercises 113
7 Convex Functions 117
7.1 Definition and Examples . 117
7.2 First Order Characterizations of Convex Functions . 119
7.3 Second Order Characterization of Convex Functions 123
7.4 Operations Preserving Convexity . 125
7.5 Level Sets of Convex Functions 130
7.6 Continuity and Differentiability of Convex Functions . 132
7.7 Extended Real-Valued Functions 135
7.8 Maxima of Convex Functions . 137
7.9 Convexity and Inequalities . 139
Exercises 141
8 Convex Optimization 147
8.1 Definition 147
8.2 Examples . 149
8.3 The Orthogonal Projection Operator 156
8.4 cvx 158
Exercises 166
9 Optimization over a Convex Set 169
9.1 Stationarity . 169
9.2 Stationarity in Convex Problems . 173
9.3 The Orthogonal Projection Revisited 173
9.4 The Gradient Projection Method . 175
9.5 Sparsity Constrained Problems 183
Exercises 189
10 Optimality Conditions for Linearly Constrained Problems 191
10.1 Separation and Alternative Theorems 191
10.2 The KKT conditions . 195
10.3 Orthogonal Regression 203
Exercises 205
11 The KK.T Conditions 207
11.1 Inequality Constrained Problems . 207
11.2 Inequality and Equality Constrained Problems 210
11.3 The Convex Case . 213
11.4 Constrained Least Squares 218Contents ix
11.5 Second Order Optimality Conditions 222
11.6 Optimality Conditions for the Trust Region Subproblem . 227
11.7 Total Least Squares 230
Exercises 233
12 Duality 237
12.1 Motivation and Definition 237
12.2 Strong Duality in the Convex Case 241
12.3 Examples . 247
Exercises 270
Bibliographic Notes
Bibliography
Index
Index
constraint qualification, 210
continuously differentiable, 9
contour set, 7
convex combination, 101
convex function, 117
convex hull, 102
convex optimization, 147
convex polytope, 100
convex problem, 147
convex set, 97
cvx, 158
damped Gauss-Newton method,
67,68
damped Newton’s method, 88
data fitting, 39
denoising, 42
descent direction, 49
descent directions method, 50
descentlemma,74
descent method, 50
diagonally dominant matrix, 22
directional derivative, 8
distance function, 130, 157
dot product, 2
dual cone, 114,205
dual objective function, 238
dual problem, 237
effective domain, 135
eigenvalue, 5
eigenvector, 5
ellipsoid, 99
epigraph, 136
Euclidean norm, 3
exact line search, 51
extended real-valued function,
135
extreme point, 111
facility location, 69
Farkas lemma, 192
281
feasible descent direction, 207
feasible set, 13
feasible solution, 13
Fejer monotonicity, 183
Fermat’s theorem, 16
Fermat-Weber problem, 68, 80
finite-valued, 135
first projection theorem, 157
Fritz-John conditions, 208
Frobenius norm, 4
full column rank, 37
function
distance, 130, 157
dual objective, 238
Huber, 189
quadratic, 32
Rosenbrock, 60
generalized Slater’s condition,
216
geometric programming, 267
global maximum and minimum,
13
global optimum, 13
Gordan’s theorem, 194, 205, 208
gradient, 9
gradient inequality, 119
gradient mapping, 177
gradient method, 52
gradient projection method, 175
Hessian, 10
hidden convexity, 155, 165
Holder’s inequality, 140
Huber function, 189
hyperplane, 98
identity matrix, 2
ill-conditioned matrices, 60
indefinite matrix, 18
indicator function, 135
induced matrix norm, 4282
inequality
Jensen’s, 118
Kantorovich, 59
linear matrix, 254
Minkowski’s, 140
strongly convex, 117
inner product, 2
interior, 7
interior point, 7
iterative hard-thresholding, 187
Jacobian, 67
Jensen’s inequality, 118
Kantorovich inequality, 59
KK.T conditions, 195, 207
KK.T point, 198, 211
Krein-Milman theorem, 113
Lagrange multipliers, 196
Lagrangian function, 198
least squares, 37
linear, 45
regularized, 41, 219, 262
total, 230
level set, 7, 130
line, 97
line search, 50
line segment principle, 108
linear approximation theorem, 10
linear fitting, 39
linear function, 118
linear least squares, 45
linear matrix inequality, 254
lin~ar programming, 107, 149,
247
linear rate, 60
Lipschitz continuity of the
gradient, 73
local maximum point, 15
local minimum point, 15
log-sum-exp, 124
Lorenz cone, 105
matrix norm, 3
maximal value, 13
maximizer, 13
minimial value, 13
minimizer, 13
Minkowski functional, 113
Minkowski’s inequality, 140
monomial, 267
Motzkin’s theorem, 205
negative definite, 18
negative semidefinite, 18
neighborhood, 7
Newton direction, 83
Newton’s method, 64, 83
damped,88
pure, 83
nonexpansive, 174
nonlinear Farkas lemma, 242
nonlinear fitting, 40
nonlinear least squares, 45, 67
nonnegative orthant, 1
nonnegative part, 157
norm
diagonally dominant, 22
identity, 2
indefinite, 18
induced matrix, 4
square root of, 21
strictly diagonally
dominant, 22
normal cone, 114
normal system, 37
open ball, 6
open line segment, 2
open set, 7
optimal set, 148
orthogonal projection, 156
orthogonal regression, 203
overdetermined system, 37
partial derivative, 8
pointed cone, 114
positive definite, 17
positive orthant, 2
positive semidefinite, 17
posynomial, 267
primal problem, 238
principal minors criterion, 21
proper, 135
pure Newton’s method, 83
Q-norm, 35
QCQP, 155, 235
quadratic approximation
theorem, 10
quadratic function, 32
quadratic problem, 150
quadratic-over-linear, 125, 127
quasi-convex function, 131
Rayleigh quotient, 5, 205,
232
regularity, 211
regularization parameter, 41
regularized least squares, 41, 219,
262
robust regression, 163
Rosenbrock function, 60
saddle point, 24
Index
scaled gradient method, 63
second projection theorem, 173
semidefinite programming, 254
separation of two convex sets, 242
separation theorem, 191
set
bounded,8
open,7
sgn, 156
singleton, 187
Slater’s condition, 214
source localization problem, 80
sparsity constrained problems,
183
spectral decomposition, 5
spectral norm, 4
square root of a matrix, 21
standard basis, 1
stationary point, 17, 169
strict global maximum, 13
strict global minimum, 13
strict local maximum, 15
strict local minimum, 15
strict separation theorem, 191
strictly concave function, 118
strictly convex function, 117
strictly diagonally dominant
matrix, 22
strong convexity parameter, 144
strong duality, 241
strongly convex function, 144,
190
sublinear rate, 182
sufficient decrease lemma, 75, 176
support, 184
support function, 136
supporting hyperplane theorem,
241
total least squares, 230
trust region subproblem, 155, 227
unit-simplex, 2, 254
unit-sum set, 171
Vandermonde, 40
weak duality theorem, 239
Weierstrass theorem, 25
well-conditioned matrices, 60
Young’s inequality, 140
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net
تحميل
يجب عليك التسجيل في الموقع لكي تتمكن من التحميل
تسجيل | تسجيل الدخول