Abstract
In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anandalingman G (1988) A mathematical programming model of decentralized multi-level systems. J Opl Res Soc 39:1021–1033
Başar T (1975) Equilibrium solutions in two-person quadratic decision problems with static information structures. IEEE Trans Automatic Control 20(3):320–328
Başar T (1978) Decentralized multicriteria optimization of linear stochastic systems. IEEE Trans Automatic Control 23(2):233–243
Başar T, Olsder GJ (1982) Dynamic Noncooperative game theory. Academic, London
Başar T, Selbuz H (1979) Closed-loop Stackelberg strategies with applications in the optimal control of multilevel systems. IEEE Trans Automatic Control 24(2):166–179
Choi SC, Desarbo WS, Harker PT (1990) Product positioning under price competition. Manage Sci 36(2):175–199
Clark PA (1983) Embedded optimization problems in chemical process design. PhD Thesis. Department of Chemical Engineering, Carnegie-Mellon University, Pittsburg
Cruz JB (1978) Leader-follower strategies for multilevel systems. IEEE Trans Automatic Control 23(2):244–255
Dua V, Papalexandri KP, Pistikopoulos EN (2004) Global optimization issues in multiparametric continuous and mixed-integer optimization problems. J Global Optim 30:59–89
Dua V, Bozinis NA, Pistikopoulos EN (2002) A multiparametric programming approach for mixed-integer quadratic engineering problems. Comput Chem Eng 26:715–733
Faísca NP, Kouramas KI, Pistikopoulos EN (2007a) Dynamic programming, Chap 7. Wiley-VCH. Weinheim
Faísca NP, Dua V, Saraiva PM, Rustem B, Pistikopoulos EN (2007b) Parametric global optimisation for bilevel programming. J Global Optim (in Press)
Fiacco AV(1976) Sensitivity analysis for nonlinear programming using penalty methods. Math Programm 10:287–311
Fiacco AV (1983) Introduction to sensitivity and stability analysis in nonlinear programming. Academic, New York
Floudas CA (2000) Deterministic global optimization. Kluwer, Dordrecht
Li M, Cruz JB, Simaan MA (2002) An approach to discrete-time incentive feedback stackelberg games. IEEE Trans Syst Man Cybern A: Syst Humans 32(4):472–481
Liu B (1998) Stackelberg–Nash equilibrium for multilevel programming with multiple followers using genetic algorithms. Comput Math Appl 36(7):79–89
McCormick GP (1976) Optimality criteria in nonlinear programming. SIAM-AMS Proc 1975(9):27
Morari M, Arkun Y, Stephanopoulos G (1980) Studies in the synthesis of control structures for chemical processes. AIChE J 26:220–232
Nie P, Chen L, Fukushima M (2006) Dynamic programming approach to discrete time dynamic feedback stackelberg games with independent and dependent followers. Euro J Oper Res 169:310–328
Pistikopoulos EN, Georgiadis MC, Dua V (2007a) Multi-parametric programming: theory, algorithms, and applications, vol 1. Wiley-VCH, Weinheim
Pistikopoulos EN, Georgiadis MC, Dua V (2007b) Multi-parametric model-based control: theory and applications, vol 2. Wiley-VCH, Weinheim
Pistikopoulos EN, Dua V, Bozinis NA, Bemporad A, Morari M (2000) On-line optimization via off-line parametric optimization tools. Comput Chem Eng 24:183–188
Rodić AD, Vukobratović MK (1999) Contribution to the integrated control synthesis of road vehicles. IEEE Trans Control Syst Technol 7(1):64–78
Ruan GZ, Wang SY, Yamakamoto Y, Zhu SS (2004) Optimality conditions and geometric properties of linear multilevel programming problem with dominated objective functions. J Optim Theory Appl 123(2):409–429
Shih HS, Wen UP, Lee ES, Lan KM, Hsiao HC (2004) A neural network approach to multiobjective and multilevel programming problems. Comput Math Appl 48:95–108
Stephanopoulos G, Ng C (2000) Perspectives on the synthesis of plant-wide control structures. J Process Control 10:97–111
Tolwinski B (1981) Closed-loop stackelberg solution to a multistage linear-quadratic game. J Optim Theory Appl 34(4):485–501
Vicente LN (1992) Bilevel programming. Master’s Thesis. Department of Mathematics, University of Coimbra, Coimbra
Vicente LN, Calamai PH (1994) Bilevel and multilevel programming: a bibliography review. J Global Optim 5(3):291–306
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Faísca, N.P., Saraiva, P.M., Rustem, B. et al. A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems. Comput Manag Sci 6, 377–397 (2009). https://doi.org/10.1007/s10287-007-0062-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-007-0062-z