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