Optimization Toolbox For Use with MATLAB Computation Visualization Programming User's Guide The MathWorks Version 2
Computation Visualization Programming For Use with MATLAB® User’s Guide Version 2 Optimization Toolbox
Contents Preface Using This Guide Related products Typographical Conventions Introduction What Is the Optimization To 1-2 New Features in version 2.2 ..13 New fsolve Default algorithm Configuration Information Technical conventions 1-5 Matrix Vector and Scalar notation Acknowledgment Tutorial Introduction Problems Covered by the Toolbox Using the Optimization Functions 25
i Contents Preface Using This Guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Related Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Typographical Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 Introduction What Is the Optimization Toolbox? . . . . . . . . . . . . . . . . . . . . . 1-2 New Features in Version 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-3 New fsolve Default Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 1-3 Configuration Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-4 Technical Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-5 Matrix, Vector, and Scalar Notation . . . . . . . . . . . . . . . . . . . . . 1-5 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-6 2 Tutorial Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-3 Problems Covered by the Toolbox . . . . . . . . . . . . . . . . . . . . . . . . 2-3 Using the Optimization Functions . . . . . . . . . . . . . . . . . . . . . . . 2-5
Examples that Use Standard Algorithm 27 Unconstrained Minimization Example 2-8 Nonlinear Inequality Constrained Example 2-9 Constrained Example with Bounds 2-11 Constrained Example with gradients Gradient Check: Analytic Versus Numeric Equality Constrained Example 2-15 Maximization 2-16 Greater-Than-Zero Constraints 2-16 Additional Arguments: Avoiding Global Variables 2-16 Nonlinear Equations with analytic Jacobian Nonlinear Equations with Finite-Difference Jacobian 220 Multiobjective Examples Large-Scale Examples 2-33 Problems Covered by Large-Scale Methods Nonlinear Equations with Jacobian Nonlinear Equations with Jacobian Sparsity Pattern 239 Nonlinear Least-squares with Full Jacobian Sparsity Pattern Nonlinear minimization with gradient and hessian Nonlinear Minimization with gradient and Hessian Sparsity Pattern 2-44 Nonlinear Minimization with bound Constraints and banded Precondit 2-46 Nonlinear Minimization with Equality Constraint 2-50 Nonlinear minimization with a dense but structured Hessian and Equality Constraints 2-51 Quadratic Minimization with Bound Constraints Quadratic Minimization with a Dense but Structured Linear Least-Squares with Bound Constraints 2-60 Linear Programming with Equalities and Inequalities 2-61 Linear Programming with Dense Columns in the Equalities. 2-62 Default Parameter Settings 2-65 Changing the Default Settings 2-65 Displaying Iterative Output 2-68 Output Headings: Medium-Scale algorithms
ii Contents Examples that Use Standard Algorithms . . . . . . . . . . . . . . . . 2-7 Unconstrained Minimization Example . . . . . . . . . . . . . . . . . . . . 2-8 Nonlinear Inequality Constrained Example . . . . . . . . . . . . . . . 2-9 Constrained Example with Bounds . . . . . . . . . . . . . . . . . . . . . 2-11 Constrained Example with Gradients . . . . . . . . . . . . . . . . . . . 2-12 Gradient Check: Analytic Versus Numeric . . . . . . . . . . . . . . . 2-14 Equality Constrained Example . . . . . . . . . . . . . . . . . . . . . . . . . 2-15 Maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-16 Greater-Than-Zero Constraints . . . . . . . . . . . . . . . . . . . . . . . . 2-16 Additional Arguments: Avoiding Global Variables . . . . . . . . . 2-16 Nonlinear Equations with Analytic Jacobian . . . . . . . . . . . . . . 2-17 Nonlinear Equations with Finite-Difference Jacobian . . . . . . 2-20 Multiobjective Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-21 Large-Scale Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-33 Problems Covered by Large-Scale Methods . . . . . . . . . . . . . . . 2-34 Nonlinear Equations with Jacobian . . . . . . . . . . . . . . . . . . . . . 2-37 Nonlinear Equations with Jacobian Sparsity Pattern . . . . . . . 2-39 Nonlinear Least-Squares with Full Jacobian Sparsity Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-41 Nonlinear Minimization with Gradient and Hessian . . . . . . . 2-43 Nonlinear Minimization with Gradient and Hessian Sparsity Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-44 Nonlinear Minimization with Bound Constraints and Banded Preconditioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-46 Nonlinear Minimization with Equality Constraints . . . . . . . . 2-50 Nonlinear Minimization with a Dense but Structured Hessian and Equality Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-51 Quadratic Minimization with Bound Constraints . . . . . . . . . . 2-55 Quadratic Minimization with a Dense but Structured Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-57 Linear Least-Squares with Bound Constraints . . . . . . . . . . . . 2-60 Linear Programming with Equalities and Inequalities . . . . . . 2-61 Linear Programming with Dense Columns in the Equalities . 2-62 Default Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-65 Changing the Default Settings . . . . . . . . . . . . . . . . . . . . . . . . . 2-65 Displaying Iterative Output . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-68 Output Headings: Medium-Scale Algorithms . . . . . . . . . . . . . 2-68
Output Headings: Large-Scale algorithms Optimization of Inline Objects Instead of M-Files 2-74 Typical Problems and How to Deal with Them 276 Converting Your Code to Version 2 Syntax U t and optimget New Calling Sequences Example of Converting from constr to fmincon Selected Bibliography 2-92 Standard Algorithms 3 Optimization Overview Unconstrained Optimization Quasi-Newton Methods 36 Line search 38 Quasi-Newton Implementation Least-Squares Optimization 3-18 Gauss-Newton method 3-19 Levenberg- Marquardt Method Nonlinear Least-Squares Implementation Nonlinear Systems of Equations 3-24 Method 3-24 Trust-Region Dogleg Method 3-24 Nonlinear Equations Implementation Constrained Optimization .... 3-28 Sequential quadratic Programming(SQP) quadratic Programming(QP) Subproblem SQP Implementatie
iii Output Headings: Large-Scale Algorithms . . . . . . . . . . . . . . . 2-71 Optimization of Inline Objects Instead of M-Files . . . . . . . 2-74 Typical Problems and How to Deal with Them . . . . . . . . . . 2-76 Converting Your Code to Version 2 Syntax . . . . . . . . . . . . . 2-80 Using optimset and optimget . . . . . . . . . . . . . . . . . . . . . . . . . . 2-81 New Calling Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-81 Example of Converting from constr to fmincon . . . . . . . . . . . . 2-89 Selected Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-92 3 Standard Algorithms Optimization Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-4 Quasi-Newton Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-6 Line Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-8 Quasi-Newton Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 3-11 Least-Squares Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-18 Gauss-Newton Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-19 Levenberg-Marquardt Method . . . . . . . . . . . . . . . . . . . . . . . . . 3-20 Nonlinear Least-Squares Implementation . . . . . . . . . . . . . . . . 3-22 Nonlinear Systems of Equations . . . . . . . . . . . . . . . . . . . . . . . 3-24 Gauss-Newton Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-24 Trust-Region Dogleg Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-24 Nonlinear Equations Implementation . . . . . . . . . . . . . . . . . . . 3-26 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-28 Sequential Quadratic Programming (SQP) . . . . . . . . . . . . . . . 3-29 Quadratic Programming (QP) Subproblem . . . . . . . . . . . . . . . 3-30 SQP Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-31
Multiobjective Optimization Introduction Goal Attainment method Algorithm Improvements for Goal Attainment Method Selected Bibliography 3-48 Large-Scale algorithms 4 Trust-Region Methods for Nonlinear Minimization 4-2 Preconditioned Conjugate Gradients 4-5 Linearly Constrained Problems Linear Equality Constraints Box Constraints Nonlinear Least-Squares 4-10 Quadratic Programming 4-11 Linear Least-Squares 4-12 Large-Scale Linear Programming Main algorithm 4-13 processing 4-16 Selected Bibliography 4-17
iv Contents Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 3-38 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-38 Goal Attainment Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-44 Algorithm Improvements for Goal Attainment Method . . . . . 3-45 Selected Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-48 4 Large-Scale Algorithms Trust-Region Methods for Nonlinear Minimization . . . . . . . 4-2 Preconditioned Conjugate Gradients . . . . . . . . . . . . . . . . . . . 4-5 Linearly Constrained Problems . . . . . . . . . . . . . . . . . . . . . . . . 4-7 Linear Equality Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-7 Box Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-7 Nonlinear Least-Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-10 Quadratic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-11 Linear Least-Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-12 Large-Scale Linear Programming . . . . . . . . . . . . . . . . . . . . . 4-13 Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-13 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-16 Selected Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-17