本书涵盖非线性规划的主要内容，包括无约束优化、凸优化、拉格朗日乘子理论和算法、对偶理论及方法等，包含了大量的实际应用案例. 本书从无约束优化问题入手，通过直观分析和严格证明给出了无约束优化问题的最优性条件，并讨论了梯度法、牛顿法、共轭方向法等基本实用算法. 进而本书将无约束优化问题的最优性条件和算法推广到具有凸集约束的优化问题中，进一步讨论了处理约束问题的可行方向法、条件梯度法、梯度投影法、双度量投影法、近似算法、流形次优化方法、坐标块下降法等. 拉格朗日乘子理论和算法是非线性规划的核心内容之一，也是本书的重点.

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 Nedi′c 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 Nedi′c; 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 book’s internet site

http://www.athenasc.com/nonlinbook.html

These exercises have been marked with the symbolsWWW. Many other exercises

contain detailed hints and/or references to internet-accessible sources.

The book’s 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 Nedi′c, Asuman Ozdaglar,

Paul Tseng, Mengdi Wang, and Huizhen (Janey) Yu.

Dimitri P. Bertsekas

June, 2016

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

本书为解决连续优化问题提供了全面而实用的方法。内容基于严格的数学分析，但尽量用可视化的方法来讲述。本书将重点放在最新的发展以及它们在很多领域的广泛的应用，例如大规模供给系统、信号处理和机器学习等。特色二：编写上主要采用“表达科普化、图表并茂”方式，强调“可操作性”，易学易用。图书出版与课程网站相辅相成，辅导读物和思考题在课程网站上体现。

本书为解决连续优化问题提供了全面而实用的方法。内容基于严格的数学分析，但尽量用可视化的方法来讲述。本书将重点放在最新的发展以及它们在很多领域的广泛的应用，例如大规模供给系统、信号处理和机器学习等。特色二：编写上主要采用“表达科普化、图表并茂”方式，强调“可操作性”，易学易用。图书出版与课程网站相辅相成，辅导读物和思考题在课程网站上体现。