Basic Mathematical Programming Theory

The subject of (static) optimization, also called mathematical programming, is one of the most important and widespread branches of modern mathematics, serving as a cornerstone of such scientific subjects as economic analysis, operations research, management sciences, engineering, chemistry, physics, statistics, computer science, biology, and social sciences. This book presents a unified, progressive treatment of the basic mathematical tools of mathematical programming theory. The authors expose said tools, along with results concerning the most common mathematical programming problems formulated in a finite-dimensional setting, forming the basis for further study of the basic questions on the various algorithmic methods and the most important particular applications of mathematical programming problems. This book assumes no previous experience in optimization theory, and the treatment of the various topics is largely self-contained. Prerequisites are the basic tools of differential calculus for functions of several variables, the basic notions of topology and of linear algebra, and the basic mathematical notions and theoretical background used in analyzing optimization problems. The book is aimed at both undergraduate and postgraduate students interested in mathematical programming problems but also those professionals who use optimization methods and wish to learn the more theoretical aspects of these questions. Preface 6 Contents 10 1 Basic Notions and Definitions 12 1.1 Introduction 12 1.2 Basic Notions of Analysis and Linear Algebra 13 1.3 Basic Definitions and Properties of Optimization Problems 20 References 33 2 Elements of Convex Analysis. Linear Theorems of the Alternative. Tangent Cones 34 2.1 Elements of Convex Analysis 34 2.2 Theorems of the Alternative for Linear Systems 52 2.3 Tangent Cones 58 References 63 3 Convex Functions and Generalized Convex Functions 64 3.1 Convex Functions 64 3.2 Generalized Convex Functions 75 3.3 Optimality Properties of Convex and Generalized Convex Functions. Nonlinear Theorems of the Alternative 85 References 92 4 Unconstrained Optimization Problems. Set-Constrained Optimization Problems. Classical Constrained Optimization Problems 94 4.1 Unconstrained Optimization Problems 94 4.2 Set-Constrained Optimization Problems 107 4.3 Optimization Problems with Equality Constraints (``Classical Constrained Optimization Problems'') 113 References 132 5 Constrained Optimization Problems with Inequality Constraints 134 5.1 First-Order Conditions 134 5.2 Constraint Qualifications 148 5.3 Second-Order Conditions 152 5.4 Other Formulations of the Problem. Some Examples 158 References 178 6 Constrained Optimization Problems with Mixed Constraints 180 6.1 First-Order Conditions 180 6.2 Constraint Qualifications 195 6.3 Second-Order Conditions 212 6.4 Problems with a Set Constraint. Asymptotic Optimality Conditions 226 References 233 7 Sensitivity Analysis 236 7.1 General Results 236 7.2 Sensitivity Results for Right-Hand Side Perturbations 247 References 253 8 Convex Optimization: Saddle Points Characterization and Introduction to Duality 254 8.1 Convex Optimization: Saddle Points Characterization 254 8.2 Introduction to Duality 265 References 284 9 Linear Programming and Quadratic Programming 285 9.1 Linear Programming 285 9.2 Duality for Linear Programming 299 9.3 Quadratic Programming 311 References 325 10 Introduction to Nonsmooth Optimization Problems 327 10.1 The Convex Case 328 10.2 The Lipschitz Case 347 10.3 The Axiomatic Approach of K.-H. Elster and J. Thierfelder to Nonsmooth Optimization 377 References 389 11 Introduction to Multiobjective Optimization 393 11.1 Optimality Notions 394 11.2 The Weighted Sum Method and Relations with Proper Efficiency 409 11.3 Optimality Conditions 413 References 439 Index 441