连续与离散单调优化和不定二次规划算法研究
|
摘要
全局优化问题主要研究如何寻找一个非凸优化问题的全局最优解．随着社会的进步以及科学技术的发展，全局最优化广泛应用于企业生产管理、金融工程、工程设计及控制、交通运输、农业预测、国防军事等重要领域．因此研究全局优化问题在理论和应用方面都有重要的意义．
本论文主要研究两类特殊结构的全局优化问题——单调优化和不定二次规划．单调优化是指目标函数和约束函数都是单调函数的全局优化问题．把单调优化问题中的变量取值限制为整数，即为离散单调优化问题(通常也称为多维不可分离背包问题)．单调优化问题的目标函数和约束函数不要求是凸的或是可分离的．不定二次规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次函数的全局优化问题．把不定二次规划问题中的变量取值限制为整数，即为整数(离散)不定二次规划问题．本文将着重研究带线性约束的连续和离散不定二次规划问题．
本论文分为七章，各章内容简要介绍如下：
第一章给出了单调优化和不定二次规划及其离散问题的描述及一些应用模型，同时对本论文的主要工作作了简要介绍．
第二章首先介绍了一般全局优化的基本算法，然后介绍文献中连续和离散单调优化及不定二次规划的现有算法．
第三章给出了一个求解单调优化问题的精确算法．该算法的框架是分枝定界，并且与区域剖分、凸化、局部搜索三种基本策略相结合．区域剖分就是把区域剖分成若干个子箱的并集，而且这些子箱的并集覆盖了可行域的边界；在每个子箱上使用凸化外逼近方法得到目标函数最优值的上界；再结合局部搜索改进下界．我们对该算法进行了数值实验，数值实验结果表明该算法是有效的，能在合理的时间内求解中小规模的单调优化问题．
第四章对离散型的单调优化问题进行研究，提出了一个离散的Polyblock算法，并且在此基础上结合凸化思想，对离散Polyblock算法进行改进，提高了界的质量，从而提高算法效率．数值实验结果表明两个算法是有效的，而且数值比较结果表明改进后的算法对具有较大区域的问题计算效果优于改进前的离散Polyblock算法．
第五章给出了一个求不定二次规划问题全局最优解的新算法．首先我们给出了不定二次规划问题的三种下界的确定方法：线性逼近、拉格朗日对偶松弛和凸松弛．然后利用这些下界并结合超长方形的两分法建立一个分枝定界算法．而且我们还证明了经正交变换所得的不定二次可分离问题的凸松弛与拉格朗日对偶松弛是等价的．数值实验结果表明该算法是有效的．
第六章给出了不定二次整数规划问题的几种新的下界并且证明了它们之间的关系．首先我们构造了问题的线性下方估计，以及通过D．C．分解构造了问题的两种凸松弛；然后通过矩阵的Cholesky分解把不定二次整数规划化为等价的可分离问题，进而应用对偶分解导出两种拉格朗日对偶界，并建立了凸松弛界和拉格朗日对偶界的关系．本章提出的某些下界估计方法也可以应用到求(连续)不定二次规划问题的算法中．
最后，我们在第七章总结了本文的主要工作，并讨论了有待进一步研究的问题．
Global optimization aims to find the global optimal solution of a nonconvex optimization problem. With the progress of the modern society and the development of science and technology, global optimization plays an important role in many fields, such as production planning and management, financial engineering, engineering design and control, traffic transportation, agricultural forecast, national defence and so on. The significance of the algorithmic studies on global optimization is therefore evident.
In this thesis, two classes of global optimization problems with special structures are studied: monotone optimization problem and indefinite quadratic programming problem. Monotone optimization deals with the problems of optimizing a monotone function subject to monotone constraints. Discrete monotone optimization problem is a monotone optimization problem with all variables restricted to integers. Such problems are also referred to as multi-dimensional nonseparable knapsack problems. The objective function and the constraint functions of a monotone optimization problem are not necessarily convex or separable. Indefinite quadratic programming deals with the problems of optimizing an indefinite quadratic function subject to linear constraints or quadratic constraints. Indefinite quadratic integer (discrete) programming is an indefinite quadratic programming with all variables restricted to integers. In this thesis, we focus on continuous and discrete indefinite quadratic programming with linear constraints.
This thesis consists of seven chapters. In Chapter 1, monotone optimization problem, indefinite quadratic programming problem and their discrete versions are formally described. Several examples of applications of continuous and discrete monotone optimization and indefinite quadratic programming are presented. Finally, the main contributions of the thesis are briefly introduced in this chapter.
In Chapter 2, some basic solution algorithms for general global optimization problems are first introduced. We then give literature survey of algorithms for continuous and discrete monotone optimization problems and indefinite quadratic programming problems.
In Chapter 3, a new exact method for monotone optimization problems is proposed. The method is of branch-and-bound framework that combines three basic strategies: partition, convexification and local search. The partition scheme is used to construct a union of subboxes that covers the boundary of the feasible region. The convexification outer approximation is then applied to each subbox to obtain an upper bound of the objective function on the subbox. The performance of the method can be further improved by incorporating the method with local search procedure. The numerical results show the feasibility and effectiveness of the proposed algorithm, and the algorithm can solve medium size monotone optimization problems in reasonable time.
In Chapter 4, we study discrete monotone optimization. A discrete polyblock algorithm is first proposed. The polyblock algorithm is then incorporated with convexification method to improve the efficiency of the algorithm. Numerical results show that the two algorithms are effective for discrete monotone optimization problems and the comparison results indicate that the improved algorithm outperforms the discrete polyblock algorithm for the problems with large domain region.
In Chapter 5, we present a new algorithm for finding global solution of indefinite quadratic programming problems. Three lower bounding techniques, linear approximation, Lagrangian dual relaxation and convex relaxation, are derived. A branch-and-bound algorithm based on these lower bounding techniques and rectangular bisection is established. We also show that the convex relaxation of transformed separable indefinite quadratic problem by orthogonal transformation is equivalent to the Lagrangian dual relaxation. Preliminary computational results indicate the effectiveness of the proposed algorithm.
In Chapter 6, several new lower bounds are derived for indefinite quadratic integer programming problems and their relations are established. We first construct convex relaxations by D. C. decomposition and linear underestimation. Cholesky factorization is used to reduce the original problem into the separable problems. Two Lagrangian bounds are then derived by applying dual decomposition schemes to the separable reformulations. Relationships between the convex relaxation bounds and Lagrangian bounds are also established. These underestimation methods are applicable to the algorithms for (continuous) indefinite quadratic programming problems.
Finally, we conclude the thesis in Chapter 7 by summarizing the main results and discussing some possible future research directions.
本论文主要研究两类特殊结构的全局优化问题——单调优化和不定二次规划．单调优化是指目标函数和约束函数都是单调函数的全局优化问题．把单调优化问题中的变量取值限制为整数，即为离散单调优化问题(通常也称为多维不可分离背包问题)．单调优化问题的目标函数和约束函数不要求是凸的或是可分离的．不定二次规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次函数的全局优化问题．把不定二次规划问题中的变量取值限制为整数，即为整数(离散)不定二次规划问题．本文将着重研究带线性约束的连续和离散不定二次规划问题．
本论文分为七章，各章内容简要介绍如下：
第一章给出了单调优化和不定二次规划及其离散问题的描述及一些应用模型，同时对本论文的主要工作作了简要介绍．
第二章首先介绍了一般全局优化的基本算法，然后介绍文献中连续和离散单调优化及不定二次规划的现有算法．
第三章给出了一个求解单调优化问题的精确算法．该算法的框架是分枝定界，并且与区域剖分、凸化、局部搜索三种基本策略相结合．区域剖分就是把区域剖分成若干个子箱的并集，而且这些子箱的并集覆盖了可行域的边界；在每个子箱上使用凸化外逼近方法得到目标函数最优值的上界；再结合局部搜索改进下界．我们对该算法进行了数值实验，数值实验结果表明该算法是有效的，能在合理的时间内求解中小规模的单调优化问题．
第四章对离散型的单调优化问题进行研究，提出了一个离散的Polyblock算法，并且在此基础上结合凸化思想，对离散Polyblock算法进行改进，提高了界的质量，从而提高算法效率．数值实验结果表明两个算法是有效的，而且数值比较结果表明改进后的算法对具有较大区域的问题计算效果优于改进前的离散Polyblock算法．
第五章给出了一个求不定二次规划问题全局最优解的新算法．首先我们给出了不定二次规划问题的三种下界的确定方法：线性逼近、拉格朗日对偶松弛和凸松弛．然后利用这些下界并结合超长方形的两分法建立一个分枝定界算法．而且我们还证明了经正交变换所得的不定二次可分离问题的凸松弛与拉格朗日对偶松弛是等价的．数值实验结果表明该算法是有效的．
第六章给出了不定二次整数规划问题的几种新的下界并且证明了它们之间的关系．首先我们构造了问题的线性下方估计，以及通过D．C．分解构造了问题的两种凸松弛；然后通过矩阵的Cholesky分解把不定二次整数规划化为等价的可分离问题，进而应用对偶分解导出两种拉格朗日对偶界，并建立了凸松弛界和拉格朗日对偶界的关系．本章提出的某些下界估计方法也可以应用到求(连续)不定二次规划问题的算法中．
最后，我们在第七章总结了本文的主要工作，并讨论了有待进一步研究的问题．
Global optimization aims to find the global optimal solution of a nonconvex optimization problem. With the progress of the modern society and the development of science and technology, global optimization plays an important role in many fields, such as production planning and management, financial engineering, engineering design and control, traffic transportation, agricultural forecast, national defence and so on. The significance of the algorithmic studies on global optimization is therefore evident.
In this thesis, two classes of global optimization problems with special structures are studied: monotone optimization problem and indefinite quadratic programming problem. Monotone optimization deals with the problems of optimizing a monotone function subject to monotone constraints. Discrete monotone optimization problem is a monotone optimization problem with all variables restricted to integers. Such problems are also referred to as multi-dimensional nonseparable knapsack problems. The objective function and the constraint functions of a monotone optimization problem are not necessarily convex or separable. Indefinite quadratic programming deals with the problems of optimizing an indefinite quadratic function subject to linear constraints or quadratic constraints. Indefinite quadratic integer (discrete) programming is an indefinite quadratic programming with all variables restricted to integers. In this thesis, we focus on continuous and discrete indefinite quadratic programming with linear constraints.
This thesis consists of seven chapters. In Chapter 1, monotone optimization problem, indefinite quadratic programming problem and their discrete versions are formally described. Several examples of applications of continuous and discrete monotone optimization and indefinite quadratic programming are presented. Finally, the main contributions of the thesis are briefly introduced in this chapter.
In Chapter 2, some basic solution algorithms for general global optimization problems are first introduced. We then give literature survey of algorithms for continuous and discrete monotone optimization problems and indefinite quadratic programming problems.
In Chapter 3, a new exact method for monotone optimization problems is proposed. The method is of branch-and-bound framework that combines three basic strategies: partition, convexification and local search. The partition scheme is used to construct a union of subboxes that covers the boundary of the feasible region. The convexification outer approximation is then applied to each subbox to obtain an upper bound of the objective function on the subbox. The performance of the method can be further improved by incorporating the method with local search procedure. The numerical results show the feasibility and effectiveness of the proposed algorithm, and the algorithm can solve medium size monotone optimization problems in reasonable time.
In Chapter 4, we study discrete monotone optimization. A discrete polyblock algorithm is first proposed. The polyblock algorithm is then incorporated with convexification method to improve the efficiency of the algorithm. Numerical results show that the two algorithms are effective for discrete monotone optimization problems and the comparison results indicate that the improved algorithm outperforms the discrete polyblock algorithm for the problems with large domain region.
In Chapter 5, we present a new algorithm for finding global solution of indefinite quadratic programming problems. Three lower bounding techniques, linear approximation, Lagrangian dual relaxation and convex relaxation, are derived. A branch-and-bound algorithm based on these lower bounding techniques and rectangular bisection is established. We also show that the convex relaxation of transformed separable indefinite quadratic problem by orthogonal transformation is equivalent to the Lagrangian dual relaxation. Preliminary computational results indicate the effectiveness of the proposed algorithm.
In Chapter 6, several new lower bounds are derived for indefinite quadratic integer programming problems and their relations are established. We first construct convex relaxations by D. C. decomposition and linear underestimation. Cholesky factorization is used to reduce the original problem into the separable problems. Two Lagrangian bounds are then derived by applying dual decomposition schemes to the separable reformulations. Relationships between the convex relaxation bounds and Lagrangian bounds are also established. These underestimation methods are applicable to the algorithms for (continuous) indefinite quadratic programming problems.
Finally, we conclude the thesis in Chapter 7 by summarizing the main results and discussing some possible future research directions.
引文
[1] 郑权，蒋百川，庄松林．一个求总极值的方法．应用数学学报，1：161-173，1978．
[2] 张贤达．矩阵分析与应用．清华大学出版社，北京，2004．
[3] J. A. Abraham. An improved algorithm for network reliability. IEEE Transactions on Reliability, 28:58-61, 1979.
[4] F. A. Al-Khayyal and J. E. Falk. Jointly constrained biconvex programming. Mathematics of Operations Research, 8:273-286, 1983.
[5] F. A. Al-Khayyal, R. Horst, and P. M. Pardalos. Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming. Annals of Operations Research, 34: 125-147, 1992.
[6] L. T. Hoai An and P. D. Tao. Solving a class of linearly constrained indefinite quadratic problems by D. C. algorithms. Journal of Global Optimization, 11:253-285, 1997.
[7] L. T. Hoai An and P. D. Tao. A branch and bound method via D. C. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. Journal of Global Optimization, 13:171-206, 1998.
[8] C. Audet, P. Hansen, B. Jaumard, and G. Savard. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Mathematical Programming, 87:131-152, 2000.
[9] D. P. Baron. Quadratic programming with quadratic constraints. Naval Research Logistics Quarterly, 19: 253-260, 1972.
[10] O. Barrientos and R. Correa. An algorithm for global minimization of linearly constrained quadratic functions. Journal of Global Optimization, 16(1):77-93, 2000.
[11] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. Wiley, New York, 1993.
[12] A. Ben-Tal, G. Eiger, and V. Gershovitz. Global optimization by reducing the duality gap. Mathematical Programming, Ser. A, 63: 193-212, 1994.
[13] J. F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numer. Math., 4:238-253, 1962.
[14] H. P. Benson. Deterministic algorithms for constrained concave minimization: A unified critical survey. Naval Research Logistics, 43: 765-795, 1996.
[15] D. P. Bertsekas. Nonlinear Programming, 2nd ed. Athena Scientific, Belmont, Massachusetts, 1999.
[16] A. Birolini. Reliability Engineering: Theory and Practice. Springer-Verlag, New York, 1999.
[17] I. M. Bomze. Branch and bound approaches to standard quadratic optimization problems. Journal of Global Optimization, 22: 17-37, 2002.
[18] K. M. Bretthauer and B. Sherry. The nonlinear resource allocation problem. Operations Research, 43: 670-683, 1995.
[19] A. Caprara, D. Pisinger, and P. Toth. Exact solution of the quadratic knapsack problem. INFORMS Journal on Computing, 11: 125-139, 1999.
[20] M. W. Carter. The indefinite zero-one quadratic problem. Discrete Applied Mathematics, 7: 23-44, 1984.
[21] P. C. Chen, P. Hansen, and B. Jaumard. On-line and off-line vertex enumeration by adjacency lists. Operations Research Letters, 10:403-409, 1991.
[22] S. H. Chew and Q. Zheng. Integral Global Optimization, volume 298 of Lecture Notes in Economics and Mathematical Systems. Springer, New York, 1988.
[23] M. J. Ciesielski and E. Kinnen. An analytical method for compacting routing area in integrated circuits. In Proceedings of 19th Conference on Design Automation, pages 30-37, Las Vegas, NV, 1982.
[24] T. F. Coleman and L. A. Hulbert. A direct active set algorithm for large sparse quadratic programs with simple bounds. Mathematical Programming, 45: 373-406, 1989.
[25] M. Dür and R. Horst. Lagrange duality and partitioning techniques in nonconvex global optimization. Journal of Optimization Theory and Application, 95:347-369, 1997.
[26] S. S. Erenguc and H. P. Benson. An algorithm for indefinite integer quadratic programming. Computers and Mathematics with Applications, 21: 99-106, 1991.
[27] J. E. Falk and K. L. Hoffman. A successive underestimating method for concave minimization problems. Mathematics of Operations Research, 1: 251-259, 1976.
[28] M. L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27: 1-18, 1981.
[29] C. A. Floudas, A. Aggarwal, and A. R. Ciric. Global optimum search for nonconvex NLP and MINLP problems. Computers and Chemical Engineering, 13(10): 1117- 1132, 1989.
[30] C. A. Floudas and V. Visweswaran. A global optimization algorithm(GOP) for certain classes of nonconvex NLPs-Ⅰ. Theory. Computers and Chemical Engineering, 14:1397-1417, 1990.
[31] C. A. Floudas and V. Visweswaran. A primal-relaxed dual global optimization approach. Journal of Optimization Theory and Appplications, 78(2):187-225, 1993.
[32] C. A. Floudas and V. Visweswaran. Quadratic optimization. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, pages 217-269. Kluwer Academic Publishers, 1995.
[33] R. P. Ge. A filled function method for finding a global minimizer of a function of several variables. Mathematical Programming, 46: 191-204, 1990.
[34] R. P. Ge and Y. F. Qin. A class of filled functions for finding a global minimizer of a function of several variables. Journal of Optimization Theory and Application, 54(2): 241-252, 1987.
[35] A. M. Geoffrion. Duality in nonlinear programming: A simplified applicationorientes development. SIAM Review, 13: 1-37, 1971.
[36] A. M. Geoffrion. Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10: 237-260, 1972.
[37] A. M. Geoffrion. Lagrangian relaxation for integer programming. Mathematical Programming Study, 2: 82-114, 1974.
[38] P. E. Gill and W. Murray. Numerically stable methods for quadratic programming. Mathematical Programming, 14: 349-372, 1978.
[39] L. Grippo and S. Lucidi. A differentiable exact penalty function for bound constrained quadratic programming problems. Optimization, 22: 557-578, 1991.
[40] O. K. Gupta and A. Ravindran. Branch-and-bound experiments in convex nonlinear integer programming. Management Science, 31:1533-1546, 1985.
[41] P. L. Hammer and Jr. D. J. Rader. Efficient methods for solving quadratic 0-1 knapsack problems. INFOR, 35: 170-182, 1997.
[42] C. G. Han, P. M. Pardalos, and Y. Ye. Computational aspects of an interior point algorithm for quadratic programming problems with box constraints. In T. F. Coleman and Y. Li, editors, Large-Scale Numerical Optimization, pages 92-112. SIAM Publications, Philadelphia, PA, 1990.
[43] C. G. Han, P. M. Pardalos, and Y. Ye. On the solution of indefinite quadratic problems using an interior point algorithm. Informatica, 3:474-496, 1992.
[44] P. Hansen, B. Jaumard, and S. H. Lu. An analytical approach to global optimization. Mathematical Programming, 52:227-241, 1991.
[45] D. Hochbaum. A nonlinear knapsack problem. Operations Research Letter, 17:103-110, 1995.
[46] K. L. A. Hoffman. A method for globally minimizing concave functions over convex set. Mathematical Programming, 20:22-32, 1981.
[47] R. Horst. An algorithm for nonconvex programming problems. Mathematical Programming, 10:312-321, 1976.
[48] R. Horst. A new branch and bound approach for concave minimization problems. Lecture Notes in Computer Science, 41:330-337, 1976.
[49] R. Horst. On the convexification of nonlinear programming problems: An applications-oriented survey. European Journal of Operations Research, 15:382-392, 1984.
[50] R. Horst. On the global minimization of concave functions, introduction and survey. Operations Research Spektrum, 6:195-205, 1984.
[51] R. Horst. A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. Journal of Optimization Theory and Applications, 51:271-291, 1986.
[52] R. Horst. Deterministic methods in constrained global optimization: Some recent advance and new fields of application. Naval Research Logistics, 37:433-471, 1990.
[53] R. Horst and J. de Vries. On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. Operations Research Letters, 7:85-90, 1988.
[54] R. Horst and P. M. Pardalos. Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.
[55] R. Horst, P. M. Pardalos, and N. V. Thoai. Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.
[56] R. Horst and N. V. Thoai. A new algorithm for solving the general quadratic programming problem. Computational Optimization and Applications, 5:39-49, 1996.
[57] R. Horst and N. Vo Thoai. D. C. programming: Overview. Journal of Optimization Theory and Applications, 103:1-43, 1999.
[58] R. Horst and H. Tuy. Global Optimization: Deterministic Approaches. Springer-Verlag, Heidelberg., 1993.
[59] T. Ibaraki and N. Katoh. Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, Mass., 1988.
[60] N. J. Jobst, M. D. Horniman, C. A. Lucas, and G. Mitra. Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitive Finance, 1: 489-501, 2001.
[61] G. Kedem and H. Watanabe. Graph-optimization techniques for IC layout and compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 3:12-20, 1984.
[62] S. Kim and M. Kojima. Second order cone programming relaxation methods of nonconvex quadratic optimization problems. Optimization Methods and Software, 15:201-224, 2001.
[63] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.
[64] K. Kleibohm. Bemerkungen zum problem der nichtkonvex programmierung (remarks on the nonconvex programming problem). Unternehmensf., 11: 49-60, 1967.
[65] M. S. Kodialam and H. Luss. Algorithm for separable nonlinear resource allocation problems. Operations Research, 46:272-284, 1998.
[66] P. L. Kough. The indefinite quadratic programming problem. Operations Research, 27(3):516-533, 1979.
[67] A. V. Levy and A. Montalvo. The tunneling algorithm for the global minimization of functions. SIAM Journal on Scientific and Statistical Computing, 6(1):15-29, 1985.
[68] D. Li. Convexification of noninferior frontier. Journal of Optimization Theory and Applications, 88:177-196, 1996.
[69] D. Li and X. L. Sun. Local convexification of Lagrangian function in nonconvex optimization. Journal of Optimization Theory and Applications, 104:109-120, 2000.
[70] D. Li and X. L. Sun. Nonlinear Integer Programming. Springer, New York, 2006.
[71] D. Li, X. L. Sun, M. P. Biswal, and F. Gao. Convexification, concavification and monotonization in global optimization. Annals of Operations Research, 105:213-226, 2001.
[72] D. Li, X. L. Sun, and K. McKinnon. An exact solution method for reliability optimization in complex systems. Annals of Operations Research, 133:129-148, 2005.
[73] D. Li, X. L. Sun, and F. L. Wang. Convergent Lagrangian and contour-cut method for nonlinear integer programming with a quadratic objective function. SIAM Journal on Optimization, 17:372-400, 2006.
[74] D. Li, X. L. Sun, and J. Wang. Optimal lot solution to cardinality constrained meanvariance formulation for portfolio selection. Mathematical Finance, 16:83-101, 2006.
[75] D. Li, Z. Y. Wu, H. W. J. Lee, X. M. Yang, and L. S. Zhang. Hidden convex minimization. Journal of Global Optimization, 31(2):211-233, 2005.
[76] J. Linderoth. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Mathematical programming, Ser.B,44(1):251-282, 2005.
[77] X. Liu. Finding global minima with a computable filled function. Journal of Global Optimization, 19:151-161, 2001.
[78] K. Maling, W. R. Heller, and S. H. Mueller. On finding most optimal rectangular package plans. In Proceedings of 19th Conference on Design Automation, pages 663-670, Las Vegas, NV, 1982.
[79] R. E. Marsten and T. L. Morin. A hybrid approach to discrete mathematical pro- gramming. Mathematical Programming, 14:21-40, 1978.
[80] R. D. Mcbride and J. S. Yormark. An implicit enumeration algorithm for quadratic integer programming. Management Science, 26: 282-296, 1980.
[81] C. K. Ng, L. S. Zhang, D. Li, and W. W. Tian. Discrete filled function method for discrete global optimization. Computation Opimization and Application, 31:87-115, 2005.
[82] E. M. Oblow. A stochastic tunneling algorithm for global optimization. Journal of Global Optimization, 20:195-212, 2001.
[83] P. Papalambros and D. J. Wilde. Principles of Optimal Design-Modeling and Computation. Cambridge University Press, Cambridge, UK, New York, 1986.
[84] P. M. Pardalos. Global optimization algorithm for linearly constrained indefinite quadratic problems. Computational Mathematics and Applications, 21:87-97, 1991.
[85] P. M. Pardalos, J. H. Glick, and J. B. Rosen. Global minimization of indefinite quadratic problems. Computing, 39:281-291, 1987.
[86] P. M. Pardalos and G. P. Rodgers. Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing, 45:131-144, 1990.
[87] P. M. Pardalos and J. B. Rosen. Methods for global concave minimization: A bibliographic survey. SIAM Review, 28:367-379, 1986.
[88] P. M. Pardalos and J. B. Rosen. Constrained Global Optimization: Algorithms and Applications. Springer-Verlag, Berlin, 1987.
[89] P. M. Pardalos and G. Schnitger. Checking local optimality in constrained quadratic programming is NP-hard. Operations Research Letters, 7:33-35, 1995.
[90] P. M. Pardalos and S. A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard. Journal of Global Optimization, 1: 843-855, 1991.
[91] A. T. Phillips and J. B. Rosen. Guaranteed ε-approximate solution for indefinite quadratic global minimization. Naval Research Logistics, 37:499-514, 1990.
[92] U. Raber. A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. Journal of Global Optimization, 13: 417-432, 1998.
[93] U. Raber. Nonconvex all-quadratic global optimization problems: Solution Methods, Application and Related Topics. PhD thesis, Universitat Trier, Germany, 1999.
[94] A. H. G. Rinnoy and G. T. Timmer. Stochastic global optimization methods, part Ⅰ: Clustering methods. Mathematical Programming, 39:27-56, 1987.
[95] A. H. G. Rinnoy and G. T. Timmer. Stochastic global optimization methods, part Ⅱ: Multi-level methods. Mathematical Programming, 39:57-78, 1987.
[96] R. T. Rockafellar. Convex Analysis. Prentice Hall, 1970.
[97] J. B. Rosen and P. M. Pardalos. Global minimization of large-scale constrained concave quadratic problems by separable programming. Mathematical Programming, 34:163-174, 1986.
[98] A. Rubinov, H. Tuy, and H. Mays. An algorithm for monotonic global optimization problems. Optimization, 49:205-221, 2001.
[99] N. Z. Shor and P. I. Stetsyuk. Lagrangian bounds in multiextremal polynomial and discrete optimization problems. Journal of Global Optimization, 23:1-47, 2002.
[100] R. Stern and H. Wolkowicz. Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM Journal on Optimization, 5:286-313, 1995.
[101] X. L. Sun and J. L. Li. A branch-and-bound based method for solving monotone optimization problems. Journal of Global Optimization, 35:367-385, 2006.
[102] X. L. Sun, H. Z. Luo, and D. Li. Convexification method for semismooth monotone optimization. Technical report, Shanghai University, 2006. Accepted for publication by Journal of Optimization Theory and Application.
[103] X. L. Sun, K. I. M. McKinnon, and D. Li. A convexification method for a class of global optimization problems with applications to reliability optimization. Journal of Global Optimization, 21:185-199, 2001.
[104] S. S. Syam. A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals. European Journal of Operational Research, 108:196-207, 1998.
[105] P. D. Tao and L. T. Hoai An. A D. C. optimization for solving the trust-region subproblem. SIAM Journal on Optimization, 8(2):476-505, 1998.
[106] T. V. Thieu, B. T. Tam, and V. T. Ban. An outer approximation method for globally minimizing a concave function over a compact convex set. Acta. Math. Vietna, 8:21-40, 1983.
[107] N. V. Thoai. Global optimization technique for solving the general quadratic integer programming problem. Computational Optimization and Applications, 10:149-163, 1998.
[108] N. V. Thoai and H. Tuy. Convergent algorithms for minimizing a concave function. Mathematics of Operations Research, 5:556-566, 1980.
[109] F. A. Tillman, C. L. Hwuang, and W. Kuo. Optimization of System Reliability. Marcel Dekker, 1980.
[110] H. Tuy. Concave programming under linear constraints. Soviet Mathematics, 5:1437-1440, 1964.
[111] H. Tuy. D. C. optimization: Theory, methods and algorithms. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, pages 149-216. Kluwer Academic Publishers, Dordrecht, 1995.
[112] H. Tuy. Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrecht, 1998.
[113] H. Tuy. Monotonic optimization: problems and solution approaches. SIAM Journal on Optimization, 11: 464-494, 2000.
[114] H. Tuy, V. Khachaturov, and S. Utkin. A class of exhaustive cone splitting procedures in conical algorithms for concave minimization. Optimization, 18:791-807, 1987.
[115] H. Tuy and L. T. Luc. A new approach to optimization under monotonic constraint. Journal of Global Optimization, 18:1-15, 2000.
[116] S. G. Tzafestas. Optimization of system reliability: A survey of problems and techniques. Int. J. Syst. Sci., 11:455-486, 1980.
[117] D. Vandenbussche and G. L. Nemhauser. A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Mathematical Programming, 102:559-575, 2005.
[118] D. Vandenbussche and G. L. Nemhauser. A polyhedral study of nonconvex quadratic programs with box constraints. Mathematical Programming, 102:531-557, 2005.
[119] V. Visweswaran and C. A. Floudas. A global optimization algorithm(GOP) for certain classes of nonconvex NLPs-Ⅱ: Application of theory and test problems. Computers and Chemical Engineering, 14:1419-1434, 1990.
[120] Z. Y. Wu, F. S. Bai, and L. S. Zhang. Convexification and concavification for a general class of global optimization problems. Journal of Global Optimization, 31: 45-60, 2005.
[121] Z. Xu, H. X. Huang, and P. M. Pardalos. Filled functions for unconstrained global optimization. Journal of Global Optimization, 20:49-65, 2001.
[122] Y. Yajima and T. Fujie. A polyhedral approach for nonconvex quadratic programming problems with box constraints. Journal of Global Optimization, 13:151-170, 1998.
[123] Y. Yao. Dynamic tunneling algorithm for global optimization. IEEE Transactions on Systems, Man and Cybernetics, 5:1222-1230, 1989.
[124] Y. Ye. Interior-point algorithms for global optimization. Annual Operations Research, 25:59-74, 1990.
[125] L. S. Zhang, C. K. Ng, D. Li, and W. W. Tian. A new filled function method for global optimization. Journal of Global Optimization, 28:17-43, 2004.
[126] Q. Zheng and L. S. Zhang. Global minimization of constrained problems with discontinuous penalty function. Journal of Computers and Mathematics with applications, 37:41-58, 1999.
[2] 张贤达．矩阵分析与应用．清华大学出版社，北京，2004．
[3] J. A. Abraham. An improved algorithm for network reliability. IEEE Transactions on Reliability, 28:58-61, 1979.
[4] F. A. Al-Khayyal and J. E. Falk. Jointly constrained biconvex programming. Mathematics of Operations Research, 8:273-286, 1983.
[5] F. A. Al-Khayyal, R. Horst, and P. M. Pardalos. Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming. Annals of Operations Research, 34: 125-147, 1992.
[6] L. T. Hoai An and P. D. Tao. Solving a class of linearly constrained indefinite quadratic problems by D. C. algorithms. Journal of Global Optimization, 11:253-285, 1997.
[7] L. T. Hoai An and P. D. Tao. A branch and bound method via D. C. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. Journal of Global Optimization, 13:171-206, 1998.
[8] C. Audet, P. Hansen, B. Jaumard, and G. Savard. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Mathematical Programming, 87:131-152, 2000.
[9] D. P. Baron. Quadratic programming with quadratic constraints. Naval Research Logistics Quarterly, 19: 253-260, 1972.
[10] O. Barrientos and R. Correa. An algorithm for global minimization of linearly constrained quadratic functions. Journal of Global Optimization, 16(1):77-93, 2000.
[11] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. Wiley, New York, 1993.
[12] A. Ben-Tal, G. Eiger, and V. Gershovitz. Global optimization by reducing the duality gap. Mathematical Programming, Ser. A, 63: 193-212, 1994.
[13] J. F. Benders. Partitioning procedures for solving mixed-variables programming problems. Numer. Math., 4:238-253, 1962.
[14] H. P. Benson. Deterministic algorithms for constrained concave minimization: A unified critical survey. Naval Research Logistics, 43: 765-795, 1996.
[15] D. P. Bertsekas. Nonlinear Programming, 2nd ed. Athena Scientific, Belmont, Massachusetts, 1999.
[16] A. Birolini. Reliability Engineering: Theory and Practice. Springer-Verlag, New York, 1999.
[17] I. M. Bomze. Branch and bound approaches to standard quadratic optimization problems. Journal of Global Optimization, 22: 17-37, 2002.
[18] K. M. Bretthauer and B. Sherry. The nonlinear resource allocation problem. Operations Research, 43: 670-683, 1995.
[19] A. Caprara, D. Pisinger, and P. Toth. Exact solution of the quadratic knapsack problem. INFORMS Journal on Computing, 11: 125-139, 1999.
[20] M. W. Carter. The indefinite zero-one quadratic problem. Discrete Applied Mathematics, 7: 23-44, 1984.
[21] P. C. Chen, P. Hansen, and B. Jaumard. On-line and off-line vertex enumeration by adjacency lists. Operations Research Letters, 10:403-409, 1991.
[22] S. H. Chew and Q. Zheng. Integral Global Optimization, volume 298 of Lecture Notes in Economics and Mathematical Systems. Springer, New York, 1988.
[23] M. J. Ciesielski and E. Kinnen. An analytical method for compacting routing area in integrated circuits. In Proceedings of 19th Conference on Design Automation, pages 30-37, Las Vegas, NV, 1982.
[24] T. F. Coleman and L. A. Hulbert. A direct active set algorithm for large sparse quadratic programs with simple bounds. Mathematical Programming, 45: 373-406, 1989.
[25] M. Dür and R. Horst. Lagrange duality and partitioning techniques in nonconvex global optimization. Journal of Optimization Theory and Application, 95:347-369, 1997.
[26] S. S. Erenguc and H. P. Benson. An algorithm for indefinite integer quadratic programming. Computers and Mathematics with Applications, 21: 99-106, 1991.
[27] J. E. Falk and K. L. Hoffman. A successive underestimating method for concave minimization problems. Mathematics of Operations Research, 1: 251-259, 1976.
[28] M. L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27: 1-18, 1981.
[29] C. A. Floudas, A. Aggarwal, and A. R. Ciric. Global optimum search for nonconvex NLP and MINLP problems. Computers and Chemical Engineering, 13(10): 1117- 1132, 1989.
[30] C. A. Floudas and V. Visweswaran. A global optimization algorithm(GOP) for certain classes of nonconvex NLPs-Ⅰ. Theory. Computers and Chemical Engineering, 14:1397-1417, 1990.
[31] C. A. Floudas and V. Visweswaran. A primal-relaxed dual global optimization approach. Journal of Optimization Theory and Appplications, 78(2):187-225, 1993.
[32] C. A. Floudas and V. Visweswaran. Quadratic optimization. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, pages 217-269. Kluwer Academic Publishers, 1995.
[33] R. P. Ge. A filled function method for finding a global minimizer of a function of several variables. Mathematical Programming, 46: 191-204, 1990.
[34] R. P. Ge and Y. F. Qin. A class of filled functions for finding a global minimizer of a function of several variables. Journal of Optimization Theory and Application, 54(2): 241-252, 1987.
[35] A. M. Geoffrion. Duality in nonlinear programming: A simplified applicationorientes development. SIAM Review, 13: 1-37, 1971.
[36] A. M. Geoffrion. Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10: 237-260, 1972.
[37] A. M. Geoffrion. Lagrangian relaxation for integer programming. Mathematical Programming Study, 2: 82-114, 1974.
[38] P. E. Gill and W. Murray. Numerically stable methods for quadratic programming. Mathematical Programming, 14: 349-372, 1978.
[39] L. Grippo and S. Lucidi. A differentiable exact penalty function for bound constrained quadratic programming problems. Optimization, 22: 557-578, 1991.
[40] O. K. Gupta and A. Ravindran. Branch-and-bound experiments in convex nonlinear integer programming. Management Science, 31:1533-1546, 1985.
[41] P. L. Hammer and Jr. D. J. Rader. Efficient methods for solving quadratic 0-1 knapsack problems. INFOR, 35: 170-182, 1997.
[42] C. G. Han, P. M. Pardalos, and Y. Ye. Computational aspects of an interior point algorithm for quadratic programming problems with box constraints. In T. F. Coleman and Y. Li, editors, Large-Scale Numerical Optimization, pages 92-112. SIAM Publications, Philadelphia, PA, 1990.
[43] C. G. Han, P. M. Pardalos, and Y. Ye. On the solution of indefinite quadratic problems using an interior point algorithm. Informatica, 3:474-496, 1992.
[44] P. Hansen, B. Jaumard, and S. H. Lu. An analytical approach to global optimization. Mathematical Programming, 52:227-241, 1991.
[45] D. Hochbaum. A nonlinear knapsack problem. Operations Research Letter, 17:103-110, 1995.
[46] K. L. A. Hoffman. A method for globally minimizing concave functions over convex set. Mathematical Programming, 20:22-32, 1981.
[47] R. Horst. An algorithm for nonconvex programming problems. Mathematical Programming, 10:312-321, 1976.
[48] R. Horst. A new branch and bound approach for concave minimization problems. Lecture Notes in Computer Science, 41:330-337, 1976.
[49] R. Horst. On the convexification of nonlinear programming problems: An applications-oriented survey. European Journal of Operations Research, 15:382-392, 1984.
[50] R. Horst. On the global minimization of concave functions, introduction and survey. Operations Research Spektrum, 6:195-205, 1984.
[51] R. Horst. A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. Journal of Optimization Theory and Applications, 51:271-291, 1986.
[52] R. Horst. Deterministic methods in constrained global optimization: Some recent advance and new fields of application. Naval Research Logistics, 37:433-471, 1990.
[53] R. Horst and J. de Vries. On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. Operations Research Letters, 7:85-90, 1988.
[54] R. Horst and P. M. Pardalos. Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.
[55] R. Horst, P. M. Pardalos, and N. V. Thoai. Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.
[56] R. Horst and N. V. Thoai. A new algorithm for solving the general quadratic programming problem. Computational Optimization and Applications, 5:39-49, 1996.
[57] R. Horst and N. Vo Thoai. D. C. programming: Overview. Journal of Optimization Theory and Applications, 103:1-43, 1999.
[58] R. Horst and H. Tuy. Global Optimization: Deterministic Approaches. Springer-Verlag, Heidelberg., 1993.
[59] T. Ibaraki and N. Katoh. Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, Mass., 1988.
[60] N. J. Jobst, M. D. Horniman, C. A. Lucas, and G. Mitra. Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitive Finance, 1: 489-501, 2001.
[61] G. Kedem and H. Watanabe. Graph-optimization techniques for IC layout and compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 3:12-20, 1984.
[62] S. Kim and M. Kojima. Second order cone programming relaxation methods of nonconvex quadratic optimization problems. Optimization Methods and Software, 15:201-224, 2001.
[63] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.
[64] K. Kleibohm. Bemerkungen zum problem der nichtkonvex programmierung (remarks on the nonconvex programming problem). Unternehmensf., 11: 49-60, 1967.
[65] M. S. Kodialam and H. Luss. Algorithm for separable nonlinear resource allocation problems. Operations Research, 46:272-284, 1998.
[66] P. L. Kough. The indefinite quadratic programming problem. Operations Research, 27(3):516-533, 1979.
[67] A. V. Levy and A. Montalvo. The tunneling algorithm for the global minimization of functions. SIAM Journal on Scientific and Statistical Computing, 6(1):15-29, 1985.
[68] D. Li. Convexification of noninferior frontier. Journal of Optimization Theory and Applications, 88:177-196, 1996.
[69] D. Li and X. L. Sun. Local convexification of Lagrangian function in nonconvex optimization. Journal of Optimization Theory and Applications, 104:109-120, 2000.
[70] D. Li and X. L. Sun. Nonlinear Integer Programming. Springer, New York, 2006.
[71] D. Li, X. L. Sun, M. P. Biswal, and F. Gao. Convexification, concavification and monotonization in global optimization. Annals of Operations Research, 105:213-226, 2001.
[72] D. Li, X. L. Sun, and K. McKinnon. An exact solution method for reliability optimization in complex systems. Annals of Operations Research, 133:129-148, 2005.
[73] D. Li, X. L. Sun, and F. L. Wang. Convergent Lagrangian and contour-cut method for nonlinear integer programming with a quadratic objective function. SIAM Journal on Optimization, 17:372-400, 2006.
[74] D. Li, X. L. Sun, and J. Wang. Optimal lot solution to cardinality constrained meanvariance formulation for portfolio selection. Mathematical Finance, 16:83-101, 2006.
[75] D. Li, Z. Y. Wu, H. W. J. Lee, X. M. Yang, and L. S. Zhang. Hidden convex minimization. Journal of Global Optimization, 31(2):211-233, 2005.
[76] J. Linderoth. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Mathematical programming, Ser.B,44(1):251-282, 2005.
[77] X. Liu. Finding global minima with a computable filled function. Journal of Global Optimization, 19:151-161, 2001.
[78] K. Maling, W. R. Heller, and S. H. Mueller. On finding most optimal rectangular package plans. In Proceedings of 19th Conference on Design Automation, pages 663-670, Las Vegas, NV, 1982.
[79] R. E. Marsten and T. L. Morin. A hybrid approach to discrete mathematical pro- gramming. Mathematical Programming, 14:21-40, 1978.
[80] R. D. Mcbride and J. S. Yormark. An implicit enumeration algorithm for quadratic integer programming. Management Science, 26: 282-296, 1980.
[81] C. K. Ng, L. S. Zhang, D. Li, and W. W. Tian. Discrete filled function method for discrete global optimization. Computation Opimization and Application, 31:87-115, 2005.
[82] E. M. Oblow. A stochastic tunneling algorithm for global optimization. Journal of Global Optimization, 20:195-212, 2001.
[83] P. Papalambros and D. J. Wilde. Principles of Optimal Design-Modeling and Computation. Cambridge University Press, Cambridge, UK, New York, 1986.
[84] P. M. Pardalos. Global optimization algorithm for linearly constrained indefinite quadratic problems. Computational Mathematics and Applications, 21:87-97, 1991.
[85] P. M. Pardalos, J. H. Glick, and J. B. Rosen. Global minimization of indefinite quadratic problems. Computing, 39:281-291, 1987.
[86] P. M. Pardalos and G. P. Rodgers. Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing, 45:131-144, 1990.
[87] P. M. Pardalos and J. B. Rosen. Methods for global concave minimization: A bibliographic survey. SIAM Review, 28:367-379, 1986.
[88] P. M. Pardalos and J. B. Rosen. Constrained Global Optimization: Algorithms and Applications. Springer-Verlag, Berlin, 1987.
[89] P. M. Pardalos and G. Schnitger. Checking local optimality in constrained quadratic programming is NP-hard. Operations Research Letters, 7:33-35, 1995.
[90] P. M. Pardalos and S. A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard. Journal of Global Optimization, 1: 843-855, 1991.
[91] A. T. Phillips and J. B. Rosen. Guaranteed ε-approximate solution for indefinite quadratic global minimization. Naval Research Logistics, 37:499-514, 1990.
[92] U. Raber. A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. Journal of Global Optimization, 13: 417-432, 1998.
[93] U. Raber. Nonconvex all-quadratic global optimization problems: Solution Methods, Application and Related Topics. PhD thesis, Universitat Trier, Germany, 1999.
[94] A. H. G. Rinnoy and G. T. Timmer. Stochastic global optimization methods, part Ⅰ: Clustering methods. Mathematical Programming, 39:27-56, 1987.
[95] A. H. G. Rinnoy and G. T. Timmer. Stochastic global optimization methods, part Ⅱ: Multi-level methods. Mathematical Programming, 39:57-78, 1987.
[96] R. T. Rockafellar. Convex Analysis. Prentice Hall, 1970.
[97] J. B. Rosen and P. M. Pardalos. Global minimization of large-scale constrained concave quadratic problems by separable programming. Mathematical Programming, 34:163-174, 1986.
[98] A. Rubinov, H. Tuy, and H. Mays. An algorithm for monotonic global optimization problems. Optimization, 49:205-221, 2001.
[99] N. Z. Shor and P. I. Stetsyuk. Lagrangian bounds in multiextremal polynomial and discrete optimization problems. Journal of Global Optimization, 23:1-47, 2002.
[100] R. Stern and H. Wolkowicz. Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. SIAM Journal on Optimization, 5:286-313, 1995.
[101] X. L. Sun and J. L. Li. A branch-and-bound based method for solving monotone optimization problems. Journal of Global Optimization, 35:367-385, 2006.
[102] X. L. Sun, H. Z. Luo, and D. Li. Convexification method for semismooth monotone optimization. Technical report, Shanghai University, 2006. Accepted for publication by Journal of Optimization Theory and Application.
[103] X. L. Sun, K. I. M. McKinnon, and D. Li. A convexification method for a class of global optimization problems with applications to reliability optimization. Journal of Global Optimization, 21:185-199, 2001.
[104] S. S. Syam. A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals. European Journal of Operational Research, 108:196-207, 1998.
[105] P. D. Tao and L. T. Hoai An. A D. C. optimization for solving the trust-region subproblem. SIAM Journal on Optimization, 8(2):476-505, 1998.
[106] T. V. Thieu, B. T. Tam, and V. T. Ban. An outer approximation method for globally minimizing a concave function over a compact convex set. Acta. Math. Vietna, 8:21-40, 1983.
[107] N. V. Thoai. Global optimization technique for solving the general quadratic integer programming problem. Computational Optimization and Applications, 10:149-163, 1998.
[108] N. V. Thoai and H. Tuy. Convergent algorithms for minimizing a concave function. Mathematics of Operations Research, 5:556-566, 1980.
[109] F. A. Tillman, C. L. Hwuang, and W. Kuo. Optimization of System Reliability. Marcel Dekker, 1980.
[110] H. Tuy. Concave programming under linear constraints. Soviet Mathematics, 5:1437-1440, 1964.
[111] H. Tuy. D. C. optimization: Theory, methods and algorithms. In R. Horst and P. M. Pardalos, editors, Handbook of Global Optimization, pages 149-216. Kluwer Academic Publishers, Dordrecht, 1995.
[112] H. Tuy. Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrecht, 1998.
[113] H. Tuy. Monotonic optimization: problems and solution approaches. SIAM Journal on Optimization, 11: 464-494, 2000.
[114] H. Tuy, V. Khachaturov, and S. Utkin. A class of exhaustive cone splitting procedures in conical algorithms for concave minimization. Optimization, 18:791-807, 1987.
[115] H. Tuy and L. T. Luc. A new approach to optimization under monotonic constraint. Journal of Global Optimization, 18:1-15, 2000.
[116] S. G. Tzafestas. Optimization of system reliability: A survey of problems and techniques. Int. J. Syst. Sci., 11:455-486, 1980.
[117] D. Vandenbussche and G. L. Nemhauser. A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Mathematical Programming, 102:559-575, 2005.
[118] D. Vandenbussche and G. L. Nemhauser. A polyhedral study of nonconvex quadratic programs with box constraints. Mathematical Programming, 102:531-557, 2005.
[119] V. Visweswaran and C. A. Floudas. A global optimization algorithm(GOP) for certain classes of nonconvex NLPs-Ⅱ: Application of theory and test problems. Computers and Chemical Engineering, 14:1419-1434, 1990.
[120] Z. Y. Wu, F. S. Bai, and L. S. Zhang. Convexification and concavification for a general class of global optimization problems. Journal of Global Optimization, 31: 45-60, 2005.
[121] Z. Xu, H. X. Huang, and P. M. Pardalos. Filled functions for unconstrained global optimization. Journal of Global Optimization, 20:49-65, 2001.
[122] Y. Yajima and T. Fujie. A polyhedral approach for nonconvex quadratic programming problems with box constraints. Journal of Global Optimization, 13:151-170, 1998.
[123] Y. Yao. Dynamic tunneling algorithm for global optimization. IEEE Transactions on Systems, Man and Cybernetics, 5:1222-1230, 1989.
[124] Y. Ye. Interior-point algorithms for global optimization. Annual Operations Research, 25:59-74, 1990.
[125] L. S. Zhang, C. K. Ng, D. Li, and W. W. Tian. A new filled function method for global optimization. Journal of Global Optimization, 28:17-43, 2004.
[126] Q. Zheng and L. S. Zhang. Global minimization of constrained problems with discontinuous penalty function. Journal of Computers and Mathematics with applications, 37:41-58, 1999.