In this book, the theory, methods and applications of separable optimization are considered. Some general results are presented, techniques of approximating the separable problem by linear programming problem, and dynamic programming are also studied. Convex separable programs subject to inequality/ equality constraint(s) and bounds on variables are also studied and convergent iterative algorithms of polynomial complexity are proposed. As an application, these algorithms are used in the implementation of stochastic quasigradient methods to some separable stochastic programs. The problems of numerical approximation of tabulated functions and numerical solution of overdetermined systems of linear algebraic equations and some systems of nonlinear equations are solved by separable convex unconstrained minimization problems. Some properties of the Knapsack polytope are also studied. This second edition includes a substantial amount of new and revised content. Three new chapters, 15-17, are included. Chapters 15-16 are devoted to the further analysis of the Knapsack problem. Chapter 17 is focused on the analysis of a nonlinear transportation problem. Three new Appendices (E-G) are also added to this edition and present technical details that help round out the coverage.
Optimization problems and methods for solving the problems considered are interesting not only from the viewpoint of optimization theory, optimization methods and their applications, but also from the viewpoint of other fields of science, especially the artificial intelligence and machine learning fields within computer science. This book is intended for the researcher, practitioner, or engineer who is interested in the detailed treatment of separable programming and wants to take advantage of the latest theoretical and algorithmic results. It may also be used as a textbook for a special topics course or as a supplementary textbook for graduate courses on nonlinear and convex optimization.
Author(s): Stefan M. Stefanov
Series: Springer Optimization and Its Applications, 177
Edition: 2
Publisher: Springer
Year: 2021
Language: English
Pages: 373
Tags: Separable Optimization; Convex Analysis; Convex Programming;
Preface to the Second Edition
Preface to the First Edition
Contents
1 Preliminaries: Convex Analysis and Convex Programming
1.1 Convex Sets. Sum of Sets and Product of a Set with a Real Number
1.2 Projection of a Point onto a Set. Separation of Sets and Support of Sets
1.3 Convex Functions
1.4 Directional Derivatives, Subgradients, and Subdifferentials. Differentiable Convex Functions
1.5 Convex Programming
1.6 Lagrangian Duality
Part I Separable Programming
2 Introduction. Approximating the Separable Problem
3 Convex Separable Programming
4 Separable Programming: A Dynamic Programming Approach
4.1 The Discrete Case
4.2 Forward and Backward Recursion. Successive Decision-Making
4.3 The Continuous Case
4.4 Models Involving Two Types of Constraints. Problem of Dimensionality …
4.5 Two-dimensional Allocation Problem
4.6 Application of Lagrange Multiplier Method for Reducing the Dimensionality …
4.7 Application of Dynamic Programming Approach to the Transportation …
4.8 Review of Some Separable Inventory and Other Models
4.8.1 Deterministic Static Models
4.8.2 Dynamic Inventory Models
4.8.3 Probabilistic Inventory Models. No-Setup Models
4.8.4 Investment Models
Part II Convex Separable Programming with Bounds on the Variables
5 Statement of the Main Problem. Basic Result
6 Version One: Linear Equality Constraints
6.1 Single Linear Equality Constraint
6.2 Several Linear Equality Constraints
7 The Algorithms
7.1 Analysis of the Optimal Solution to Problem (C)
7.2 Statement of Algorithm 1 (for Problem (C))
7.3 Convergence and Computational Complexity of Algorithm 1
7.4 Analysis of the Optimal Solution to Problem (C=)
7.5 Algorithm 2 (for Problem (C=)) and Its Convergence
7.6 Commentary
8 Version Two: Linear Constraint of the Form ``ge''
8.1 Statement of Problem (Cge) and Results
8.2 Algorithm 3 (for Problem (Cge))
9 Well-Posedness of Optimization Problems
9.1 Well-Posedness and Calmness of Optimization Problems
9.1.1 Tychonov and Hadamard Well-Posedness. Well-Posedness in the Generalized Sense
9.1.2 Calmness in the Sense of Clarke
9.1.3 Well-Posedness of Problems (C), (C=), and (Cge)
9.2 On the Stability of the Set of Saddle Points of the Lagrangian
9.2.1 The Concept of Stability of Saddle Points of the Lagrangian
9.2.2 Concerning Stability of the Set of Saddle Points for the Methods Suggested for Problems (C), (C=), (Cge)
10 Extensions
10.1 Theoretical Aspects
10.2 Computational Aspects
11 Applications and Computational Experiments
11.1 Some Important Types of Functions for Problems (C), (C=), and (Cge)
11.2 Computational Experiments
Part III Selected Supplementary Topics and Applications
12 Applications of Convex Separable Unconstrained Nondifferentiable Optimization to Approximation Theory
12.1 Introduction. Statement of Problems Under Consideration
12.2 Some Properties of Objective Functions and Solvability of Problems
12.3 Methods for Solving Problems Under Consideration
12.3.1 Theoretical Matters. The Subgradient Method
12.3.2 Calculation of Subgradients and Subdifferentials
12.3.3 The Gradient Method for Differentiable Functions
12.4 Numerical Solution of Some Systems of Nonlinear Algebraic Equations
12.4.1 Statement of Problems Under Consideration
12.4.2 Properties of the Objective Functions and Solvability of the Considered Problems
12.4.3 Calculation of Subgradients and Subdifferentials
12.4.4 Calculation of Gradients
12.5 Solution of Systems of Nonlinear Equations Defined by Convex Functions
12.5.1 Systems of Nonlinear Equations Defined by Convex Differentiable Functions
12.5.2 Systems of Nonlinear Equations Defined by Separable Convex Differentiable Functions
12.5.3 Solvability of the Considered Problems
12.5.4 Calculation of Subgradients and Subdifferentials
12.5.5 Calculation of Gradients
12.6 Computational Experiments and Conclusions
13 About Projections in the Implementation of Stochastic Quasigradient Methods to Some Probabilistic Inventory Control Problems
13.1 Introduction
13.2 Stochastic Quasigradient Methods
13.3 On the Projection in the Implementation of Stochastic …
13.4 The Stochastic Problem of Best Chebyshev Approximation
14 Valid Inequalities, Cutting Planes, and Integrality of the Knapsack Polytope
14.1 Basic Formulations, Definitions, and Results
14.1.1 Formulations
14.1.2 Definitions
14.1.3 Preliminaries
14.2 Valid Inequalities for Knapsack Polytope
14.2.1 Valid, Equivalent, and Dominating Inequalities
14.2.2 Valid Inequalities Generation—Modular Arithmetic Approach
14.3 Integrality of the Knapsack Polytope
15 Relaxation of the Equality Constrained Convex Continuous Knapsack Problem
15.1 Introduction
15.2 The Relaxed Problem
16 On the Solution of Multidimensional Convex Separable Continuous Knapsack Problem with Bounded Variables
16.1 Statement of the Problem
16.2 Characterization Theorem
16.3 Primal-dual Analysis
17 Characterization of the Optimal Solution of the Convex Generalized Nonlinear Transportation Problem
17.1 Statement of the Problems
17.2 Characterization Theorem for Problem (GNTP)
17.3 Generalized Nonlinear Transportation Problem with Bounded …
Appendix A Some Definitions and Theorems of Calculus
Appendix B Metric, Banach and Hilbert Spaces
Appendix C Existence of Solutions to Optimization Problems—A General Approach
Appendix D Best Approximation: Existence and Uniqueness
Appendix E On the Solvability of a Quadratic Optimization Problem with a Feasible Region Defined as a Minkowski Sum of a Compact Set and Finitely Generated Convex Closed Cone
Appendix F On the Cauchy-Schwarz Inequality Approach for Solving a Quadratic Optimization Problem
Appendix G Theorems of the Alternative
Appendix Bibliography
Appendix Notation
Appendix List of Statements
Index
