非線性規劃（第3版）

基本信息

非線性規劃（第3版）

本書是控制、規劃與最佳化領域的一本經典教材，在學界影響很大。我社曾引進翻譯本書的第二版，現引進第三版，供大家參考學習。

作者：Dimitri P. Bertsekas
定價：169元
印次：1-1
ISBN：9787302482345
出版日期：2018.06.01
印刷日期：2018.04.17

內容簡介

本書涵蓋非線性規劃的主要內容，包括無約束最佳化、凸最佳化、拉格朗日乘子理論和算法、對偶理論及方法等，包含了大量的實際套用案例. 本書從無約束最佳化問題入手，通過直觀分析和嚴格證明給出了無約束最佳化問題的最優性條件，並討論了梯度法、牛頓法、共軛方向法等基本實用算法. 進而本書將無約束最佳化問題的最優性條件和算法推廣到具有凸集約束的最佳化問題中，進一步討論了處理約束問題的可行方向法、條件梯度法、梯度投影法、雙度量投影法、近似算法、流形次最佳化方法、坐標塊下降法等. 拉格朗日乘子理論和算法是非線性規劃的核心內容之一，也是本書的重點.

圖書目錄

Contents

1. Unconstrained Optimization: Basic Methods . . . . . . p. 1

1.1. OptimalityConditions . . . . . . . . . . . . . . . . . . . p. 5

1.1.1. Variational Ideas . . . . . . . . . . . . . . . . . . . . p. 5

1.1.2. MainOptimalityConditions . . . . . . . . . . . . . . . p. 15

1.2. GradientMethods –Convergence . . . . . . . . . . . . . . p. 28

1.2.1. DescentDirections and StepsizeRules . . . . . . . . . . p. 28

1.2.2. ConvergenceResults . . . . . . . . . . . . . . . . . . p. 49

1.3. GradientMethods –Rate ofConvergence . . . . . . . . . . p. 67

1.3.1. The LocalAnalysisApproach . . . . . . . . . . . . . . p. 69

1.3.2. TheRole of theConditionNumber . . . . . . . . . . . . p. 70

1.3.3.ConvergenceRateResults................p.82

1.4.Newton’sMethodandVariations..............p.95

1.4.1.ModifiedCholeskyFactorization............p.101

1.4.2.TrustRegionMethods................p.103

1.4.3.VariantsofNewton’sMethod.............p.105

1.4.4.LeastSquaresandtheGauss-NewtonMethod......p.107

1.5.NotesandSources...................p.117

2.UnconstrainedOptimization:AdditionalMethods..p.119

2.1.ConjugateDirectionMethods...............p.120

2.1.1.TheConjugateGradientMethod............p.125

2.1.2.ConvergenceRateofConjugateGradientMethod....p.132

2.2.Quasi-NewtonMethods.................p.138

2.3.NonderivativeMethods.................p.148

2.3.1.CoordinateDescent.................p.149

2.3.2.DirectSearchMethods................p.154

2.4.IncrementalMethods..................p.158

2.4.1.IncrementalGradientMethods.............p.161

2.4.2.IncrementalAggregatedGradientMethods.......p.172

2.4.3.IncrementalGauss-NewtonMethods..........p.178

2.4.3.IncrementalNewtonMethods.............p.185

2.5.DistributedAsynchronousAlgorithms...........p.194

v

viContents

2.5.1.TotallyandPartiallyAsynchronousAlgorithms.....p.197

2.5.2.TotallyAsynchronousConvergence...........p.198

2.5.3.PartiallyAsynchronousGradient-LikeAlgorithms....p.203

2.5.4.ConvergenceRateofAsynchronousAlgorithms.....p.204

2.6.Discrete-TimeOptimalControlProblems.........p.210

2.6.1.GradientandConjugateGradientMethodsfor........

OptimalControl...................p.221

2.6.2.Newton’sMethodforOptimalControl.........p.222

2.7.SolvingNonlinearProgrammingProblems-Some........

