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