基本介紹
- 中文名：非線性規劃（第3版）
- 作者：Dimitri P. Bertsekas
- 出版社：清華大學出版社
- 出版時間：2018年6月1日
- 定價：169 元
- ISBN：9787302482345
內容簡介,圖書目錄,
內容簡介
本書涵蓋非線性規劃的主要內容，包括無約束最佳化、凸最佳化、拉格朗日乘子理論和算法、對偶理論及方法等，包含了大量的實際套用案例. 本書從無約束最佳化問題入手，通過直觀分析和嚴格證明給出了無約束最佳化問題的最優性條件，並討論了梯度法、牛頓法、共軛方向法等基本實用算法. 進而本書將無約束最佳化問題的最優性條件和算法推廣到具有凸集約束的最佳化問題中，進一步討論了處理約束問題的可行方向法、條件梯度法、梯度投影法、雙度量投影法、近似算法、流形次最佳化方法、坐標塊下降法等. 拉格朗日乘子理論和算法是非線性規劃的核心內容之一，也是本書的重點.
圖書目錄
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
