Multilevel Optimization: Algorithms and Applications

Researchers working with nonlinear programming often claim "the word is non linear" indicating that real applications require nonlinear modeling. The same is true for other areas such as multi-objective programming (there are always several goals in a real application), stochastic programming (all data is uncer tain and therefore stochastic models should be used), and so forth. In this spirit we claim: The word is multilevel. In many decision processes there is a hierarchy of decision makers, and decisions are made at different levels in this hierarchy. One way to handle such hierar chies is to focus on one level and include other levels' behaviors as assumptions. Multilevel programming is the research area that focuses on the whole hierar chy structure. In terms of modeling, the constraint domain associated with a multilevel programming problem is implicitly determined by a series of opti mization problems which must be solved in a predetermined sequence. If only two levels are considered, we have one leader (associated with the upper level) and one follower (associated with the lower level).

Klappentext

In many decision processes there is an hierarchy of decision-makers and decisions are taken at different levels in this hierarchy. Multilevel programming focuses on the whole hierarchy structure. In terms of modeling, the constraint domain associated with a multilevel programming problem is implicitly determined by a series of optimization problems which must be solved in a predetermined sequence. The field of multilevel optimization has become a well-known and important research field. Hierarchical structures can be found in scientific disciplines such as environment, ecology, biology, chemical engineering, mechanics, classification theory, databases, network design, transportation, game theory and economics. Moreover, new applications are constantly being introduced. This has stimulated the development of new theory and efficient algorithms. This volume contains 16 chapters written by various leading researchers and presents a cohesive authoritative overview of developments and applications in their emerging field of optimization. Audience: Researchers whose work involves the application of mathematical programming and optimization to hierarchical structures.

Inhalt
1 Congested O-D Trip Demand Adjustment Problem: Bilevel Programming Formulation and Optimality Conditions.- 1 Introduction.- 2 Literature Review.- 3 Model Analysis.- 4 Necessary Optimality Conditions of the DAP.- 5 Conclusions.- 2 Determining Tax Credits for Converting Nonfood Crops to Biofuels: An Application of Bilevel Programming.- 1 Introduction.- 2 Mathematical Model.- 3 Description of Algorithms.- 4 Computational Results.- 5 Discussion.- 3 Multilevel Optimization Methods in Mechanics.- 1 Introduction.- 2 Presentation of the Multilevel Decomposition Methods.- 3 Large Cable Structures.- 4 Large Elastoplastic Structures.- 5 Validation and Improvements of Simplified Models.- 6 Extension to other Problems. Decomposition Algorithms for Nonconvex Minimization Problems.- 7 A Multilevel Method for the Approximation of a Nonconvex Minimum Problem by Convex ones.- 8 Multilevel Decomposition into two Convex Problems.- 9 Structures with Fractal Interfaces.- 4 Optimal Structural Design in Nonsmooth Mechanics.- 1 Introduction.- 2 Parametric Nonsmooth Structural Analysis Problems.- 3 Optimal Design Problems.- 4 Mathematical Analysis and Algorithms.- 5 Discussion.- References.- 5 Optimizing the Operations of an Aluminium Smelter Using Non-Linear Bi-Level Programming.- 1 Introduction.- 2 The Mathematical Model of the Aluminium Smelter.- 3 The Solution Algorithm.- 4 The Mathematical Model Representing the Multi-period Operations of the Aluminium Smelter.- 5 Concluding Remarks.- References.- 6 Complexity Issues in Bilevel Linear Programming.- 1 Introduction.- 2 Difficulty in Approximation.- 3 A Special Case Solvable in Polynomial Time.- 4 Regret Ratio in Decision Analysis.- 5 Future Directions.- References.- 7 The Computational Complexity of Multi-Level Bottleneck Programming Problems.- 1 Introduction.- 2 Problem Statement and Previous Complexity Results.- 3 Hardness Proof for Multi-Level Bottleneck Programs.- 4 Hardness Proof for Multi-Level Linear Programs.- 5 The Complexity of Bi-Level Programs.- 6 Discussion.- References.- 8 On the Linear Maxmin and Related Programming Problems.- 1 Introduction.- 2 Reformulations.- 3 Tools for Resolution.- 4 Solving the Linear Maxmin Problem.- 9 Piecewise Sequential Quadratic Programming for Mathematical Programs with Nonlinear Complementarity Constraints.- 1 Introduction.- 2 Application to Optimal Design of Mechanical Structures.- 3 The Piecewise Smooth Approach to NCP-MP.- 4 The PSQP Method for NCP-MPEC.- 5 Computational Testing of PSQP.- References.- 10 A New Branch and Bound Method for Bilevel Linear Programs.- 1 Introduction.- 2 The Equivalent Reverse Convex Program.- 3 Solution Method.- 4 Implementation Issues.- 5 Illustrative Example.- 11 A Penalty Method for Linear Bilevel Programming Problems.- 1 Introduction.- 2 Linear Bilevel Programming Problem.- 3 The Method.- 4 Globalization of the Solution.- 5 Numerical Examples.- 6 Concluding Remarks.- 12 An Implicit Function Approach to Bilevel Programming Problems.- 1 Introduction.- 2 Lipschitz Continuity of Optimal Solutions.- 3 Application of the Bundle Method.- 4 Non-uniquely Solvable Lower Level Problems.- 5 Nonconvex Lower Level Problems and Coupling Constraints in the Upper Level Problem.- 13 Bilevel Linear Programming, Multiobjective Programming, and Monotonic Reverse Convex Programming.- 1 Introduction.- 2 Optimization over the Efficient Set.- 3 Bilevel Linear Programming.- 4 Basic Properties of (FMRP).- 5 Different D.C. Approaches to (FMRP).- 14 Existence of Solutions to Generalized Bilevel Programming Problem.- 1 Introduction.- 2 Notations and Preliminaries.- 3 Parametric Implicit Variational Problem.- 4 Existence Results for Generalized Bilevel Problems.- 5 Final Remarks.- 15 Application of Topological Degree Theory to Complementarity Problems.- 1 Problem Specification and Topological Degree Theory.- 2 General Complementarity Problem.- 3 Sufficient Conditions for Solution Existence.- 4 Standard Complementarity Problem.- 5 Implicit Complementarity Problem.- 6 General Order Complementarity Problem.- References.- 16 Optimality and Duality in Parametric Convex Lexicographic Programming.- 1 Introduction.- 2 Orientation.- 3 Continuity.- 4 Global Optimality.- 5 Local Optimality.- 6 Duality.- 7 Bilevel Zermelo's Problems.