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

Global minimization of indefinite quadratic problems. (English) Zbl 0627.65072

Computing 39, 281-291 (1987).
A branch and bound algorithm is proposed for finding the global optimum of large-scale indefinite quadratic problems over a polytope. The algorithm uses separable programming and techniques from concave optimization to obtain approximate solutions. Results on error bounding are given and preliminary computational results using the Cray 1 S supercomputer are reported.

Cited in 25 Documents

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming

Keywords:

constrained global optimization; indefinite quadratic programming; branch and bound algorithm; global optimum; large-scale indefinite quadratic problems; concave optimization; error bounding

Software:

MINOS
PDF BibTeX XML Cite
\textit{P. M. Pardalos} et al., Computing 39, 281--291 (1987; Zbl 0627.65072)
Full Text: DOI

References:

[1] Brayton, R. K., Hachtel, G. D., Sangiovanni-Vincentelli, A. L.: A survey of optimization techniques for integrated-circuit design. Proceedings of the IEEE69/10, 1334–1362 (1981).
[2] Ciesielski, M. J., Kinnen, E.: An Analytic Method for Compacting Routing Area in Integrated Circuits. Proceedings of the 19th Design Automation Conference, Las Vegas, NV. (1982) pp. 30–37.
[3] Cirina, M.: A class of nonlinear programming test problems. Working paper, Dipart. di Informatica, Torino (1985).
[4] Crowder, H., Johnson, E. L., Padberg, M. W.: Solving large-scale zero-one linear programming problems. Oper. Res.31/5, 803–834 (1982). · Zbl 0576.90065
[5] Geoffrion, A.: Generalized Bender’s decompositions. J. Optimiz. Theory Applic.10, 237–260 (1972). · Zbl 0229.90024
[6] Kalantari, B.: Large scale concave quadratic minimization and extensions. PhD thesis, Computer Sci. Dept., University of Minnesota (1984).
[7] Kedem, G., Watanabe, H.: Optimization Techniques for IC Layout and Compaction. Proceedings IEEE Intern. Conf. in Computer Design: VLSI in Computers (1983) pp. 709–713.
[8] Kough, P. F.: The indefinite quadratic programming problem. Oper. Res.27/3, 516–533 (1979). · Zbl 0409.90070
[9] Maling, K., Mueller, S. H., Heller, W. R.: On finding most optimal rectangular package plans. Proceedings of the 19th Design Automation Conference, Las Vegas, NV. (1982) pp. 663–670.
[10] Mueller, R. K.: A method for solving the indefinite quadratic programming problem. Manag. Science16/5, 333–339 (1979). · Zbl 0191.48605
[11] Meyer, R. R.: Computational aspects of two-segment separable programming. Math Progr.26, 21–32 (1983). · Zbl 0516.90058
[12] Murtagh, B. A., Saunders, M. A.: MINOS 5.0 User’s Guide. Tech. Rep. SOL 83-20, Dept. of Oper. Res., Stanford Univ. (1983).
[13] Pardalos, P. M.: Integer, and separable programming techniques for large scale global optimization problems. PhD thesis, Computer Sci. Dept, University of Minnesota (1985).
[14] Pardalos, P. M., Rosen, J. B.: Methods for global concave minimization: a bibliographic survey. SIAM Review8/3, 367–379 (1986). · Zbl 0602.90105
[15] Pardalos, P. M., Rosen, J. B.: Global optimization approach to the linear complementarity problem. To appear in SIAM J. Sci. Stat. Computing (1987). · Zbl 0638.90064
[16] Rosen, J. B., Pardalos, P. M.: Global minimization of large scale constrained concave quadratic problems by separable programming. Math. Progr.34, 163–174 (1986). · Zbl 0597.90066
[17] Soukup, J.: Circuit layout. Proceedings of the IEEE.69/10, 1281–1304 (1984).
[18] Thakur, L. S.: Error analysis for convex separable programs: the piecewise linear approximation and the bounds on the optimal objective value. SIAM J. Appl. Math.34/4., 704–714 (1978). · Zbl 0379.90084
[19] Thoai, N. V., Tuy, H.: Solving the linear complementary problem through concave programming. Zh. Vychisl. Mat. i. Mat. Fiz.23/3, 602–608 (1983). · Zbl 0552.90088
[20] Tuy, H.: Global minimization of the difference of two convex functions. In: Selected Topics in Operations Research and Mathematical Economics. Lecture Notes Econ. Math. Syst.226, 98–118 (1984). · Zbl 0559.90071
[21] Watanabe, H.: IC Layout Generation and Compaction Using Mathematical Optimization. Ph. D. thesis Comp. Sci. Dept. Rochester Univ. (1984).
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.