Admin
مدير المنتدى
عدد المساهمات : 18726
التقييم : 34712
تاريخ التسجيل : 01/07/2009
الدولة : مصر
العمل : مدير منتدى هندسة الإنتاج والتصميم الميكانيكى
 |  موضوع: كتاب Linear Programming With MATLAB الجمعة 10 مارس 2023, 11:50 pm | |
| 
أخواني في الله
أحضرت لكم كتاب
Linear Programming With MATLAB
Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright
University of Wisconsin – Madison
Madison, Wisconsin
و المحتوى كما يلي :
Contents
Preface xi
1 Introduction 1
1.1 An Example: The Professor’s Dairy . 2
1.1.1 The Setup . 2
1.1.2 Formulating the Problem and a Graphical Solution 2
1.1.3 Changing the Problem . 4
1.1.4 Discussion . 6
1.2 Formulations . 7
1.3 Applications . 8
1.3.1 The Diet Problem . 8
1.3.2 Linear Surface Fitting . 9
1.3.3 Load Balancing Problem 10
1.3.4 Resource Allocation 10
1.3.5 Classification 11
1.3.6 Minimum-Cost Network Flow . 12
1.4 Algorithms and Complexity . 14
1.4.1 The Simplex Method 14
1.4.2 Interior-Point Methods . 15
2 Linear Algebra: A Constructive Approach 17
2.1 Jordan Exchange . 17
2.2 Linear Independence . 23
2.3 Matrix Inversion . 27
2.4 Exact Solution of m Equations in n Unknowns . 32
2.5 Solving Linear Equations Efficiently 39
2.6 LU Decomposition . 41
3 The Simplex Method 45
3.1 A Simple Example 46
3.2 Vertices 51
3.3 The Phase II Procedure . 53
3.4 The Phase I Procedure 60
3.5 Finite Termination 65
viiviii Contents
3.5.1 The Nondegenerate Case . 65
3.5.2 Cycling . 66
3.5.3 The General Case . 67
3.6 Linear Programs in Nonstandard Form . 72
3.6.1 Transforming Constraints and Variables 72
3.6.2 Scheme I 76
3.6.3 Scheme II . 80
3.6.4 Summary 86
4 Duality 89
4.1 Duality and Rank in Linear Systems 89
4.2 Duality in Linear Programming . 94
4.3 Interpretation of Linear Programming Duality . 96
4.4 Duality Theory 97
4.5 KKT Optimality Conditions . 100
4.6 Dual Simplex Method 102
4.7 General Linear Programs 107
4.8 Big M Method 110
4.9 Applications of Duality . 112
5 Solving Large Linear Programs 117
5.1 Foundations . 118
5.1.1 Basic Feasible Solutions and Basis Matrices . 118
5.1.2 Geometric Viewpoint . 121
5.2 The Revised Simplex Method 123
5.2.1 Upper and Lower Bounds . 129
5.2.2 Generating Basic Feasible Solutions . 134
5.2.3 Basis Updates . 139
5.2.4 Advanced Pivot Selection Mechanisms 142
5.3 Network Flow Problems . 143
5.3.1 Minimum-Cost Network Flow . 144
5.3.2 Shortest-Path Problem . 145
5.3.3 Max-Flow Problem 146
5.3.4 Transportation Problem 147
5.3.5 Assignment Problem 149
5.3.6 Network Simplex Method . 149
6 Sensitivity and Parametric Linear Programming 151
6.1 Sensitivity Analysis . 151
6.2 Adding New Variables or Constraints 155
6.3 Parametric Optimization of the Objective Function . 158
6.4 Parametric Optimization of the Right-Hand Side 164
7 Quadratic Programming and Complementarity Problems 169
7.1 Nonlinear Programs: Optimality Conditions 169
7.2 Quadratic Programming . 172Contents ix
7.2.1 Basic Existence Result . 172
7.2.2 KKT Conditions 173
7.2.3 Duality . 176
7.3 Linear Complementarity Problems . 177
7.4 Lemke’s Method . 178
7.5 Bimatrix Games . 185
7.5.1 Computing Nash Equilibria 186
7.5.2 Zero-Sum Games As Dual Linear Programs . 192
8 Interior-Point Methods 195
8.1 Motivation and Outline . 195
8.2 Newton’s Method 197
8.3 Primal-Dual Methods 201
8.3.1 An Affine-Scaling Approach 202
8.3.2 Path-Following Methods 204
8.3.3 Solution of the Linear System at Each Interior-Point
Iteration 208
8.3.4 Practical Primal-Dual Methods 209
8.4 Interior-Point vs. Simplex 212
8.5 Extension to Quadratic Programming 212
9 Approximation and Classification 217
9.1 Minimax Problems 217
9.2 Approximation 218
9.2.1 Chebyshev Approximation . 219
9.2.2 L1 Approximation . 221
9.2.3 Approximate Solutions to Systems with Inequality
Constraints . 223
9.2.4 Least-Squares Problems 224
9.3 Huber Estimation 227
9.4 Classification Problems . 230
A Linear Algebra, Convexity, and Nonlinear Functions 237
A.1 Linear Algebra 237
A.2 Convex Sets . 239
A.3 Smooth Functions 242
A.4 Convex Functions 242
A.5 Quadratic Functions . 244
A.6 Norms and Order Notation . 247
A.7 Taylor’s Theorem 249
B Summary of Available MATLAB Commands 251
B.1 Basic MATLAB Operations . 251
B.2 MATLAB Functions Defined in This Book . 252x Contents
Bibliography 257
Index 26
Index
affine-scaling method, 202–204, 206, 210
poor performance of, 203
steplength choice, 203
approximation problems, 218–227
1-norm, 221–224
2-norm. See least-squares problems
∞-norm. See Chebyshev approximation
for linear equalities, 218–223
with hard constraints, 223–224, 227
arc, 12–14, 144
back substitution. See triangular substitution
basic feasible solution, 118
as iterates ofrevised simplexmethod,
123
associationwith basismatrix, 120–121
association with vertex, 121–123
degenerate, 120
existence, 119–120
initial, 129, 134–139
basic solution, 118
basis, 117, 126, 152
for problemswith bound constraints,
130
initial, 125, 134–137
optimal, 129, 152–156
basis matrix, 52, 118, 120, 123, 139, 140,
154
for network linear program, 149
LU factorization of, 139–142
big M method, 110–112
behavior on infeasible problems, 112
motivation, 110–111
proof of effectiveness, 111
specification, 111–112
bimatrix game, 185
Bland’s rule. See smallest-subscript rule
blocking variable, 48
breakpoint, 163
canonical form, 8, 16, 45, 117, 120, 123,
129, 130, 134, 138, 139, 150,
151, 156, 195, 197
dual of, 109
for problemswith bound constraints,
130
centering parameter, 206, 214
central path, 205
Chebyshev approximation, 219–221, 223
Cholesky factorization, 209, 212
classification, 11–12, 230–235
labeled points, 230
testing set, 235
training set, 235
tuning set, 235
classifier, 230
linear, 230
nonlinear, 233, 234
complementarity, 101–102, 178, 237
almost-, 178, 179
existence of strictly complementary
primal-dual solution, 114–115
strict, 101
complementary slackness.
See complementarity
concave function, 161, 244
constraints, 1
active, 14
bounds, 74–75
equality, 72–87
inactive, 14
inequality, 72–87
convex combination, 239, 241
convex function, 170, 242–244, 248
261262 Index
linear underestimation, 170, 250
strict, 173
convex hull, 56, 113, 241
convex set, 170, 173, 239–241
cost vector, 7, 151, 154
parametrized, 159
cross-validation, 235
cycling, 66–72, 104
Dantzig, George B., 7, 16
degenerate linear program, 66, 67
diet problem, 8, 96
divergence, 144
domain, 242
dual linear program
of canonical form, 196
of standard form, 94, 102
tableau representation, 94
dual linear system, 89
dual pair of linear programs. See primaldual pair of linear programs
dual simplex method, 89, 102–106, 164,
220–223
motivation for, 102
relationship to simplex method applied
to the dual, 105–106
specification of, 103–104
duality, 89–115
for quadratic programs, 176–177
practical example, 96–98
strong, 98–99
applications of, 112–115, 167
for quadratic programming, 176–177
weak, 97–98, 101, 111, 176
duality gap, 197
duality measure, 197, 205, 213
ellipsoid method, 15
entering variable, 47
epigraph, 217, 242–243
equilibrium pair. See Nash equilibrium
expected loss, 185
Farkas lemma, 112–113
feasible point, 3
dual, 98, 103
feasible region, 3, 46, 51, 53, 169, 171,
182
feasible set. See feasible region
feature space, 233
fickle variable, 69
finite termination of simplex method,
65–72
floating-point number, 127
floating-point operations, 39
forward substitution. See triangular
substitution
Frank–Wolfe theorem, 172–173
fundamental theorem of algebra, 113, 225
Gaussian elimination, 39
general form of linear program, 75
dual of, 107–109
global solution, 170, 171, 173, 182
Gordan theorem, 113
gradient, 172, 242, 244, 247
graphical solution of linear programs, 2–6
Hessian, 171, 172, 214, 224, 242, 244,
245
Huber estimation
formulation as quadratic program,
229–230
motivation and definition, 227–228
optimality conditions, 228–229
infeasible linear program, 14, 62, 98, 225
infeasible point, 3
integer programming, 7, 16
interior-point methods
basic properties of primal-dual
methods, 196–197
comparison with simplex method, 212
introduction, 15, 195–197
path-following. See path-following
methods
relationship to Newton’s method, 202
Jacobian, 199, 202, 249
Jordan exchange, 17–23, 26, 27, 46–48,
53, 83, 179, 221. See also pivot
block, 31Index 263
blocking of, 25, 33, 36, 38
interpretation on dual tableaus, 89–91
Karmarkar, Narendra, 15, 214
Karush–Kuhn–Tucker (KKT) conditions,
100–101, 129, 192, 195
as constrained nonlinear equations,
201–202
for canonical form, 195, 196
for linear programs in general form,
108
for quadratic programs, 173–175, 181,
184–185, 212, 229, 233
statement of, 100–101
kernel, 234
Gaussian, 234–235
linear, 234
polynomial, 234
KKT (Karush–Kuhn–Tucker) conditions.
See Karush–Kuhn–Tucker
conditions
knapsack problem, 130
Lagrange multipliers, 173, 176, 195, 229,
232
Lagrangian, 176
LCP. See linear complementarity
problem (LCP)
least-squares problems, 211, 224–229
normal equations, 225
leaving variable, 48, 156
Lemke’s method, 178–185
application to quadratic programs,
182–185
outline of, 178
Phase I, 178–179, 188
Phase II, 179, 188
termination of, 182
Lemke–Howson method, 187
level set, 243
linear combination, 240
linear complementarity problem (LCP),
169, 177–178
definition, 177
infeasible, 182
relationship to quadratic programming,
174, 177, 180, 182
linear dependence, 23, 24, 138, 221
of functions, 24
linear equations, 32–39
inconsistent, 218, 227
overdetermined, 220, 221, 223, 224,
226, 227, 230
solution using Gaussian elimination,
39–41
solution using Jordan exchanges,
32–39
flop count, 39, 44
with infinitely many solutions, 37
linear independence, 17, 23–27, 51, 52,
118, 119
of functions, 24
of rows/columns in a matrix, 92
local solution, 169, 170, 173, 184
LU decomposition. See LU factorization
LU factorization, 17, 39–44, 127, 138, 197
complete pivoting, 43
flop count, 44
partial pivoting, 42–44
updating, 139–142
matching pennies game, 188–191, 193
matrix
addition, 239
basis. See basis matrix
diagonal, 196, 208, 238
eigenvalues, 246
identity, 238
indefinite, 208, 214, 245
inverse, 27–31, 238
invertible, 51, 152, 225
loss, 185–188, 191
lower triangular, 39, 209, 239
unit, 40
multiplication, 239
nonsingular, 27
permutation, 39–41, 139, 209, 238
poorly conditioned, 226
positive definite, 245, 246
positive semidefinite, 172, 174, 176,
224, 245, 246264 Index
representation in MATLAB, 251–252
singular, 27, 31
skew-symmetric, 178
sparse, 208, 209, 238
symmetric, 172, 244
totally unimodular, 150
transpose, 238
upper triangular, 39
Mehrotra predictor-corrector method.
See path-following methods
minimax problems, 217–218
discrete, 218
minimum principle, 170, 173, 184
mixed strategy, 185
mixed-integer linear programming, 150
monotone, 247
Nash equilibrium, 186, 192
computation of, 186–187
Nash, John, 169, 186
network linear program, 143–150
assignment problem, 149
circulation problem, 147
general properties, 143–144
max-flow, 146–147
minimum-cost, 12–14, 144–146, 149
node-arc incidence matrix, 145
shortest-path, 145–146
transportation problem, 147–149
network simplex method, 149–150
Newton’s method, 197–201
for scalar nonlinear equations, 197–198
for systems of nonlinear equations,
197–201
quadratic convergence of, 199
with line search, 201
node, 12, 144
demand, 13, 145
sink, 145
supply, 13
nondegenerate linear program, 65, 66
nonlinear programming, 169–172
nonnegative orthant, 171, 251
norm, 218, 247–248
1, 221, 247
2, 231, 247
p, 219, 247
∞, 219, 247
dual, 231, 248
equivalence of, 248
objective function, 1, 154, 241
contours, 4, 46, 159
optimal face, 58. See also solution set
order notation
O(·), 248
o(·), 248–250
parametric programming, 151, 158–168
path-following methods
MATLAB implementation of, 209
choice of centering parameter, 207,
210
choice of starting point, 211
choice of steplength, 207, 211
corrector direction, 210, 211
for quadratic programming, 212–214
linear algebra issues, 208–209, 211,
214
normal-equations form, 208
long-step, 206–207
specification of algorithm, 206–207
motivation, 204–205
practical enhancements, 209–211
relationship to Newton’s method,
205–206
permutation, 29
Phase I of simplex method, 60–65, 179,
223
after addition of constraints, 157
description of, 60–65
dual simplex as possible alternative,
102, 104
for canonical form, 134–138
for problems with parametrized constraints, 167
for solution of linear inequalities, 64
purpose of, 53
Phase II of simplex method, 53–60, 62,
71, 103, 135–137
piecewise-linear function, 161, 163, 217Index 265
pivot, 18, 20, 46, 47. See also Jordan exchange
block, 31
degenerate, 62, 64, 69
nondegenerate, 67
submatrix, 31
pivot selection, 15. See also pricing
Devex, 142, 143
for dual simplex, 103
for Lemke’s algorithm, 179
steepest-edge, 142
polynomial complexity, 207
predictor-corrector method.
See path-following methods
preprocessing, 212
pricing, 47, 49, 53, 68, 117
partial, 142
primal-dual methods. See interior-point
methods
primal-dual pair of linear programs, 89
definition, 94
for general linear programs, 108
interior-point methods and, 195
optimality conditions for, 100
weak duality for, 97
zero-sum games and, 192
prisoners’ dilemma, 186, 191
projection, 173, 205, 244
pure strategies, 185
QR factorization, 226
quadratic function, 244–247
convex, 244–247
quadratic programming, 7, 172–177,
212–215, 227, 231
convex, 172, 173, 175, 212
general form, 175
infeasible, 182, 183
nonconvex, 182, 184
unbounded, 182, 183
rank, 91, 225
determination via Jordan exchanges,
91–92
full, 225
ratio test, 48, 126, 203
after addition of constraints, 157
definition, 49
for dual simplex method, 103, 104,
157, 165
in Lemke’s method, 179, 180, 188
robust implementation of, 143
ties in, 66, 68
reduced costs, 49, 68, 124, 132, 142, 152,
153, 160
regression problems. See approximation
problems
residual vector, 219, 221, 227
outliers, 227
resource allocation, 10–11
revised simplex method, 52, 117, 123–143,
156
choice of initial basis, 125
for problems with bound constraints,
129, 134
fundamental idea, 123–124
initial basic feasible solution, 134–139
linear algebra in, 124–126
pivot selection, 142–143
roundoff error issues, 127–129
specification, 124
roundoff error, 28, 127, 143
saddle point, 184
scalar product, 252
Scheme II for linear programs in nonstandard form, 72, 80–86, 157, 220,
221, 223
Schur complement, 31
sensitivity analysis, 4, 151
separating hyperplane, 11, 230, 231, 233
separation lemma, 113
shadow prices, 97, 154, 155. See also
Lagrange multipliers
Sherman–Morrison–Woodbury formula,
140
shifting, 74
simplex method, 6, 7, 45–87
introduction, 14–15
network, 149–150
slack variables, 8, 45, 117, 152, 196
definition, 45
dual, 101, 103266 Index
smallest-subscript rule, 67–72, 78, 104
solution set, 58–60
source, 145
standard form, 7, 16, 45, 117, 151
standard form, transformation to, 72–76
free variable method, 75
Scheme I, 72, 76–80
Scheme II, 80–86
substitution method, 74
Steinitz theorem, 26–27, 38, 92
support vector machines
linear, 230–233
linear programming (1)formulation,
233
nonlinear, 233–234
nonseparable, 231–233
separable, 230–231
support vectors, 231, 232
tableau, 18–20
augmented, 62
condensed, 45, 47, 123
degenerate, 65, 66, 120
dual, 89
feasible, 46, 187
initial, 47, 119
labels, 21
MATLAB representation, 21–22
nondegenerate, 65
optimal, 49, 53, 58, 71, 152–154,
156
primal, 89
unbounded, 54
Taylor’s theorem, 170, 198, 199, 249
theorem of the alternative, 113
tolerance
pivot, 127
slack, 127
triangular substitution, 40, 139, 141, 209
unbounded linear program, 14, 46, 54–56,
66, 98
unbounded ray, 54, 182, 183
uncertainty in formulation, 151
variables, 2
artificial, 61, 62, 135, 167, 179, 218
for equality constraints, 80–82, 193
basic, 45, 152
blocking, 133
dependent, 18, 21, 23
dual, 89. See also Lagrange
multipliers
free, 75, 80, 107, 134, 136–139, 167,
184, 222
independent, 18, 21, 23, 26
nonbasic, 45, 51, 130
nonnegative, 107
slack. See slack variables
vector
norm. See norm
notation, 237
representation in MATLAB, 251
vertex, 14–15, 46, 51–53, 120, 163
adjacent, 15
degenerate, 52
zero-sum game, 185, 192–193
#ماتلاب,#متلاب,#Matlab,
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net
أتمنى أن تستفيدوا من محتوى الموضوع وأن ينال إعجابكم
رابط من موقع عالم الكتب لتنزيل كتاب Linear Programming With MATLAB
رابط مباشر لتنزيل كتاب Linear Programming With MATLAB 
|
|
