Solving Optimization Problems with MATLAB® / Edition 1

by Dingyü Xue, Tsinghua University Press

Overview

This book focuses on solving optimization problems with MATLAB. Descriptions and solutions of nonlinear equations of any form are studied first. Focuses are made on the solutions of various types of optimization problems, including unconstrained and constrained optimizations, mixed integer, multiobjective and dynamic programming problems. Comparative studies and conclusions on intelligent global solvers are also provided.

Product Details

ISBN-13:	9783110663648
Publisher:	De Gruyter
Publication date:	04/06/2020
Series:	De Gruyter STEM
Pages:	342
Product dimensions:	6.69(w) x 9.45(h) x (d)
Age Range:	18 Years

About the Author

Dingyü Xue, Northeastern University, Shenyang, China

Table of Contents

Preface v

1 An introduction to equations and optimization problems 1

1.1 Equations and their solutions 1

1.2 Origins and development of optimization problems 2

1.3 Structure of the book 3

1.4 Exercises 4

2 Solutions of algebraic equations 7

2.1 Solutions of polynomial equations 7

2.1.1 Polynomial equations of degrees 1 and 2 8

2.1.2 Analytical solutions of cubic equations 9

2.1.3 Analytical solutions of quartic equation 10

2.1.4 Higher-degree equations and Abel-Ruffini theorem 13

2.2 Graphical methods for nonlinear equations 13

2.2.1 Smooth graphics for implicit functions 13

2.2.2 Univariate equations 15

2.2.3 Equations with two unknowns 17

2.2.4 Isolated equation solutions 20

2.3 Numerical solutions of algebraic equations 20

2.3.1 Newton-Raphson iterative algorithm 20

2.3.2 Direct solution methods with MATLAB 25

2.3.3 Accuracy specifications 28

2.3.4 Complex domain solutions 29

2.4 Accurate solutions of simultaneous equations 31

2.4.1 Analytical solutions of low-degree polynomial equations 32

2.4.2 Quasianalytical solutions of polynomial-type equations 35

2.4.3 Quasianalytical solutions of polynomial matrix equations 37

2.4.4 Quasianalytical solutions of nonlinear equations 40

2.5 Nonlinear matrix equations with multiple solutions 41

2.5.1 An equation solution idea and its implementation 41

2.5.2 Pseudopolynomial equations 46

2.5.3 A quasianalytical solver 48

2.6 Underdetermined algebraic equations 49

2.7 Exercises 51

3 Unconstrained optimization problems 55

3.1 Introduction to unconstrained optimization problems 55

3.1.1 The mathematical model of unconstrained optimization problems 55

3.1.2 Analytical solutions of unconstrained minimization problems 56

3.1.3 Graphical solutions 56

3.1.4 Local and global optimum solutions 58

3.1.5 MATLAB implementation of optimization algorithms 60

3.2 Direct solutions of unconstrained optimization problem with MATLAB 62

3.2.1 Direct solution methods 62

3.2.2 Control options in optimization 65

3.2.3 Additional parameters 69

3.2.4 Intermediate solution process 70

3.2.5 Structured variable description of optimization problems 72

3.2.6 Gradient information 73

3.2.7 Optimization solutions from scattered data 77

3.2.8 Parallel computation in optimization problems 78

3.3 Towards global optimum solutions 79

3.4 Optimization with decision variable bounds 83

3.4.1 Univariate optimization problem 83

3.4.2 Multivariate optimization problems 85

3.4.3 Global optimum solutions 87

3.5 Application examples of optimization problems 87

3.5.1 Solutions of linear regression problems 88

3.5.2 Least-squares curve fitting 89

3.5.3 Shooting method in boundary value differential equations 93

3.5.4 Converting algebraic equations into optimization problems 96

3.6 Exercises 97

4 Linear and quadratic programming 103

4.1 An introduction to linear programming 104

4.1.1 Mathematical model of linear programming problems 104

4.1.2 Graphical solutions of linear programming problems 105

4.1.3 Introduction to the simplex method 106

4.2 Direct solutions of linear programming problems 110

4.2.1 A linear programming problem solver 110

4.2.2 Linear programming problems with multiple decision vectors 116

4.2.3 Linear programming with double subscripts 117

4.2.4 Transportation problem 118

4.3 Problem-based description and solution of linear programming problems 122

4.3.1 MPS file for linear programming problems 122

4.3.2 Problem-based description of linear programming problems 124

4.3.3 Conversions in linear programming problems 129

4.4 Quadratic programming 130

4.4.1 Mathematical quadratic programming models 131

4.4.2 Direct solutions of quadratic programming problems 131

4.4.3 Problem-based quadratic programming problem description 132

4.4.4 Quadratic programming problem with double subscripts 136

4.5 Linear matrix inequalities 138

4.5.1 Description of linear matrix inequality problems 138

4.5.2 Lyapunov inequalities 139

4.5.3 Classifications of LMI problems 141

4.5.4 MATLAB solutions of LMI problems 142

