·ÇÏßÐԹ滮(µÚ3°æ)/DIMITRI P.BERTSEKAS

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