1Introduction to Optimization
158Nonlinear Programming: Fundamentals
21.1 What is Optimization?: Practice Problem 1.1.1:
1597.1 Introduction to Nonlinear Programming
31.2 Applications of Optimization: Practice Problem 1.2.1:
1607.2 Unconstrained Optimization
41.3 Types of Optimization Problems
161Several techniques have been developed to solve unconstrained optimization problems, including:
51. Linear Programming (LP):
1621. Gradient-based Methods:
62. Nonlinear Programming (NLP):
1632. Direct Search Methods:
73. Integer Programming (IP):
1643. Heuristic Methods:
84. Mixed-Integer Programming (MIP):
165Solved Example:: Practice Problem:
95. Quadratic Programming (QP):
1667.3 Constrained Optimization
106. Semidefinite Programming (SDP):
167Several techniques have been developed to solve constrained optimization problems, including:
117. Stochastic Programming:
1681. Penalty and Barrier Methods:
128. Global Optimization:: 9. Multiobjective Optimization:
1692. Projection and Feasible Direction Methods:
13Practice Problem 1.3.1:: Here are the solutions to the examples and practice problems provided in Chapter 1: Introduction to Optimization.
1703. Sequential Quadratic Programming (SQP):
14Practice Problem 1.2.1:
1714. Generalized Reduced Gradient Methods
15Practice Problem 1.3.1:
172Solved Example:
161.4 Linear vs. Nonlinear Programming
173Practice Problems:
17Linear Programming (LP):
1747.4 Convex and Non-Convex Functions
18Nonlinear Programming (NLP):: Practice Problem 1.4.1:
175Definition of Convex Function:
191.5 Modeling Optimization Problems: Practice Problem 1.5.1:
176Properties of Convex Functions:
201.6 Optimization Software and Tools
177Non-Convex Functions:
211. Commercial Optimization Software:
178Importance of Convexity in Nonlinear Programming:
222. Open-Source Optimization Tools:
179Examples of Convex and Non-Convex Functions:
233. Modeling Languages and Algebraic Modeling Systems:
180Convex Functions:: Non-Convex Functions:
244. Specialized Solvers and Libraries:
181Solved Examples:
25Practice Problem 1.6.1:: Here are the solutions to the examples and practice problems provided in Chapter 1: Introduction to Optimization.
182Practice Problems:
26Conclusion
1837.5 Optimality Conditions
27Linear Programming: Fundamentals
184Karush-Kuhn-Tucker (KKT) Conditions:
282.1 The Linear Programming Problem: Practice Problem 2.1.1:
1851. Stationarity condition:
292.2 Graphical Solution for Two-Variable Problems: Practice Problem 2.2.1:
1862. Primal feasibility:
302.3 Slack and Surplus Variables
1873. Dual feasibility:: 4. Complementary slackness:
31Slack Variables:
188Other Optimality Conditions:
32Surplus Variables:
189Solved Examples:: Practice Problems:
33Practice Problem 2.3.1:: Solutions:
1907.6 Sensitivity Analysis in Nonlinear Programming
342.4 Standard Form of Linear Programming Problems: Practice Problems:
191Parametric Sensitivity Analysis:
352.5 Sensitivity Analysis
192Sensitivity Analysis for Convex Optimization Problems:
361. Objective Function Coefficients:
193Sensitivity Analysis for Non-Convex Problems:
372. Right-Hand Side (RHS) Constants of the Constraints:
194Solved Examples:
383. Constraint Coefficients:: Practice Problems:
195Practice Problems:: Practice Problem Solutions:
392.6 Computer Solutions for Linear Programming: Practice Problems:
196Conclusion
40Conclusion
197Unconstrained Optimization Techniques
41The Simplex Method
1988.1 Gradient Descent Methods
423.1 Introduction to the Simplex Method
199Basic Gradient Descent Algorithm:
433.2 Simplex Algorithm
200Line Search Procedures:
443.3 Simplex Tableaux
201Convergence Properties:
45Solved Example 1:
202Variations and Extensions:
46Practice Problem 1:
203Solved Example:: Practice Problems:
47Solved Example 2:: Practice Problem 2:
2048.2 Newton’s Method
483.4 Unbounded and Infeasible Solutions
205Algorithm:
49Infeasible Solutions:
206Convergence Properties:
50Unbounded Solutions:
207Modifications and Globalization Strategies:
51Solved Example 1:
208Solved Example:: Practice Problems:
52Solved Example 2:
2098.3 Conjugate Gradient Methods
53Practice Problem 1:: Practice Problem 2:
210Algorithm:
543.5 Duality in Linear Programming
211Convergence Properties:: Advantages and Applications:
55The Primal Problem:
2128.4 Quasi-Newton Methods
56The Dual Problem:
213Advantages of Quasi-Newton methods:
57Dual Simplex Method:
214Disadvantages of Quasi-Newton methods:
58Sensitivity Analysis:
215Solved Example:: Practice Problem:
59Solved Example:: Practice Problem:
2168.5 Line Search Techniques
603.6 Sensitivity Analysis with the Simplex Method
217Exact Line Search:
611. Objective Function Coefficient Analysis:
218Inexact Line Search:
622. Constraint Coefficient Analysis:
219Backtracking Line Search:
633. Right-Hand Side Value Analysis:
220Goldstein Condition:
64Solved Example:
221The Goldstein condition is given by:
65Sensitivity Analysis:
222Wolfe Conditions:
661. Objective Function Coefficient Analysis:
223Advantages of line search techniques:
672. Constraint Coefficient Analysis:: 3. Right-Hand Side Value Analysis:
224Disadvantages of line search techniques:
68Practice Problem:
225Solved Example:
69Solved Example: : Here are the solutions to the practice problems:
226Practice Problem:
70Practice Problem (Section 3.6):
2278.6 Trust Region Methods
71Sensitivity Analysis:
228Advantages of trust region methods:
721. Objective Function Coefficient Analysis:
229Disadvantages of trust region methods:
732. Constraint Coefficient Analysis:: 3. Right-Hand Side Value Analysis:
230Solved Example:
74Conclusion
231Practice Problem 1:: Practice Problem 2:
75Transportation and Assignment Problems
232Conclusion
764.1 The Transportation Problem
233Constrained Optimization Techniques
77Mathematical Formulation:
2349.1 Penalty and Barrier Methods
78The decision variables are:
235Penalty Methods:
79Subject to:
236Barrier Methods:
80Assumptions:
237Solved Example:
81Solved Example:: Practice Problem:
238Solved Example:
824.2 The Northwest Corner Method
239Practice Problem 1:: Practice Problem 2:
83Solved Example:: Practice Problem:
2409.2 Augmented Lagrangian Methods
844.3 The Least-Cost Method
241Advantages of augmented Lagrangian methods:
85Solved Example:
242Disadvantages of augmented Lagrangian methods:
86Practice Problem:
243Solved Example:
87Practice Problem Solutions:
244Practice Problem 1:: Practice Problem 2:
884.2 The Northwest Corner Method - Practice Problem Solution:: 4.3 The Least-Cost Method - Practice Problem Solution:
2459.3 Sequential Quadratic Programming
894.4 The Vogel’s Approximation Method
246Advantages of SQP:
90The Vogel’s Approximation Method follows these steps:
247Disadvantages of SQP:
91Solved Example:: Practice Problem:
248Solved Example:
924.5 The Assignment Problem
249Practice Problem 1:
93Mathematical Formulation:
250Practice Problem 2:
94The decision variables are:
251Here are the solutions to the practice problems for Chapter 9:
95Subject to:
252Practice Problem 1 (Section 9.1 Penalty and Barrier Methods):
96Assumptions:
253Practice Problem 2 (Section 9.1 Penalty and Barrier Methods):
97Solved Example:: Practice Problem:
254Practice Problem 1 (Section 9.2 Augmented Lagrangian Methods):
984.6 The Hungarian Method
255Practice Problem 2 (Section 9.2 Augmented Lagrangian Methods):
99Solved Example:
256Practice Problem 1 (Section 9.3 Sequential Quadratic Programming):
100Practice Problem:
257Practice Problem 2 (Section 9.3 Sequential Quadratic Programming):
101Practice Problem Solutions:
2589.4 Interior Point Methods
1024.4 The Vogel’s Approximation Method - Practice Problem Solution:
2599.4.1 Introduction to Interior Point Methods
1034.5 The Assignment Problem - Practice Problem Solution:: 4.6 The Hungarian Method - Practice Problem Solution:
2609.4.2 Theoretical Background
104Conclusion
2619.4.3 Algorithm
105Network Optimization
2629.4.4 Advantages and Disadvantages
1065.1 Network Models
263Advantages of interior point methods:: Disadvantages of interior point methods:
107There are two main types of network models:
2649.4.5 Applications
108Solved Example:: Practice Problem:
2659.4.6 Solved Examples
1095.2 Shortest Path Problems
2669.4.7 Practice Problems
110Solved Example:: Practice Problem:
2679.5 Active Set Methods
1115.3 Minimum Spanning Tree Problems
2689.5.1 Introduction to Active Set Methods
1121. Kruskal’s Algorithm:
2699.5.2 Theoretical Background
1132. Prim’s Algorithm:
2709.5.3 Algorithm
114Solved Example:
2719.5.4 Advantages and Disadvantages
115Practice Problem:
272Advantages of active set methods:: Disadvantages of active set methods:
116Here are the solutions to the practice problems from Chapter 5: Network Optimization:
2739.5.5 Applications
117Practice Problem 5.1 Network Models:
2749.5.6 Solved Examples
118Practice Problem 5.2 Shortest Path Problems:: Practice Problem 5.3 Minimum Spanning Tree Problems:
2759.5.7 Practice Problems
1195.4 Maximum Flow Problems
2769.6 Successive Linear Programming
120Formal Definition:
2779.6.1 Introduction to Successive Linear Programming
121Applications of Maximum Flow Problems:
2789.6.2 Theoretical Background
122Algorithms for Solving Maximum Flow Problems:
2799.6.3 Algorithm
123Solved Example:: Practice Problem:
2809.6.4 Advantages and Disadvantages
1245.5 Project Scheduling (PERT/CPM)
281Advantages of successive linear programming:: Disadvantages of successive linear programming:
125PERT (Program Evaluation and Review Technique):: CPM (Critical Path Method):
2829.6.5 Applications
1265.6 Network Simplex Method
2839.6.6 Solved Examples
127Minimum Cost Flow Problem:
2849.6.7 Practice Problems
128Formal Definition:
285Conclusion
129Key Steps of the Network Simplex Method:
286Convex Optimization
130Applications of the Network Simplex Method:
28710.1 Convex Sets and Functions
131Solved Example:: Practice Problem:
28810.1.1 Convex Sets
132Conclusion
28910.1.2 Convex Functions
133Integer Programming
29010.1.3 Convex Optimization Problems
1346.1 Introduction to Integer Programming
29110.1.4 Solved Examples
1356.2 Formulating Integer Programming Problems
29210.1.5 Practice Problems
1366.3 Cutting Plane Methods
29310.2 Optimality Conditions for Convex Problems
137Solved Example:
29410.2.1 First-Order Optimality Conditions
138Formulation:
295Subgradients:
139Practice Problems:
296Karush-Kuhn-Tucker (KKT) Conditions:
140Additional Examples and Practice Problems:: Practice Problem: Knapsack Problem
2971. Stationarity:
1416.4 Branch-and-Bound Method: Solved Example:
2982. Primal feasibility:
1426.5 Heuristic Methods for Integer Programming
2993. Dual feasibility:: 4. Complementary slackness:
1431. Rounding Heuristics:
30010.2.2 Second-Order Optimality Conditions
1442. Greedy Heuristics:
301Consider the convex optimization problem:
1453. Local Search Heuristics:
302Second-Order Necessary Condition:
1464. Metaheuristics:
303Second-Order Sufficient Condition:
1475. Lagrangian Relaxation:: 6. Column Generation:
30410.2.3 Solved Examples
148Greedy Heuristic Algorithm:
30510.2.4 Practice Problems
149Simulated Annealing Heuristic:: Solved Example:
30610.3 Duality in Convex Optimization
150Greedy Heuristic Algorithm:
30710.3.1 Lagrangian Duality
151Following the greedy heuristic algorithm:: Practice Problems:
30810.3.2 Duality Gap
1526.6 Applications of Integer Programming
30910.3.3 Applications of Duality
1531. Production Planning and Scheduling
31010.3.4 Solved Examples
1542. Facility Location and Supply Chain Optimization
31110.3.5 Practice Problems
1553. Transportation and Logistics
312Conclusion
1564. Capital Budgeting and Project Selection: 5. Cutting and Packing Problems
313Glossary
157Conclusion
314Index
