A local convergence analysis of bilevel decomposition algorithms. (English) Zbl 1176.90566
Summary: Multidisciplinary design optimization (MDO) problems are engineering design problems that require the consideration of the interaction between several design disciplines. Due to the organizational aspects of MDO problems, decomposition algorithms are often the only feasible solution approach. Decomposition algorithms reformulate the MDO problem as a set of independent subproblems, one per discipline, and a coordinating master problem. A popular approach to MDO problems is bilevel decomposition algorithms. These algorithms use nonlinear optimization techniques to solve both the master problem and the subproblems. In this paper, we propose two new bilevel decomposition algorithms and analyze their properties. In particular, we show that the proposed problem formulations are mathematically equivalent to the original problem and that the proposed algorithms converge locally at a superlinear rate. Our computational experiments illustrate the numerical performance of the algorithms.
MSC:
| 90C30 | Nonlinear programming |
Keywords:
decomposition algorithms; bilevel programming; nonlinear programming; multidisciplinary design optimization (MDO)References:
| [1] | Alexandrov NM, Hussaini MY (eds.), (1997) Multidisciplinary optimization: State of the art, Philadelphia, SIAM. |
| [2] | Alexandrov NM, Lewis RM (1999) Comparative properties of collaborative optimization and other approaches to MDO, Proc., First ASMO UK/ISSMO conference on Engineering Design Optimization, MCB Press. |
| [3] | Alexandrov NM, Lewis RM (2000) Analytical and computational aspects of collaborative optimization, Tech. Report TM-2000-210104, NASA |
| [4] | Braun RD (1996) Collaborative optimization: An architecture for large-scale distributed design., Ph.D. thesis, Stanford University |
| [5] | Braun RD, Kroo IM (1997) Development and application of the collaborative optimization architecture in a multidisciplinary design environment, Multidisciplinary Design Optimization: State of the Art (N.M. Alexandrov and M.Y. Hussaini, eds.) |
| [6] | Calamai PH, Vicente LN (1994) Generating quadratic bilevel programming test problems, ACM Transactions on Mathematical Software 20(1):103–119 · Zbl 0888.65068 · doi:10.1145/174603.174411 |
| [7] | Cramer EJ, Dennis JE, Frank PD, Lewis RM, Shubin GR (1994) Problem formulation for multidisciplinary optimization, SIAM J. Optimization 4(4):754–776 · Zbl 0818.65055 · doi:10.1137/0804044 |
| [8] | DeMiguel AV (2001) Two decomposition algorithms for nonconvex optimization problems with global variables, Ph.D. thesis, Stanford University |
| [9] | DeMiguel AV, Murray W (2000) An analysis of collaborative optimization methods, Eight AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, AIAA Paper 00–4720 |
| [10] | DeMiguel AV, Murray W (2001a) Generating optimization problems with global variables, Tech. Report SOL 01-3, Dept. of Management Science and Engineering, Stanford University |
| [11] | DeMiguel AV, Murray W (2001b) Two decomposition algorithms for nonconvex optimization problems with global variables, Tech. Report SOL 01-1, Dept. of Management Science and Engineering, Stanford University |
| [12] | DeMiguel V, Nogales FJ (2005) On decomposition methods for multidisciplinary design optimization. Working paper, London Business School |
| [13] | Dempe S (2002) Foundations of bilevel programming, Kluwer Academic Publishers, Boston · Zbl 1038.90097 |
| [14] | Fiacco AV (1983) Introduction to sensitivity and stability analysis in nonlinear programming, Academic Press: New York · Zbl 0543.90075 |
| [15] | Fiacco AV, McCormick GP (1968) Nonlinear programming: Sequential unconstrained minimization techniques, New York: John Wiley & Sons · Zbl 0193.18805 |
| [16] | Fletcher R (1987) Practical methods of optimization, Wiley: New York · Zbl 0905.65002 |
| [17] | Gill PE, Murray W, Saunders MA, Wright MH (1986) User’s guide for NPSOL (version 4.0), Tech. Report SOL 86-2, Dept. of Operations Research, Stanford University |
| [18] | Gill PE, Murray W, Wright MH (1981) Practical optimization, Academic Press: New York · Zbl 0503.90062 |
| [19] | Haftka RT, Sobieszczanski-Sobieski J (1997) Multidisciplinary aerospace design optimization: Survey of recent developments. Structural Optimization 14:1–23 · doi:10.1007/BF01197554 |
| [20] | Haftka RT, Watson LT (2002) Multidisciplinary design optimization with quasiseparable subsystems, Tech. Report TR-02-09, Computer Science, Virginia Polytechnic Institute and State University · Zbl 1093.90026 |
| [21] | Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints, Cambridge University Press: Cambridge |
| [22] | Manning VM (2000) Large-scale design of supersonic aircraft via collaborative optimization., Ph.D. thesis, Stanford University |
| [23] | Murray W, Prieto FJ (1995) A sequential quadratic programming algorithm using an incomplete solution of the subproblem. SIAM J. Optimization 5(3):590–640 · Zbl 0840.65052 · doi:10.1137/0805030 |
| [24] | Nocedal J, Wright SJ (1999) Numerical optimization, Springer-Verlag: New York · Zbl 0930.65067 |
| [25] | Rockafellar RT, Wets RJ-B (1991) Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research 16:119–147 · Zbl 0729.90067 · doi:10.1287/moor.16.1.119 |
| [26] | Rodriguez JF, Renaud JE, Watson LT (1998a) Convergence of trust region augmented lagrangian methods using variable fidelity approximation data. Structural Optim. 15:141–156 · doi:10.1007/BF01203525 |
| [27] | Rodriguez JF, Renaud JE, Watson LT (1998b) Trust region augmented lagrangian methods for sequential response surface approximation and optimization. ASME M. Mech. Design 120:58–66 · doi:10.1115/1.2826677 |
| [28] | Shankar J, Ribbens CJ, Haftka RT, Watson LT 1993 Computational study of a nonhierarchical decomposition algorithm. Comput. Optim. Appl. 2:273–293 · Zbl 0792.90072 · doi:10.1007/BF01299452 |
| [29] | Shimizu K, Ishizuka Y, Bard JF (1997) Nondifferentiable and two-level mathematical programming, Boston: Kluwer Academic Publishers · Zbl 0878.90088 |
| [30] | Sobieski IP (1998) Multidisciplinary design using collaborative optimization., Ph.D. thesis, Stanford University |
| [31] | Sobieszczanski-Sobieski J (1988) Optimization by decomposition: A step from hierarchic to nonhierarchic systems, Second NASA/Air Force Symp. on Recent Advances in Multidisciplinary Analysis and Optimization |
| [32] | Tammer K (1987) The application of parametric optimization and imbedding for the foundation and realization of a generalized primal decomposition approach. Parametric optimization and related topics Guddat J, Jongen H, Kummer B, and Nozicka F (eds.), Mathematical Research, vol. 35, Akademie-Verlag, Berlin · Zbl 0634.90079 |
| [33] | Wright SJ (1997) Primal-Dual Interior-Point Methods, SIAM, Philadelphia · Zbl 0863.65031 |
| [34] | Yamashita H, Yabe H (1996) Superlinear and quadratic convergence of some primal–dual interior point methods for constrained optimization, Mathematical Programming 75:377–397 · Zbl 0874.90175 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
