×
Rosen, J. B.; Pardalos, P. M.

Global minimization of large-scale constrained concave quadratic problems by separable programming. (English) Zbl 0597.90066

Math. Program. 34, 163-174 (1986).
In der Arbeit werden konkave quadratische Minimierungsprobleme untersucht, in denen ein Teil der Variablen nur im Linearteil der Zielfunktion auftritt. Im zweiten Abschnitt wird durch eine Eigenwert- Eigenvektor-Zerlegung der quadratischen Form ein äquivalentes separables quadratisches Problem formuliert. Falls der zulässige Bereich beschränkt ist, kann mit den minimalen beziehungsweise maximalen Werten der Einzelfunktionen des separablen Problems eine untere Schranke für das Ausgangsproblem angegeben werden. Zur Bestimmung von \(\epsilon\)-Lösungen wird im vierten Abschnitt ein gemischt-ganzzahliges 0-1-Problem formuliert. Den Abschluß der Arbeit bildet die Formulierung eines Algorithmus und erste Testresultate.
Reviewer: H.Bernau

Cited in 52 Documents

MSC:

90C20 Quadratic programming
65K05 Numerical mathematical programming methods

Keywords:

large-scale linearly constrained concave quadratic problem; separable programming; concave quadratic minimization; eigenvalue-eigenvector- decomposition; \(\epsilon \) -optimal solutions

Software:

LINDO; EISPACK
PDF BibTeX XML Cite
\textit{J. B. Rosen} and \textit{P. M. Pardalos}, Math. Program. 34, 163--174 (1986; Zbl 0597.90066)
Full Text: DOI

References:

[1] M.S. Bazaraa and H.D. Sherali, ”On the use of exact and heuristic cutting plane methods for the quadratic assignment problem”,Journal of Operational Research Society 33 (1982) 991–1003. · Zbl 0497.90042
[2] H. Crowder, E.L. Johnson and M.W. Padberg, ”Solving large-scale zero–one linear programming problems”,Operations Research 31 (1982) 803–834. · Zbl 0576.90065
[3] J.E. Falk and K.R. Hoffman, ”A successive underestimating method for concave minimization problems”,Mathematics of Operations Research 1 (1976) 251–259. · Zbl 0362.90082
[4] A.M. Frieze, ”A bilinear programming formulation of the 3-dimensional assignment problem”,Mathematical Programming 7 (1974) 376–379. · Zbl 0296.90031
[5] C.D. Heising-Goodman, ”A survey of methodology for the global minimization of concave functions subject to convex constraints”,OMEGA, International Journal of Management Science 9 (1981) 313–319.
[6] R. Horst, ”An algorithm for nonconvex programming problems”,Mathematical Programming 10 (1976) 312–321. · Zbl 0337.90062
[7] B. Kalantari, ”Large scale concave quadratic minimization and extensions”, Ph.D. thesis, Computer Science Department, University of Minnesota (Minneapolis, MN, 1984).
[8] B. Kalantari and J.B. Rosen, ”Construction of large scale global minimum concave quadratic test problems”, to be published inJournal of Optimization Theory and Applications (1986). · Zbl 0559.90066
[9] H. Konno, ”Maximizing a convex quadratic function subject to linear constraints”,Mathematical Programming 11 (1976) 117–127. · Zbl 0355.90052
[10] E.L. Lawler, ”The quadratic assignment problem”,Management Science 9 (1963) 586–599. · Zbl 0995.90579
[11] O.L. Mangasarian, ”Characterization of linear complementarity problems as linear programs”,Mathematical Programming Study 7 (1978) 74–87. · Zbl 0378.90053
[12] P.M. Pardalos and J.B. Rosen, ”Methods for global concave minimization: A bibliographic survey”, to appear inSIAM Review (1986). · Zbl 0602.90105
[13] M. Raghavachari, ”On connections between zero–one integer programming and concave programming under linear constraints”,Operations Research 17 (1969) 680–684. · Zbl 0176.49805
[14] J.B. Rosen, ”Global minimization of a linearly constrained concave function by partition of feasible domain”,Mathematics of Operations Research 8 (1983) 215–230. · Zbl 0526.90072
[15] J.B. Rosen, ”Performance of approximate algorithms for global minimization”,Mathematical Programming Study 22 (1984) 231–236. · Zbl 0554.90085
[16] J.B. Rosen, ”Computational solution of large scale constrained global minimization problems”, in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (SIAM, Philadelphia, PA, 1985) pp. 263–271.
[17] L. Schrage,Linear integer and quadratic programming with LINDO (Scientific Press, Palo Alto, CA, 1984).
[18] B.T. Smith, J. Boyle, B. Garbow, Y. Ikebe, V. Klema and C. Moler,Matrix eigensystem routines-EISPACK guide, Lecture notes in computer science, Vol. 6 (Springer-Verlag, New York, 1976). · Zbl 0325.65016
[19] N.V. Thoai and H. Tuy, ”Convergent algorithms for minimizing a concave function”,Mathematics of Operations Research 5 (1980) 556–566. · Zbl 0472.90054
[20] H. Tuy, ”Concave programming under linear constraints”,Doklady Akademii Nauk SSSR 159, 32–35 (English translation inSoviet Mathematics Doklady 5 (1964) 1437–1440).
[21] H. Tuy, ”Global minimization of a difference of two convex functions”, in:Selected topics in operations research and mathematical economics. Lecture Notes in Economics and Mathematical Systems 226 (1984) 98–118.
[22] H. Watanabe, ”IC layout generation and compaction using mathematical optimization”, Ph.D. Thesis, Computer Science Department, University of Rochester (Rochester, NY, 1984).
[23] N. Zilverberg, ”Global minimization for large scale linearly constrained systems”, Ph.D. Thesis, Computer Science Department, University of Minnesota (Minneapolis, MN, 1983).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.