內容簡介

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

作者介紹

Dimitri P.Bertsekas，美國工程院院士，IEEE會士。1971年獲MIT電子工程博士學位。長期在MIT執教，曾獲得2001年度美國控制協會J.Ragazzini教育獎。其研究領域涉及優化、控制、大規模計算、資料通信網路等，許多研究具有開創性貢獻。著有Nonlinear Programming等十餘部教材和專著，其中許多被MIT等名校用作研究生或本科生教材。

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’sMethod andVariations . . . . . . . . . . . . . . p. 95
1.4.1. ModifiedCholeskyFactorization . . . . . . . . . . . . p. 101
1.4.2. TrustRegionMethods . . . . . . . . . . . . . . . . p. 103
1.4.3. Variants ofNewton’sMethod . . . . . . . . . . . . . p. 105
1.4.4. Least Squares and theGauss-NewtonMethod . . . . . . p. 107
1.5. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 117
2. Unconstrained Optimization: Additional Methods . . p. 119
2.1. ConjugateDirectionMethods . . . . . . . . . . . . . . . p. 120
2.1.1. TheConjugateGradientMethod . . . . . . . . . . . . p. 125
2.1.2. ConvergenceRate ofConjugateGradientMethod . . . . p. 132
2.2. Quasi-NewtonMethods . . . . . . . . . . . . . . . . . p. 138
2.3. NonderivativeMethods . . . . . . . . . . . . . . . . . p. 148
2.3.1. CoordinateDescent . . . . . . . . . . . . . . . . . p. 149
2.3.2. Direct SearchMethods . . . . . . . . . . . . . . . . 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
vi Contents
2.5.1. Totally andPartiallyAsynchronousAlgorithms . . . . . p. 197
2.5.2. TotallyAsynchronousConvergence . . . . . . . . . . . p. 198
2.5.3. PartiallyAsynchronousGradient-LikeAlgorithms . . . . p. 203
2.5.4. ConvergenceRate ofAsynchronousAlgorithms . . . . . p. 204
2.6. Discrete-TimeOptimalControlProblems . . . . . . . . . p. 210
2.6.1. Gradient andConjugateGradientMethods for . . . . . . . .
OptimalControl . . . . . . . . . . . . . . . . . . . p. 221
2.6.2. Newton’sMethod forOptimalControl . . . . . . . . . p. 222
2.7. SolvingNonlinearProgrammingProblems - Some . . . . . . . .
PracticalGuidelines . . . . . . . . . . . . . . . . . . . p. 227
2.8. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 232
3. Optimization Over a Convex Set . . . . . . . . . . p. 235
3.1. ConstrainedOptimizationProblems . . . . . . . . . . . . p. 236
3.1.1. Necessary and SufficientConditions forOptimality . . . . p. 236
3.1.2. Existence ofOptimal Solutions . . . . . . . . . . . . p. 246
3.2. FeasibleDirections -ConditionalGradientMethod . . . . . p. 257
3.2.1. DescentDirections and StepsizeRules . . . . . . . . . p. 257
3.2.2. TheConditionalGradientMethod . . . . . . . . . . . p. 262
3.3. GradientProjectionMethods . . . . . . . . . . . . . . . p. 272
3.3.1. FeasibleDirections and StepsizeRulesBasedon . . . . . . . .
Projection . . . . . . . . . . . . . . . . . . . . . p. 272
3.3.2. ConvergenceAnalysis . . . . . . . . . . . . . . . . . p. 283
3.4. Two-MetricProjectionMethods . . . . . . . . . . . . . p. 292
3.5. Manifold SuboptimizationMethods . . . . . . . . . . . . p. 298
3.6. ProximalAlgorithms . . . . . . . . . . . . . . . . . . p. 307
3.6.1. Rate ofConvergence . . . . . . . . . . . . . . . . . p. 312
3.6.2. Variants of theProximalAlgorithm . . . . . . . . . . p. 318
3.7. BlockCoordinateDescentMethods . . . . . . . . . . . . p. 323
3.7.1. Variants ofCoordinateDescent . . . . . . . . . . . . p. 327
3.8. NetworkOptimizationAlgorithms . . . . . . . . . . . . . p. 331
3.9. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 338
4. LagrangeMultiplierTheory . . . . . . . . . . . . p. 343
4.1. NecessaryConditions forEqualityConstraints . . . . . . . p. 345
4.1.1. ThePenaltyApproach . . . . . . . . . . . . . . . . p. 349
4.1.2. TheEliminationApproach . . . . . . . . . . . . . . p. 352
4.1.3. The LagrangianFunction . . . . . . . . . . . . . . . p. 356
4.2. SufficientConditions and SensitivityAnalysis . . . . . . . . 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-Tucker Necessary Conditions . . . . . . . p. 378
Contents vii
4.3.2. SufficientConditions and Sensitivity . . . . . . . . . . p. 383
4.3.3. Fritz JohnOptimalityConditions . . . . . . . . . . . p. 386
4.3.4. ConstraintQualifications andPseudonormality . . . . . p. 392
4.3.5. Abstract SetConstraints and theTangentCone . . . . . p. 399
4.3.6. Abstract SetConstraints,Equality, and Inequality . . . . . . .
Constraints . . . . . . . . . . . . . . . . . . . . . p. 415
4.4. LinearConstraints andDuality . . . . . . . . . . . . . . p. 429
4.4.1. ConvexCostFunction andLinearConstraints . . . . . . p. 429
4.4.2. DualityTheory: ASimpleFormforLinear . . . . . . . . . .
Constraints . . . . . . . . . . . . . . . . . . . . . p. 432
4.5. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 441
5. Lagrange Multiplier Algorithms . . . . . . . . . . p. 445
5.1. Barrier and InteriorPointMethods . . . . . . . . . . . . p. 446
5.1.1. PathFollowingMethods forLinearProgramming . . . . p. 450
5.1.2. Primal-DualMethods forLinearProgramming . . . . . . p. 458
5.2. Penalty andAugmentedLagrangianMethods . . . . . . . . p. 469
5.2.1. TheQuadraticPenaltyFunctionMethod . . . . . . . . p. 471
5.2.2. MultiplierMethods –Main Ideas . . . . . . . . . . . . p. 479
5.2.3. ConvergenceAnalysis ofMultiplierMethods . . . . . . . p. 488
5.2.4. Duality and SecondOrderMultiplierMethods . . . . . . p. 492
5.2.5. Nonquadratic Augmented Lagrangians - The Exponential . . .
Method ofMultipliers . . . . . . . . . . . . . . . . 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-LikeMethods forEqualityConstraints . . . . . p. 535
5.4.3. GlobalConvergence . . . . . . . . . . . . . . . . . p. 545
5.4.4. AComparisonofVariousMethods . . . . . . . . . . . p. 548
5.5. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 550
6. Duality andConvexProgramming . . . . . . . . . p. 553
6.1. Duality andDualProblems . . . . . . . . . . . . . . . p. 554
6.1.1. GeometricMultipliers . . . . . . . . . . . . . . . . p. 556
6.1.2. TheWeakDualityTheorem . . . . . . . . . . . . . . p. 561
6.1.3. Primal andDualOptimal Solutions . . . . . . . . . . p. 566
6.1.4. Treatment ofEqualityConstraints . . . . . . . . . . . p. 568
6.1.5. SeparableProblems and theirGeometry . . . . . . . . p. 570
6.1.6. Additional IssuesAboutDuality . . . . . . . . . . . . p. 575
6.2. ConvexCost –LinearConstraints . . . . . . . . . . . . . p. 582
6.3. ConvexCost –ConvexConstraints . . . . . . . . . . . . p. 589
viii Contents
6.4. ConjugateFunctions andFenchelDuality . . . . . . . . . p. 598
6.4.1. ConicProgramming . . . . . . . . . . . . . . . . . p. 604
6.4.2. MonotropicProgramming . . . . . . . . . . . . . . . p. 612
6.4.3. NetworkOptimization . . . . . . . . . . . . . . . . p. 617
6.4.4. Games and theMinimaxTheorem . . . . . . . . . . . p. 620
6.4.5. ThePrimalFunction and SensitivityAnalysis . . . . . . p. 623
6.5. DiscreteOptimization andDuality . . . . . . . . . . . . p. 630
6.5.1. Examples ofDiscreteOptimizationProblems . . . . . . p. 631
6.5.2. Branch-and-Bound . . . . . . . . . . . . . . . . . . p. 639
6.5.3. LagrangianRelaxation . . . . . . . . . . . . . . . . p. 648
6.6. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 660
7. DualMethods . . . . . . . . . . . . . . . . . . p. 663
7.1. Dual Derivatives and Subgradients . . . . . . . . . . . . p. 666
7.2. Dual Ascent Methods for Differentiable Dual Problems . . . p. 673
7.2.1. CoordinateAscent forQuadraticProgramming . . . . . p. 673
7.2.2. SeparableProblems andPrimalStrictConvexity . . . . . p. 675
7.2.3. Partitioning andDual StrictConcavity . . . . . . . . . p. 677
7.3. Proximal andAugmentedLagrangianMethods . . . . . . . p. 682
7.3.1. TheMethod ofMultipliers as aDual . . . . . . . . . . . . .
ProximalAlgorithm . . . . . . . . . . . . . . . . . p. 682
7.3.2. EntropyMinimization andExponential . . . . . . . . . . .
Method ofMultipliers . . . . . . . . . . . . . . . . p. 686
7.3.3. IncrementalAugmentedLagrangianMethods . . . . . . p. 687
7.4. AlternatingDirectionMethods ofMultipliers . . . . . . . . p. 691
7.4.1. ADMMApplied to SeparableProblems . . . . . . . . . p. 699
7.4.2. ConnectionsBetweenAugmentedLagrangian- . . . . . . . .
RelatedMethods . . . . . . . . . . . . . . . . . . . p. 703
7.5. Subgradient-Based Optimization Methods . . . . . . . . . p. 709
7.5.1. Subgradient Methods . . . . . . . . . . . . . . . . . p. 709
7.5.2. Approximate and Incremental Subgradient Methods . . . p. 714
7.5.3. Cutting PlaneMethods . . . . . . . . . . . . . . . . p. 717
7.5.4. Ascent andApproximateAscentMethods . . . . . . . . p. 724
7.6. DecompositionMethods . . . . . . . . . . . . . . . . . p. 735
7.6.1. LagrangianRelaxation of theCouplingConstraints . . . . p. 736
7.6.2. Decomposition byRight-Hand SideAllocation . . . . . . p. 739
7.7. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 742
Appendix A: Mathematical Background . . . . . . . . p. 745
A.1. Vectors andMatrices . . . . . . . . . . . . . . . . . . p. 746
A.2. Norms, Sequences,Limits, andContinuity . . . . . . . . . p. 749
A.3. SquareMatrices andEigenvalues . . . . . . . . . . . . . p. 757
A.4. Symmetric andPositiveDefiniteMatrices . . . . . . . . . p. 760
A.5. Derivatives . . . . . . . . . . . . . . . . . . . . . . p. 765
Contents ix
A.6. ConvergenceTheorems . . . . . . . . . . . . . . . . . p. 770
AppendixB:ConvexAnalysis . . . . . . . . . . . . p. 783
B.1. Convex Sets andFunctions . . . . . . . . . . . . . . . p. 783
B.2. Hyperplanes . . . . . . . . . . . . . . . . . . . . . . p. 793
B.3. Cones andPolyhedralConvexity . . . . . . . . . . . . . p. 796
B.4. ExtremePoints andLinearProgramming . . . . . . . . . p. 798
B.5. Differentiability Issues . . . . . . . . . . . . . . . . . . p. 803
Appendix C: Line Search Methods . . . . . . . . . . p. 809
C.1. Cubic Interpolation . . . . . . . . . . . . . . . . . . . p. 809
C.2. Quadratic Interpolation . . . . . . . . . . . . . . . . . p. 810
C.3. TheGolden SectionMethod . . . . . . . . . . . . . . . p. 812
Appendix D: Implementation of Newton’s Method . . . p. 815
D.1. CholeskyFactorization . . . . . . . . . . . . . . . . . p. 815
D.2. Application to aModifiedNewtonMethod . . . . . . . . . p. 817
References . . . . . . . . . . . . . . . . . . . . p. 821
Index . . . . . . . . . . . . . . . . . . . . . . . p. 857

看更多

序

Preface to the Third Edition
The third edition of the book is a thoroughly rewritten version of the 1999 second edition. New material was included, some of the old material was discarded, and a large portion of the remainder was reorganized or revised.
The total number of pages has increased by about 10 percent.
Aside from incremental improvements, the changes aim to bring the book up-to-date with recent research progress, and in harmony with the major developments in convex optimization theory and algorithms that have occurred in the meantime.

看更多