4.5.5 Optimization solutions with YALMIP toolbox 144

4.5.6 Trials on nonconvex problems 146

4.5.7 Problems with quadratic constraints 147

4.6 Exercises 149

5 Nonlinear programming 153

5.1 Introduction to nonlinear programming 153

5.1.1 Mathematical models of nonlinear programming problems 154

5.1.2 Feasible regions and graphical methods 154

5.1.3 Examples of numerical methods 157

5.2 Direct solutions of nonlinear programming problems 159

5.2.1 Direct solution using MATLAB 159

5.2.2 Handling of earlier termination phenomenon 165

5.2.3 Gradient information 166

5.2.4 Solving problems with multiple decision vectors 168

5.2.5 Complicated nonlinear programming problems 169

5.3 Trials with global nonlinear programming solver 171

5.3.1 Trials on global optimum solutions 171

5.3.2 Nonconvex quadratic programming problems 174

5.3.3 Concave-cost transportation problem 176

5.3.4 Testing of the global optimum problem solver 178

5.3.5 Handling piecewise objective functions 179

5.4 Bilevel programming problems 181

5.4.1 Bilevel linear programming problems 182

5.4.2 Bilevel quadratic programming problem 183

5.4.3 Bilevel program solutions with YALMIP Toolbox 184

5.5 Nonlinear programming applications 185

5.5.1 Maximum inner polygon inside a circle 185

5.5.2 Semiinfinite programming problems 189

5.5.3 Pooling and blending problem 193

5.5.4 Optimization design of heat exchange network 196

5.5.5 Solving nonlinear equations with optimization techniques 199

5.6 Exercises 201

6 Mixed integer programming 207

6.1 Introduction to integer programming 207

6.1.1 Integer and mixed-integer programming problems 207

6.1.2 Computational complexity of integer programming problems 208

6.2 Enumeration methods for integer programming 209

6.2.1 An introduction to the enumeration method 209

6.2.2 Discrete programming 213

6.2.3 0-1 programming 214

6.2.4 Trials on mixed-integer programming problems 216

6.3 Solutions of mixed-integer programming problems 219

6.3.1 Mixed-integer linear programming 219

6.3.2 Integer programming with YALMIP Toolbox 222

6.3.3 Mixed-integer nonlinear programming 223

6.3.4 A class of discrete programming problems 226

6.3.5 Solutions of ordinary discrete programming problems 227

6.4 Mixed 0-1 programming problems 229

6.4.1 0-1 linear programming problems 229

6.4.2 0-1 nonlinear programming problems 233

6.5 Mixed-integer programming applications 235

6.5.1 Optimal material usage 235

6.5.2 Assignment problem 236

6.5.3 Traveling salesman problem 238

6.5.4 Knapsack problems 242

6.5.5 Sudoku problems 244

6.6 Exercises 247

7 Multiobjective programming 253

7.1 Introduction to multiobjective programming 253

7.1.1 Background introduction 253

7.1.2 Mathematical model of multiobjective programming 254

7.1.3 Graphical solution of multiobjective programming problems 255

7.2 Multiobjective programming conversions and solutions 257

7.2.1 Least-squares solutions of multiobjective programming problems 258

7.2.2 Linear weighting conversions 260

7.2.3 Best compromise solution of linear programs 261

7.2.4 Least-squares linear programming 263

7.3 Pareto optimal solutions 264

7.3.1 Nonuniqueness of multiobjective programming 265

7.3.2 Dominant solutions and Pareto frontiers 265

7.3.3 Computations of Pareto frontier 267

7.4 Minimax problems 268

7.5 Exercises 275

8 Dynamic programming and shortest paths 277

8.1 An introduction to dynamic programming 277

8.1.1 Concept and mathematical models in dynamic programming 277

8.1.2 Dynamic programming solutions of linear programming problems 278

8.2 Shortest path problems in oriented graphs 279

8.2.1 Examples of oriented graphs 280

8.2.2 Manual solutions of shortest path problem 281

8.2.3 Solution with dynamic programming formulation 282

8.2.4 Matrix representation of graphs 283

8.2.5 Finding the shortest path 284

8.2.6 Dijkstra algorithm implementation 288

8.3 Optimal paths for undigraphs 290

8.3.1 Matrix description 290

8.3.2 Route planning for cities with absolute coordinates 292

8.4 Exercises 293

9 Introduction to intelligent optimization methods 297

9.1 Intelligent optimization algorithms 297

9.1.1 Genetic algorithms 297

9.1.2 Particle swarm optimization methods 299

9.2 MATLAB Global Optimization Toolbox 299

9.3 Examples and comparative studies of intelligent optimization methods 301

9.3.1 Unconstrained optimization problems 302

9.3.2 Constrained optimization problems 305

9.3.3 Mixed-integer programming 312

9.3.4 Discrete programming problems with the genetic algorithm 315

9.4 Exercises 317

Bibliography 319

MATLAB function index 321

Index 325