PracticalGuidelines...................p.227

2.8.NotesandSources...................p.232

3.OptimizationOveraConvexSet..........p.235

3.1.ConstrainedOptimizationProblems............p.236

3.1.1.NecessaryandSufficientConditionsforOptimality....p.236

3.1.2.ExistenceofOptimalSolutions............p.246

3.2.FeasibleDirections-ConditionalGradientMethod.....p.257

3.2.1.DescentDirectionsandStepsizeRules.........p.257

3.2.2.TheConditionalGradientMethod...........p.262

3.3.GradientProjectionMethods...............p.272

3.3.1.FeasibleDirectionsandStepsizeRulesBasedon........

Projection.....................p.272

3.3.2.ConvergenceAnalysis.................p.283

3.4.Two-MetricProjectionMethods.............p.292

3.5.ManifoldSuboptimizationMethods............p.298

3.6.ProximalAlgorithms..................p.307

3.6.1.RateofConvergence.................p.312

3.6.2.VariantsoftheProximalAlgorithm..........p.318

3.7.BlockCoordinateDescentMethods............p.323

3.7.1.VariantsofCoordinateDescent............p.327

3.8.NetworkOptimizationAlgorithms.............p.331

3.9.NotesandSources...................p.338

4.LagrangeMultiplierTheory............p.343

4.1.NecessaryConditionsforEqualityConstraints.......p.345

4.1.1.ThePenaltyApproach................p.349

4.1.2.TheEliminationApproach..............p.352

4.1.3.TheLagrangianFunction...............p.356

4.2.SufficientConditionsandSensitivityAnalysis........p.364

4.2.1.TheAugmentedLagrangianApproach.........p.365

4.2.2.TheFeasibleDirectionApproach............p.369

4.2.3.Sensitivity..........p.370

4.3.InequalityConstraints.......p.376

4.3.1.Karush-Kuhn-TuckerNecessaryConditions.......p.378

Contentsvii

4.3.2.SufficientConditionsandSensitivity..........p.383

4.3.3.FritzJohnOptimalityConditions...........p.386

4.3.4.ConstraintQualificationsandPseudonormality.....p.392

4.3.5.AbstractSetConstraintsandtheTangentCone.....p.399

4.3.6.AbstractSetConstraints,Equality,andInequality.......

Constraints..........p.415

4.4.LinearConstraintsandDuality......p.429

4.4.1.ConvexCostFunctionandLinearConstraints......p.429

4.4.2.DualityTheory:ASimpleFormforLinear..........

Constraints..........p.432

4.5.NotesandSources........p.441

5.LagrangeMultiplierAlgorithms..........p.445

5.1.BarrierandInteriorPointMethods............p.446

5.1.1.PathFollowingMethodsforLinearProgramming....p.450

5.1.2.Primal-DualMethodsforLinearProgramming......p.458

5.2.PenaltyandAugmentedLagrangianMethods........p.469

5.2.1.TheQuadraticPenaltyFunctionMethod........p.471

5.2.2.MultiplierMethods–MainIdeas............p.479

5.2.3.ConvergenceAnalysisofMultiplierMethods.......p.488

5.2.4.DualityandSecondOrderMultiplierMethods......p.492

5.2.5.NonquadraticAugmentedLagrangians-TheExponential...

MethodofMultipliers.....p.494

5.3.ExactPenalties–SequentialQuadraticProgramming....p.502

5.3.1.NondifferentiableExactPenaltyFunctions.......p.503

5.3.2.SequentialQuadraticProgramming..........p.513

5.3.3.DifferentiableExactPenaltyFunctions.........p.520

5.4.LagrangianMethods.......p.527

5.4.1.First-OrderLagrangianMethods............p.528

5.4.2.Newton-LikeMethodsforEqualityConstraints.....p.535

5.4.3.GlobalConvergence......p.545

5.4.4.AComparisonofVariousMethods...........p.548

