新書推薦：
《
鸟类图典
》
售價：HK$
43.8
《
古典与文明·《周官》之制与大一统
》
售價：HK$
86.9
《
海外中国研究·朝贡·海禁·互市：近世东亚的贸易与秩序（一部刷新明清外交与通商认知的典范之作。挑战朝贡
》
售價：HK$
107.8
《
财报防坑指南：20分钟看透企业真实现金流与盈利陷阱
》
售價：HK$
76.8
《
安逸哲学：锦绣天府人生智慧“安逸四川”三部曲第一部 安逸是中华文明为世界贡献的人生智慧
》
售價：HK$
96.8
《
风月狩（全二册）
》
售價：HK$
71.5
《
大学问·改过自新：清代以来自首制度的表达与实践（以丰富案例生动还原清代以来自首制度在基层的运行图景，
》
售價：HK$
74.8
《
DK照亮未知的灯塔
》
售價：HK$
74.8
|
| 編輯推薦： |
|
本书为解决连续优化问题提供了全面而实用的方法。内容基于严格的数学分析，但尽量用可视化的方法来讲述。本书将重点放在*的发展以及它们在很多领域的广泛的应用，例如大规模供给系统、信号处理和机器学习等。
|
| 內容簡介： |
|
本书涵盖非线性规划的主要内容，包括无约束优化、凸优化、拉格朗日乘子理论和算法、对偶理论及方法等，包含了大量的实际应用案例. 本书从无约束优化问题入手，通过直观分析和严格证明给出了无约束优化问题的*性条件，并讨论了梯度法、牛顿法、共轭方向法等基本实用算法. 进而本书将无约束优化问题的*性条件和算法推广到具有凸集约束的优化问题中，进一步讨论了处理约束问题的可行方向法、条件梯度法、梯度投影法、双度量投影法、近似算法、流形次优化方法、坐标块下降法等. 拉格朗日乘子理论和算法是非线性规划的核心内容之一，也是本书的重点.
|
| 目錄：
|
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. NewtonsMethod andVariations . . . . .
. . . . . . . . . p. 95
1.4.1. ModifiedCholeskyFactorization . . .
. . . . . . . . . p. 101
1.4.2. TrustRegionMethods . . . . . . . . .
. . . . . . . p. 103
1.4.3. Variants ofNewtonsMethod . . . . .
. . . . . . . . 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. NewtonsMethod 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 Newtons
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. These
developments were documented in three
of my books： the 2015 book Convex
Optimization Algorithms, the 2009
book Convex Optimization Theory, and the
2003 book Convex Analysis
and Optimization coauthored
with Angelia Nedic and Asuman Ozdaglar.
A major difference is that these books have
dealt primarily with convex, possibly
nondifferentiable, optimization problems
and rely on convex analysis,
while the present book focuses primarily on
algorithms for possibly nonconvex
differentiable problems, and relies on
calculus and variational analysis.
Having written several interrelated
optimization books, I have come to
see nonlinear programming and its
associated duality theory as the lynchpin
that holds together deterministic
optimization. I have consequently set as an
objective for the present book to integrate
the contents of my books, together
with internet-accessible material, so that
they complement each other and
form a unified whole. I have thus provided
bridges to my other works with
extensive references to generalizations,
discussions, and elaborations of the
analysis given here, and I have used
throughout fairly consistent notation and
mathematical level.
Another connecting link of my books is that
they all share the same style：
they rely on rigorous analysis, but they
also aim at an intuitive exposition that
makes use of geometric visualization. This
stems from my belief that success
in the practice of optimization strongly
depends on the intuitive as well as
the analytical understanding of the
underlying theory and algorithms.
Some of the more prominent new features of
the present edition are：
a An expanded coverage of incremental
methods and their connections to
stochastic gradient methods, based in part
on my 2000 joint work with
Angelia Nedic; see Section 2.4
and Section 7.3.2.
b A discussion of asynchronous
distributed algorithms based in large part
on my 1989 Parallel and Distributed
Computation book coauthored
xvii
xviii Preface to the Third Edition
with John Tsitsiklis; see Section 2.5.
c A discussion of the proximal algorithm
and its variations in Section 3.6,
and the relation with the method of
multipliers in Section 7.3.
d A substantial coverage of the
alternating direction method of multipliers
ADMM in Section 7.4, with a discussion of
its many applications and
variations, as well as references to my
1989 Parallel and Distributed
Computation and 2015 Convex Optimization
Algorithms books.
e A fairly detailed treatment of conic
programming problems in Section
6.4.1.
f A discussion of the question of
existence of solutions in constrained optimization,
based on my 2007 joint work with Paul Tseng
[BeT07], which
contains further analysis; see Section
3.1.2.
g Additional material on network flow
problems in Section 3.8 and 6.4.3,
and their extensions to monotropic
programming in Section 6.4.2, with
references to my 1998 Network
Optimization book.
h An expansion of the material of Chapter
4 on Lagrangemultiplier theory,
using a strengthened version of the Fritz
John conditions, and the notion
of pseudonormality, based on my 2002 joint
work with Asuman Ozdaglar.
i An expansion of the material of Chapter
5 on Lagrange multiplier algorithms,
with references to my 1982 Constrained
Optimization and
Lagrange Multiplier Methods book.
The book contains a few new exercises. As
in the second edition, many
of the theoretical exercises have been
solved in detail and their solutions have
been posted in the books internet site
http：www.athenasc.comnonlinbook.html
These exercises have been marked with the
symbolsWWW. Many other exercises
contain detailed hints andor references to
internet-accessible sources.
The books internet site also contains
links to additional resources, such as
many additional solved exercises from my
convex optimization books, computer
codes, my lecture slides from MIT Nonlinear
Programming classes, and
full course contents from the MIT
OpenCourseWare OCW site.
I would like to express my thanks to the
many colleagues who contributed
suggestions for improvement of the third
edition. In particular, let
me note with appreciation my principal
collaborators on nonlinear programming
topics since the 1999 second edition：
Angelia Nedic, Asuman Ozdaglar,
Paul Tseng, Mengdi Wang, and Huizhen
Janey Yu.
Dimitri P. Bertsekas
June, 2016
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
