Numerical nonsmooth optimization

✍ Scribed by Bagirov A.M (ed.)

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 696
• Category: Library

✦ Table of Contents

Preface......Page 5
Contents......Page 8
Contributors......Page 10
Acronyms and Symbols......Page 13
1 Introduction......Page 16
1.1 Notations......Page 17
1.2 Definitions and Basic Results......Page 18
1.3 Nonsmooth vs. Smooth Optimization......Page 21
1.4 Subgradient Methods......Page 25
1.5 Bundle Methods......Page 28
1.6 Forthcoming Chapters......Page 31
Part I General Methods......Page 32
2 Advances in Low-Memory Subgradient Optimization......Page 33
2.1 Introduction......Page 34
2.2 Example Application: Transportation Problem and First Subgradient Algorithm......Page 36
2.3 Complexity Results for Convex Optimization......Page 41
2.4.1 Nesterov Smoothing......Page 48
2.4.2 Nemirovski Mirror Prox......Page 51
2.5 NSO in Large Dimensions......Page 53
2.5.1 Convex Nonsmooth Objective Function......Page 55
2.5.2 General Convex and Quasiconvex Objectives......Page 59
2.6 Universal Methods......Page 61
2.7 Concluding Remarks......Page 68
References......Page 69
3.1 Introduction......Page 74
3.2.1 Trust-Region Stabilization......Page 79
3.2.2 Proximal Stabilization......Page 83
3.2.3 Level Stabilization......Page 86
3.2.4 Center-Based Approaches......Page 88
3.2.5 Approximate CPM Approaches......Page 91
3.3.1 Dual Forms of the Master Problem......Page 93
3.3.2 Algorithmic Uses of Duality......Page 97
3.3.3 Duality in the Original Problem......Page 100
3.3.4 Generalized Stabilization......Page 104
3.4.1 Quadratic Models......Page 108
3.4.2 Disaggregate Models......Page 110
3.4.3 Constraints and Easy Components......Page 113
3.4.4 Specialized Dynamic Models......Page 116
3.4.5 Diminishing the MP Cost......Page 118
3.5 Inexact and Incremental Approaches......Page 119
3.5.1 Inexact Approaches......Page 120
3.5.2 Incremental Approaches......Page 122
3.6 Conclusion......Page 124
References......Page 125
4.1 Introduction......Page 130
4.2.1 Smooth Optimality Conditions and SQP......Page 134
4.2.2 Nonsmooth Optimality Conditions......Page 135
4.3 Derivation of the Method......Page 136
4.3.1 Theoretical Basics......Page 137
4.3.2 The Bundle Algorithm......Page 142
4.3.3 The Line Search......Page 151
4.4.1 Convergence of the Line Search......Page 156
4.4.2 Global Convergence......Page 157
References......Page 175
5.1 Introduction......Page 179
5.2 Limited Memory Bundle Method......Page 181
5.3 Diagonal Bundle Method......Page 194
5.4 Splitting Metrics Diagonal Bundle Method......Page 198
5.5 Numerical Experiments and Discussion......Page 205
Appendix......Page 208
References......Page 210
6 Gradient Sampling Methods for Nonsmooth Optimization......Page 212
6.1 Introduction......Page 213
6.2 Algorithm GS......Page 214
6.3.1 Global Convergence Guarantees......Page 218
6.3.2 A Local Linear Convergence Result......Page 220
6.3.3 The Non-Lipschitz Case......Page 221
6.4.2 Avoiding the Differentiability Check......Page 222
6.4.3 Adaptive Sampling......Page 224
6.4.4 Second Order-Type Variants......Page 225
6.5.2 SQP-GS for Constrained Optimization......Page 226
6.5.3 Derivative-Free Optimization......Page 227
6.6 Applications......Page 228
6.7 Conclusion and Future Directions......Page 229
Appendix 1......Page 231
References......Page 234
Part II Structure Exploiting Methods......Page 237
7.1 Introduction......Page 238
7.3 The Penalized Problem......Page 241
7.4 Local Search Method......Page 243
7.5 Convergence Properties of Scheme 1......Page 247
7.6 Exact Penalty and Lagrange Multipliers......Page 256
7.7 About Stopping Criteria......Page 264
7.8 Conclusion......Page 267
References......Page 268
8.1 Introduction......Page 271
8.2 Optimality Conditions in DC Optimization......Page 272
8.3 Convex Cutting Plane Model of a DC Component......Page 277
8.4 Proximal Bundle Method PBDC......Page 278
8.5 Double Bundle Method DBDC......Page 289
8.6 Piecewise Concave Bundle Method DCPCA......Page 298
8.7 Numerical Results......Page 299
References......Page 302
9.1 Introduction......Page 305
9.2 Linear Convergence of Proximal Bundle Methods......Page 307
9.3 Introduction of VU-Analysis......Page 313
9.4 A Conceptual VU-Algorithm......Page 319
9.5.1 Replacing the V-Step by a Prox-Step......Page 322
9.5.2 A Quasi-Newton U-Step......Page 325
9.6 An Implementable Algorithm with Exact Prox-Calculation......Page 327
9.7.1 Calculating Uk......Page 330
9.7.2 Incorporating a Bundle Routine......Page 332
References......Page 335
10.1 Motivation and Introduction......Page 338
10.2 The Oracle and Piecewise Differentiation......Page 339
10.3 Abs-Normal Objectives......Page 344
10.4 The Abs-Linear Approximation......Page 347
10.5 Checking Gradient Activity......Page 349
10.6 Checking Criticality and Second Order Optimality......Page 355
10.7 Demonstration on Crescent......Page 358
10.8 Covering the Euclidean Norm......Page 361
References......Page 366
11.1 Generalized Minimax Problems......Page 369
11.2.1 Barriers and Barrier Functions......Page 375
11.2.2 Iterative Determination of a Minimax Vector......Page 377
11.2.3 Direct Determination of a Minimax Vector......Page 380
11.2.4 Implementation......Page 384
11.2.5 Global Convergence......Page 386
11.2.6 Special Cases......Page 392
11.3.1 Basic Properties......Page 396
11.3.2 Global Convergence......Page 400
11.3.3 Special Cases......Page 404
11.4.1 Basic Properties......Page 406
11.4.2 Implementation......Page 411
11.5 Numerical Experiments......Page 412
Appendix......Page 416
References......Page 419
Part III Methods for Special Problems......Page 421
12.1 Introduction......Page 422
12.2 Inexact Oracles: The Main Assumptions and Examples......Page 424
12.2.1 Examples of Inexact Oracles......Page 425
12.3.1 Models, Localizer Sets, and Optimality Certificate......Page 429
12.3.2 An Algorithmic Pattern......Page 431
12.3.3.1 The Combinatorial Setting......Page 432
12.3.3.3 The Convex Setting......Page 433
12.3.4 Handling Oracles with On-Demand Accuracy......Page 435
12.4 Inexact Proximal Bundle Methods......Page 437
12.4.1 Descent Test and Optimality Certificate......Page 438
12.4.2 Inexact Proximal Bundle Algorithm......Page 440
12.4.3 Convergence Analysis......Page 441
12.4.4.2 Incremental Proximal Bundle Method......Page 443
12.4.4.3 Nonlinearly Constrained Problems......Page 446
12.5 Doubly stabilized bundle method (DSBM)......Page 447
12.5.1 Optimality Certificate and More......Page 449
12.5.2 Doubly Stabilized Bundle Algorithm......Page 450
12.5.3 Convergence Analysis......Page 452
12.6 Nonconvex Objective Functions......Page 453
12.6.1 Some Examples of Inexact Nonconvex Oracles......Page 454
12.6.2 Models: Handling Nonconvexity and Inexactness......Page 455
12.6.3 Key Relations and the Stationarity Certificate......Page 456
12.6.4 Inexact Nonconvex Proximal Bundle Algorithm......Page 458
12.7 Concluding Remarks and Research Perspectives......Page 459
References......Page 461
13.1 Introduction......Page 465
13.2 Preliminaries......Page 467
13.3 Scaled Improvement Function......Page 470
13.4 Multiobjective Proximal Bundle Method......Page 474
13.5 Convergence Analysis......Page 477
13.6 Numerical Examples......Page 479
References......Page 481
14.1 Introduction to Multiobjective DC Optimization......Page 484
14.2 Critical Versus Stationary Solution in Multiobjective DC Optimization......Page 486
14.3 Multiobjective Double Bundle Method for DC Optimization......Page 489
14.4 Numerical Behaviour of MDBDC......Page 496
References......Page 498
15 Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods......Page 501
15.1 Introduction and Motivation......Page 502
15.2 Mixed-Binary Linear Optimization and Its Convexified Counterpart......Page 503
15.2.1 The Lagrangian Dual......Page 505
15.2.2 Optimality Conditions for the Convexified Problem......Page 507
15.2.3 Conditions for Optimality and Near Optimality of Mixed-Binary Linear Optimization Problems......Page 509
15.3.1 Basic Convergence in the Lagrangian Dual Problem......Page 513
15.3.2 Ergodic Convergence in the Primal Problem......Page 518
15.3.3 Enhanced Primal Ergodic Convergence......Page 519
15.3.4 Finite Primal Feasibility and Finite E-Optimality......Page 522
15.4 Dual Cutting-Planes: Dantzig–Wolfe Decomposition......Page 523
15.5 A Two-Phase Method: Subgradient Optimization and Dantzig–Wolfe Decomposition......Page 527
15.6.1 Primal Integer Solutions From Lagrangian Heuristics......Page 531
15.6.2 Approximate Solutions to the Primal Problem via Core Problems......Page 533
15.6.3 Optimal Solutions via a Branch-and-Bound Framework......Page 534
15.7 Notes and Further Reading......Page 536
References......Page 546
16.1 Introduction......Page 550
16.2 Deterministic Algorithms for Convex MINSO......Page 552
16.2.1 NSO Branch and Bound......Page 553
16.2.2 Outer Approximation......Page 555
16.2.3 Extended Cutting-Plane Method......Page 560
16.2.4 Extended Supporting Hyperplane Method......Page 564
16.2.5 Extended Level Bundle Method......Page 567
16.3 Illustrative Example......Page 570
16.4 Concluding Remarks......Page 576
References......Page 577
17.1 Introduction......Page 580
17.2 Basic Concepts......Page 581
17.3 Tackling the Lagrangian Dual......Page 587
17.4 Lagrangian Heuristics......Page 589
17.4.1 An Example of Dual Ascent......Page 591
17.5 Applications......Page 593
17.5.1 Generalized Assignment......Page 594
17.5.2 Spanning Tree with Minimum Branch Vertices......Page 596
17.5.3 Directional Sensors Location......Page 599
17.5.4 Cross Docking Scheduling......Page 604
17.5.5 Feature Selection in Support Vector Machines......Page 608
17.5.6 Multiple Instance Learning......Page 612
References......Page 616
Part IV Derivative-Free Methods......Page 619
18.1 Introduction......Page 620
18.2 Theoretical Background......Page 622
18.3 Discrete Gradients......Page 627
18.4 Approximation of Subdifferentials......Page 629
18.5 Discrete Gradient Method......Page 637
18.6 Limited Memory Discrete Gradient Bundle Method......Page 643
18.7 Illustrative Examples......Page 648
References......Page 651
19.1 Introduction......Page 654
19.2 Historical Overview......Page 656
19.2.1 Model-Based DFO for Nonsmooth Functions......Page 658
19.2.2 Model-Based DFO Used Within Direct Search......Page 661
19.3.1 Linear Interpolation and the Simplex Gradient......Page 663
19.3.2 Fully Linear and Fully Quadratic Models......Page 664
19.3.3 The Generalized Simplex Gradient......Page 666
19.3.4 Quadratic Models......Page 670
19.3.5 Using Fully Linear or Quadratic Models in a DFO Algorithm......Page 673
19.4.1 Accuracy of Nonsmooth Functions......Page 675
19.4.2 Constructing Models of Nonsmooth Functions......Page 681
19.5 Conclusions and Open Directions......Page 685
References......Page 686
Final Words......Page 691
Index......Page 693