Separable Optimization: Theory and Methods

Description

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. 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