5.5.NotesandSources........p.550

6.DualityandConvexProgramming.........p.553

6.1.DualityandDualProblems.......p.554

6.1.1.GeometricMultipliers.....p.556

6.1.2.TheWeakDualityTheorem......p.561

6.1.3.PrimalandDualOptimalSolutions..........p.566

6.1.4.TreatmentofEqualityConstraints...........p.568

6.1.5.SeparableProblemsandtheirGeometry........p.570

6.1.6.AdditionalIssuesAboutDuality............p.575

6.2.ConvexCost–LinearConstraints.....p.582

6.3.ConvexCost–ConvexConstraints............p.589

viiiContents

6.4.ConjugateFunctionsandFenchelDuality.........p.598

6.4.1.ConicProgramming......p.604

6.4.2.MonotropicProgramming.......p.612

6.4.3.NetworkOptimization.....p.617

6.4.4.GamesandtheMinimaxTheorem...........p.620

6.4.5.ThePrimalFunctionandSensitivityAnalysis......p.623

6.5.DiscreteOptimizationandDuality............p.630

6.5.1.ExamplesofDiscreteOptimizationProblems......p.631

6.5.2.Branch-and-Bound.......p.639

6.5.3.LagrangianRelaxation.....p.648

6.6.NotesandSources........p.660

7.DualMethods.......p.663

7.1.DualDerivativesandSubgradients............p.666

7.2.DualAscentMethodsforDifferentiableDualProblems...p.673

7.2.1.CoordinateAscentforQuadraticProgramming.....p.673

7.2.2.SeparableProblemsandPrimalStrictConvexity.....p.675

7.2.3.PartitioningandDualStrictConcavity.........p.677

7.3.ProximalandAugmentedLagrangianMethods.......p.682

7.3.1.TheMethodofMultipliersasaDual.....

ProximalAlgorithm......p.682

7.3.2.EntropyMinimizationandExponential...........

MethodofMultipliers.....p.686

7.3.3.IncrementalAugmentedLagrangianMethods......p.687

7.4.AlternatingDirectionMethodsofMultipliers........p.691

7.4.1.ADMMAppliedtoSeparableProblems.........p.699

7.4.2.ConnectionsBetweenAugmentedLagrangian-........

RelatedMethods........p.703

7.5.Subgradient-BasedOptimizationMethods.........p.709

7.5.1.SubgradientMethods......p.709

7.5.2.ApproximateandIncrementalSubgradientMethods...p.714

7.5.3.CuttingPlaneMethods.....p.717

7.5.4.AscentandApproximateAscentMethods........p.724

7.6.DecompositionMethods......p.735

7.6.1.LagrangianRelaxationoftheCouplingConstraints....p.736

7.6.2.DecompositionbyRight-HandSideAllocation......p.739

7.7.NotesandSources........p.742

AppendixA:MathematicalBackground........p.745

A.1.VectorsandMatrices.......p.746

A.2.Norms,Sequences,Limits,andContinuity.........p.749

A.3.SquareMatricesandEigenvalues.....p.757

A.4.SymmetricandPositiveDefiniteMatrices.........p.760

A.5.Derivatives.....p.765

Contentsix

A.6.ConvergenceTheorems......p.770

AppendixB:ConvexAnalysis............p.783

B.1.ConvexSetsandFunctions.......p.783

B.2.Hyperplanes.....p.793

B.3.ConesandPolyhedralConvexity.....p.796

B.4.ExtremePointsandLinearProgramming.........p.798

B.5.DifferentiabilityIssues.......p.803

AppendixC:LineSearchMethods..........p.809

C.1.CubicInterpolation........p.809

C.2.QuadraticInterpolation......p.810

C.3.TheGoldenSectionMethod.......p.812

AppendixD:ImplementationofNewton’sMethod...p.815

D.1.CholeskyFactorization......p.815

D.2.ApplicationtoaModifiedNewtonMethod.........p.817

References.........p.821

Index......p.857