×

An outcome-space finite algorithm for solving linear multiplicative programming. (English) Zbl 1103.65065

The authors present an outcome-space finite algorithm for solving the linear multiplicative programming problem. The algorithm solves a convex quadratic programming in each iteration. The convergence of the algorithm is established. Some numerical results are presented.

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
90C20 Quadratic programming
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bennett, K. P., Global tree optimization: a non-greedy decision tree algorithm, Computing Sciences and Statistics, 26, 156-160 (1994)
[2] Benson, H. P., Vector maximization with two objective functions, Journal of Optimization Theory and Applications, 28, 253-257 (1979) · Zbl 0372.90126
[3] Keeney, R. L.; Raiffa, H., Decisions with Multiple Objective (1993), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 0488.90001
[4] Geoffrion, M., Solving bicriterion mathematical programs, Operation Research, 5, 39-54 (1967) · Zbl 0173.21602
[5] Konno, H.; Shirakawa, H.; Yamazaki, H., A mean-absolute deviation skewness portfolio optimization model, Annals of Operations Research, 45, 205-220 (1993) · Zbl 0785.90014
[6] Markowitz, H. M., Portfolio Selection (1991), Basil Blackwell Inc.: Basil Blackwell Inc. Oxford
[7] Konno, H.; Watanabe, H., Bond portfolio optimization problems and their application to index tracking: a partial optimization approach, Journal of the Operations Research Society of Japan, 39, 285-306 (1996) · Zbl 0873.90009
[8] Maranas, C. D.; Androulakis, I. P.; Floudas, C. A.; Berger, A. J.; Mulvey, J. M., Solving long-term financial planning problems via global optimization, Journal of Economic Dynamics & Control, 21, 1405-1425 (1997) · Zbl 0901.90016
[9] Henderson, J. M.; Quandt, R. E., Microeconomic Theory (1971), McGraw-Hill: McGraw-Hill New York · Zbl 0224.90014
[10] Kuno, T., Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set, Operations Research Letters, 13, 295-303 (1993) · Zbl 0799.90098
[11] Konno, H.; Kuno, T., Generalized linear multiplicative and fractional programming, Annals of Operations Research, 25, 147-161 (1990) · Zbl 0725.90082
[12] Bennett, K. P.; Mangasarian, O. L., Bilinear separation of two sets in n-space, Computational Optimization and Applications, 2, 207-227 (1994) · Zbl 0795.90060
[13] Falk, J. E.; Palocsa, S. W., Image space analysis of generalized fractional programs, Journal of Global Optimization, 4, 1, 63-88 (1994) · Zbl 0809.90121
[14] Benson, H. P.; Boger, G. M., Analysis of an outcome-space formulation of the multiplicative programming problem, (Yong Shi; Milan Zeleny, New Frontiers of Decision Making for the Information Technology Era (1998), World Scientific Publishing Co.: World Scientific Publishing Co. Singapore), 100-122
[15] Benson, H. P.; Boger, G. M., Outcome-space cutting-plane algorithm for linear multiplicative programming, Journal of Optimization Theory and Applications, 104, 2, 301-332 (2000) · Zbl 0962.90024
[16] Matsui, T., NP-Hardness of linear multiplicative programming and related problems, Journal of Global Optimization, 9, 2, 113-119 (1996) · Zbl 0868.90111
[17] Konno, H.; Kuno, T., Linear multiplicative programming, Mathematical Programming, 56, 51-64 (1992) · Zbl 0761.90080
[18] Konno, H.; Kuno, T.; Yajima, Y., Global optimization of a generalized convex multiplicative function, Journal of Global Optimization, 4, 47-62 (1994) · Zbl 0791.90045
[19] Konno, H.; Yajima, Y.; Matsui, T., Parametric simplex algorithms for solving a special class of nonconvex minimization problems, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[20] Kuno, T.; Yajima, Y.; Konno, H., An outer approximation method for minimizing the product of several convex functions on a convex set, Journal of Global Optimization, 3, 3, 325-335 (1993) · Zbl 0798.90117
[21] Thoai, N. V., A global optimization approach for solving the convex multiplicative programming problems, Journal of Global Optimization, 1, 4, 341-357 (1991) · Zbl 0752.90056
[22] Pardalos, P. M., Polynomial time algorithms for some classes of constrained quadratic problems, Optimization, 21, 6, 843-853 (1990) · Zbl 0714.90082
[23] Bazaaraa, M. S.; Shetty, C. M., Nonlinear programming: Theory and Algorithms (1979), Wiley: Wiley New York
[24] Schaible, S.; Sodini, C., Finite algorithm for generalized linear multiplicative programming, Journal of Optimization Theory and Applications, 87, 2, 41-55 (1995) · Zbl 0839.90113
[25] Konno, H.; Kuno, T.; Yajima, Y., Parametric simplex algorithms of a class of NP-complete problems whose average number of steps is polynomial, Computational Optimization and Applications, 1, 227-239 (1992) · Zbl 0770.90048
[26] Benson, H. P.; Boger, G. M., Multiplicative programming problems: analysis and efficient point search heuristic, Journal of Optimization Theory and Applications, 94, 2, 487-510 (1997) · Zbl 0889.90128
[27] Liu, X. J.; Umegaki, T.; Yamamoto, Y., Heuristic methods for linear multiplicative programming, Journal of Global Optimization, 4, 15, 433-447 (1999) · Zbl 0966.90051
[28] Dorneich, M. C.; Sahinidis, N. V., Global optimization algorithms for chip design and compaction, Engineering Optimization, 25, 2, 131-154 (1995)
[29] K. Maling, S.H. Mueller, W.R. Heller, On finding most optimal rectangular package plans, in: Proceedings of the 19th Design Automation Conference, 1982, pp. 663-670.; K. Maling, S.H. Mueller, W.R. Heller, On finding most optimal rectangular package plans, in: Proceedings of the 19th Design Automation Conference, 1982, pp. 663-670.
[30] Hong, S. R.; Nikolaos, V. S., Global optimization of multiplicative programs, Journal of Global Optimization, 26, 387-418 (2003) · Zbl 1052.90091
[31] Kuno, T., Solving a class of multiplicative programs with 0-1 knapsack constraints, Journal of Optimization Theory and Applications, 103, 121-125 (1999) · Zbl 0945.90028
[32] Benson, H. P., An outcome space branch and bound-outer approximation algorithm for convex multiplicative programming, Journal of Global Optimization, 15, 315-342 (1999) · Zbl 0997.90078
[33] Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A., Robust optimization of large-scale systems, Operations Research, 43, 264-281 (1995) · Zbl 0832.90084
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.