Numerical methods and optimization : an introduction / Sergiy Butenko, Panos M. Pardalos
- Author:
- Butenko, Sergiy
- Published:
- Boca Raton : CRC Press : Taylor & Francis Group, [2014]
- Copyright Date:
- ©2014
- Physical Description:
- xvi, 397 pages : illustrations ; 25 cm.
- Additional Creators:
- Pardalos, P. M. (Panos M.), 1954-
- Series:
- Contents:
- Machine generated contents note: I.Basics -- 1.Preliminaries -- 1.1.Sets and Functions -- 1.2.Fundamental Theorem of Algebra -- 1.3.Vectors and Linear (Vector) Spaces -- 1.3.1.Vector norms -- 1.4.Matrices and Their Properties -- 1.4.1.Matrix addition and scalar multiplication -- 1.4.2.Matrix multiplication -- 1.4.3.The transpose of a matrix -- 1.4.4.Triangular and diagonal matrices -- 1.4.5.Determinants -- 1.4.6.Trace of a matrix -- 1.4.7.Rank of a matrix -- 1.4.8.The inverse of a nonsingular matrix -- 1.4.9.Eigenvalues and eigenvectors -- 1.4.10.Quadratic forms -- 1.4.11.Matrix norms -- 1.5.Preliminaries from Real and Functional Analysis -- 1.5.1.Closed and open sets -- 1.5.2.Sequences -- 1.5.3.Continuity and differentiability -- 1.5.4.Big O and little o notations -- 1.5.5.Taylor's theorem -- 2.Numbers and Errors -- 2.1.Conversion between Different Number Systems -- 2.1.1.Conversion of integers -- 2.1.2.Conversion of fractions -- 2.2.Floating Point Representation of Numbers -- 2.3.Definitions of Errors -- 2.4.Round-off Errors -- 2.4.1.Rounding and chopping -- 2.4.2.Arithmetic operations -- 2.4.3.Subtractive cancellation and error propagation -- II.Numerical Methods for Standard Problems -- 3.Elements of Numerical Linear Algebra -- 3.1.Direct Methods for Solving Systems of Linear Equations -- 3.1.1.Solution of triangular systems of linear equations -- 3.1.2.Gaussian elimination -- 3.1.2.1.Pivoting strategies -- 3.1.3.Gauss-Jordan method and matrix inversion -- 3.1.4.Triangular factorization -- 3.2.Iterative Methods for Solving Systems of Linear Equations -- 3.2.1.Jacobi method -- 3.2.2.Gauss-Seidel method -- 3.2.3.Application: input-output models in economics -- 3.3.Overdetermined Systems and Least Squares Solution -- 3.3.1.Application: linear regression -- 3.4.Stability of a Problem -- 3.5.Computing Eigenvalues and Eigenvectors -- 3.5.1.The power method -- 3.5.2.Application: ranking methods -- 4.Solving Equations -- 4.1.Fixed Point Method -- 4.2.Bracketing Methods -- 4.2.1.Bisection method -- 4.2.1.1.Convergence of the bisection method -- 4.2.1.2.Intervals with multiple roots -- 4.2.2.Regula-falsi method -- 4.2.3.Modified regula-falsi method -- 4.3.Newton's Method -- 4.3.1.Convergence rate of Newton's method -- 4.4.Secant Method -- 4.5.Solution of Nonlinear Systems -- 4.5.1.Fixed point method for systems -- 4.5.2.Newton's method for systems -- 5.Polynomial Interpolation -- 5.1.Forms of Polynomials -- 5.2.Polynomial Interpolation Methods -- 5.2.1.Lagrange method -- 5.2.2.The method of undetermined coefficients -- 5.2.3.Newton's method -- 5.3.Theoretical Error of Interpolation and Chebyshev Polynomials -- 5.3.1.Properties of Chebyshev polynomials -- 6.Numerical Integration -- 6.1.Trapezoidal Rule -- 6.2.Simpson's Rule -- 6.3.Precision and Error of Approximation -- 6.4.Composite Rules -- 6.4.1.The composite trapezoidal rule -- 6.4.2.Composite Simpson's rule -- 6.5.Using Integrals to Approximate Sums -- 7.Numerical Solution of Differential Equations -- 7.1.Solution of a Differential Equation -- 7.2.Taylor Series and Picard's Methods -- 7.3.Euler's Method -- 7.3.1.Discretization errors -- 7.4.Runge-Kutta Methods -- 7.4.1.Second-order Runge-Kutta methods -- 7.4.2.Fourth-order Runge-Kutta methods -- 7.5.Systems of Differential Equations -- 7.6.Higher-Order Differential Equations -- III.Introduction to Optimization -- 8.Basic Concepts -- 8.1.Formulating an Optimization Problem -- 8.2.Mathematical Description -- 8.3.Local and Global Optimality -- 8.4.Existence of an Optimal Solution -- 8.5.Level Sets and Gradients -- 8.6.Convex Sets, Functions, and Problems -- 8.6.1.First-order characterization of a convex function -- 8.6.2.Second-order characterization of a convex function -- 9.Complexity Issues -- 9.1.Algorithms and Complexity -- 9.2.Average Running Time -- 9.3.Randomized Algorithms -- 9.4.Basics of Computational Complexity Theory -- 9.4.1.Class NP -- 9.4.2.P vs. NP -- 9.4.3.Polynomial time reducibility -- 9.4.4.NP-complete and NP-hard problems -- 9.5.Complexity of Local Optimization -- 9.6.Optimal Methods for Nonlinear Optimization -- 9.6.1.Classes of methods -- 9.6.2.Establishing lower complexity bounds for a class of methods -- 9.6.3.Defining an optimal method -- 10.Introduction to Linear Programming -- 10.1.Formulating a Linear Programming Model -- 10.1.1.Defining the decision variables -- 10.1.2.Formulating the objective function -- 10.1.3.Specifying the constraints -- 10.1.4.The complete linear programming formulation -- 10.2.Examples of LP Models -- 10.2.1.A diet problem -- 10.2.2.A resource allocation problem -- 10.2.3.A scheduling problem -- 10.2.4.A mixing problem -- 10.2.5.A transportation problem -- 10.2.6.A production planning problem -- 10.3.Practical Implications of Using LP Models -- 10.4.Solving Two-Variable LPs Graphically -- 10.5.Classification of LPs -- 11.The Simplex Method for Linear Programming -- 11.1.The Standard Form of LP -- 11.2.The Simplex Method -- 11.2.1.Step 1 -- 11.2.2.Step 2 -- 11.2.3.Recognizing optimality -- 11.2.4.Recognizing unbounded LPs -- 11.2.5.Degeneracy and cycling -- 11.2.6.Properties of LP dictionaries and the simplex method -- 11.3.Geometry of the Simplex Method -- 11.4.The Simplex Method for a General LP -- 11.4.1.The two-phase simplex method -- 11.4.2.The big-M method -- 11.5.The Fundamental Theorem of LP -- 11.6.The Revised Simplex Method -- 11.7.Complexity of the Simplex Method -- 12.Duality and Sensitivity Analysis in Linear Programming -- 12.1.Defining the Dual LP -- 12.1.1.Forming the dual of a general LP -- 12.2.Weak Duality and the Duality Theorem -- 12.3.Extracting an Optimal Solution of the Dual LP from an Optimal Tableau of the Primal LP -- 12.4.Correspondence between the Primal and Dual LP Types -- 12.5.Complementary Slackness -- 12.6.Economic Interpretation of the Dual LP -- 12.7.Sensitivity Analysis -- 12.7.1.Changing the objective function coefficient of a basic variable -- 12.7.2.Changing the objective function coefficient of a nonbasic variable -- 12.7.3.Changing the column of a nonbasic variable -- 12.7.4.Changing the right-hand side -- 12.7.5.Introducing a new variable -- 12.7.6.Introducing a new constraint -- 12.7.7.Summary -- 13.Unconstrained Optimization -- 13.1.Optimality Conditions -- 13.1.1.First-order necessary conditions -- 13.1.2.Second-order optimality conditions -- 13.1.3.Using optimality conditions for solving optimization problems -- 13.2.Optimization Problems with a Single Variable -- 13.2.1.Golden section search -- 13.2.1.1.Fibonacci search -- 13.3.Algorithmic Strategies for Unconstrained Optimization -- 13.4.Method of Steepest Descent -- 13.4.1.Convex quadratic case -- 13.4.2.Global convergence of the steepest descent method -- 13.5.Newton's Method -- 13.5.1.Rate of convergence -- 13.5.2.Guaranteeing the descent -- 13.5.3.Levenberg-Marquardt method -- 13.6.Conjugate Direction Method -- 13.6.1.Conjugate direction method for convex quadratic problems -- 13.6.2.Conjugate gradient algorithm -- 13.6.2.1.Non-quadratic problems -- 13.7.Quasi-Newton Methods -- 13.7.1.Rank-one correction formula -- 13.7.2.Other correction formulas -- 13.8.Inexact Line Search -- 14.Constrained Optimization -- 14.1.Optimality Conditions -- 14.1.1.First-order necessary conditions -- 14.1.1.1.Problems with equality constraints -- 14.1.1.2.Problems with inequality constraints -- 14.1.2.Second-order conditions -- 14.1.2.1.Problems with equality constraints -- 14.1.2.2.Problems with inequality constraints -- 14.2.Duality -- 14.3.Projected Gradient Methods -- 14.3.1.Affine scaling method for LP -- 14.4.Sequential Unconstrained Minimization -- 14.4.1.Penalty function methods -- 14.4.2.Barrier methods -- 14.4.3.Interior point methods.
- Subject(s):
- ISBN:
- 9781466577770 (Hardback)
1466577770 (Hardback) - Note:
- "A Chapman & Hall book."
- Bibliography Note:
- Includes bibliographical references (pages 389-390) and index.
View MARC record | catkey: 12559014