Introduction to Linear Optimization and Extensions with MATLAB

Introduction to Linear Optimization and Extensions with MATLAB
Roy H. Kwon
Contents
Preface vii
Acknowledgments xi
About the Author xiii
1 Linear Programming 1
1.1 Introduction . 1
1.1.1 The Diet Problem 1
1.1.2 Embedded Assumptions . 5
1.2 General Linear Programming Problems 6
1.2.1 Standard Form of a Linear Program 7
1.2.2 Linear Programming Terminology . 8
1.3 More Linear Programming Examples . 10
1.3.1 Converting Minimization Problems with Absolute Value 16
1.3.2 Network Optimization Models . 19
1.3.2.1 Minimum Cost Flow Problem 20
1.3.2.2 Maximum Flow Problem . 23
1.3.3 Solving Linear Programs with MATLAB R . 25
1.4 Exercises . 29
1.5 Computational Project . 36
2 Geometry of Linear Programming 43
2.1 Introduction . 43
2.2 Geometry of the Feasible Set 43
2.2.1 Geometry of Optimal Solutions . 49
2.3 Extreme Points and Basic Feasible Solutions . 52
2.3.1 Generating Basic Feasible Solutions 58
2.3.1.1 Generating Basic Feasible Solutions with
MATLAB R 61
2.3.2 Degeneracy 63
2.4 Resolution (Representation) Theorem . 64
2.4.1 Fundamental Theorem of Linear Programming 67
2.5 Exercises
4.9 Exercises . 172
5 Dantzig-Wolfe Decomposition 177
5.1 Introduction . 177
5.2 Decomposition for Block Angular Linear Programs 177
5.3 Master Problem Reformulation . 180
5.4 Restricted Master Problem and the Revised Simplex Method 182
5.5 Dantzig-Wolfe Decomposition . 185
5.5.1 Economic Interpretation . 201
5.5.2 Initialization . 202
5.5.3 Bounds on Optimal Cost 202
5.6 Dantzig-Wolfe MATLAB R Code 205
5.6.1 DantzigWolfeDecomp MATLAB Code . 207
5.7 Exercises . 211
6 Interior Point Methods 217
6.1 Introduction . 217
6.2 Linear Programming Optimality Conditions . 217
6.2.1 Newton-Raphson Method 219
6.3 Primal-Dual Interior Point Strategy 223
6.3.1 Barrier Reformulation 224
6.3.1.1 Newton-Raphson Method for KKT Conditions
of the Barrier Problem 225
6.3.2 General Primal-Dual Interior Point Method 227
6.3.2.1 Starting with an Infeasible Interior Point 228
6.3.3 Complexity of General Primal-Dual Interior Path Following Methods 229
6.3.3.1 Polynomial Complexity of Short-Step PathFollowing Methods . 232
6.4 The Predictor-Corrector Variant of the Primal-Dual Interior
Point Method 233
6.4.1 Predictor Step 233
6.4.2 Setting the Centering Parameter 234
6.4.3 Corrector and Centering Step 234
6.4.4 Computational Overhead 235
6.4.5 Predictor-Corrector Algorithm . 235
6.4.5.1 Initial Point Generation 236
6.5 Primal-Dual Interior Point Method in MATLAB R 241
6.5.1 MATLAB Code 242
6.6 Exercises . 244
7 Quadratic Programming 249
7.1 Introduction . 249
7.2 QP Model Structure . 249
7.3 QP Application: Financial Optimization
7.4 Solving Quadratic Programs Using MATLAB R . 257
7.4.1 Generating the Efficient Frontier Using MATLAB 258
7.5 Optimality Conditions for Quadratic Programming . 259
7.5.1 Local and Global Optima 260
7.5.2 Unconstrained Quadratic Programs 261
7.5.2.1 Convex Unconstrained Quadratic Programming (Global Optimality) . 265
7.5.3 Convex Optimization 268
7.5.4 Equality-Constrained Quadratic Programs . 269
7.5.4.1 Alternative Solution Methods for EQP . 273
7.5.5 Inequality Constrained Convex Quadratic Programming 274
7.5.6 Predictor-Corrector Algorithm for Convex QP 275
7.6 Exercises . 281
8 Linear Optimization under Uncertainty 287
8.1 Introduction . 287
8.2 Stochastic Programming 288
8.2.1 Stochastic Programming with Recourse 290
8.2.1.1 Two-Stage Stochastic Programming with Recourse 293
8.3 More Stochastic Programming Examples . 297
8.3.1 Solving Two-Stage Stochastic Programs with Recourse 300
8.3.1.1 Dantzig-Wolfe Decomposition for Stochastic
Programming 301
8.3.1.2 L-Shaped Method (Constraint Generation) . 301
8.3.1.3 Convergence of the L-Shaped Method 309
8.4 Robust Optimization 310
8.4.1 Constraint-wise Construction of RC: 311
8.5 Exercises . 318
A Linear Algebra Review 323
Bibliography 329
Index 33

كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net