×
Tuy, Hoang

The complementary convex structure in global optimization. (English) Zbl 0787.90091

J. Glob. Optim. 2, No. 1, 21-40 (1992).
Summary: We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...

Cited in 9 Documents

MSC:

90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

generalized rank \(k\) property; specially structured nonconvex global optimization; nonconvex nucleus; complementary convex structure
PDF BibTeX XML Cite
\textit{H. Tuy}, J. Glob. Optim. 2, No. 1, 21--40 (1992; Zbl 0787.90091)
Full Text: DOI

References:

[1] Thach, P. T. (1987), D. C. Sets, D. C. Functions and Systems of Equations, Preprint, Institute of Mathematics, Hanoi. To appear in Mathematical Programming.
[2] Tuy, H. and R., Horst (1991), The Geometric Complementarity Problem and Transcending Stationarity in Global Optimization in ?Applied Geometry and Discrete Mathematics?, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, 341-354. · Zbl 0813.90115
[3] Henderson, J. M. and R. E. Quant (1971), Microeconomic Theory, McGraw-Hill.
[4] Maling, K., S. H. Mueller, and W. R. Heller (1982), On Finding Most Optimal Rectangular Package Plans, Proceedings of the 19th Design Automation Conference, 663-670.
[5] Konno, H. and M., Inori (1988), Bon Portfolio Optimization by Bilinear Fractional Programming, J. of Oper. Res. of Japan 32, 143-158. · Zbl 0675.90011
[6] Paradalos, P. M. (1988), Polynomial Time Algorithms for Some Classes of Constrained Non-Convex Quadratic Problems, Preprint, Computer Science Department, the Pennsylvania State University.
[7] Forgo, F. (1975), The Solution of a Special Quadratic Problem, Szigma, 53-59 (in Hungarian). · Zbl 0302.90044
[8] Gabasov, R. and F. M. Kirillova (1980), Linear Programming Methods, Part 3 (Special Problems), Minsk (in Russian). · Zbl 0484.90067
[9] Pardalos, P. M. (1988), On the Global Minimization of the Product of Two Linear Functions over a Polytope, Preprint, Computer Science Department, The Pennsylvania State University.
[10] Konno H. and T. Kuno (1989), Linear Multiplicative Programming, IHSS Report 89-13, Institute of Human and Social Sciences, Tokyo Institute of Technology. · Zbl 0761.90080
[11] Tuy, H. and B. T. Tam (1990), An Efficient Solution Method for Rank Two Quasiconcave Minimization Problems, to appear in Optimization. · Zbl 0817.90079
[12] Idrissi, H., P., Loridan, and C., Michelot (1988), Approximation of Solutions for Location Problems, Journal of Optimization Theory and Applications 56, 127-143. · Zbl 0616.90036
[13] Tuy, H. and Faiz A. Al-Khayyal (1991), A Class of Global Optimization Problems Solvable by Sequential Unconstrained Convex Minimization, to appear in C. Floudas and P. Pardalos (eds), Recent Advances in Global Optimization, Princeton University Press.
[14] Ben-Ayed, O. and C. E., Blair (1990), Computational Difficulties of Bilevel Linear Programming, Operations Research 38, 556-560. · Zbl 0708.90052
[15] Tuy, H., A. Migdalas, and P. Värbrand (1990), A Global Optimization Approach for the Linear Two Level Program, Preprint, Department of Mathematics, Linköping University (submitted). · Zbl 0771.90108
[16] Tuy, H. (1990), On Polyhedral Annexation Method for Concave Minimization, in Lev, J. Leifman (ed.), Functional Analysis, Optimization, and Mathematical Economics (volume dedicated to the memory of Kantorovich), Oxford University Press, New York, 248-260. · Zbl 0989.90546
[17] Konno, H. (1976), A Cutting Plane Algorithm for Solving Bilinear Programs, Mathematical Programming 11, 14-27. · Zbl 0353.90069
[18] Tuy, H. (1987), Convex Programs with an Additional Reverse Convex Constraint, Journal of Optimization Theory and Applications 52, 463-485. · Zbl 0585.90071
[19] Tuy, H. (1991), Polyhedral Annexation, Dualization, and Dimension Reduction Technique in Global Optimization, Journal of Global Optimization, 1, 229-244. · Zbl 0752.90077
[20] Thach, P. T. (1991), Quasiconjugates of Functions and Duality Correspondence between Quasiconcave Minimization under a Reverse Convex Constraint and Quasi Convex Maximization under a Convex Constraint, Journal of Mathematical Analysis and Applications. · Zbl 0734.90073
[21] Thach, P. T., and R. E. Burkard (1990), Reverse Convex Programs Dealing with the Product of Two Linear Functions, Preprint, Institute of Mathematics, Graz Technical University.
[22] Thach, P. T. and H., Tuy (1990), Dual Solution Methods for Concave Programs and Reverse Convex Programs, Preprint, IHSS, Tokyo, Institute of Technology.
[23] Horst, R. and H. Tuy (1990), Global Optimization (Deterministic Approaches), Springer-Verlag. · Zbl 0704.90057
[24] Kuno, T. and H. Konno (1990), Parametric Successive Underestimation Method for Convex Multiplicative Programming Problems, Preprint IHSS, Tokyo Institute of Technology. · Zbl 0752.90057
[25] Konno H. and T. Kuno (1991), Generalized Linear Multiplicative and Fractional Programming, to appear in Annals of Operations Research.
[26] Rockafella, R. T. (1970), Convex Analysis, Princeton University Press.
[27] Horst, R., N. V., Thoai, and J.de, Vries (1988), On Finding New Vertices and Redundant Constraints in Cutting Plane Algorithms for Global Optimization, Operations Research Letters 7, 85-90. · Zbl 0644.90085
[28] Tuy, H. (1991), Normal Conical Algorithm for Concave Minimization over Polytopes, Mathematical Programming, 51, 229-245. · Zbl 0743.90103
[29] Falk, J. E. (1973), A Linear Max-Min Problem, Mathematical Programming 5, 169-188. · Zbl 0276.90053
[30] Tuy, H. and N. V., Thuong (1988), On the Global Minimization of a Convex Function under General Nonconvex Constraints, Applied Mathematics and Optimization 18, 119-142. · Zbl 0657.90083
[31] Kuno T. and H. Konno (1990), A Parametric Successive Underestimation Method for Convex Programming Problems with an Additional Convex Multiplicative Constraint, Preprint, IHSS, Tokyo Institute of Technology. · Zbl 0780.90075
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.