求总极值的某些确定性算法——连续变量和整变量情况
|
摘要
通常一个求总极值问题可以表述为：给定一个n维欧氏空间中的紧致集D(?)R~n，和一个连续函数f：A→R，(A(?)D)寻找一个点x~*∈D，对所有x∈D，满足f(x~*)≤f(x)。记作求总极值问题的方法在科学技术、工程设计、经济管理等方面有着很广泛的应用。本文主要研究讨论某些求总极值的确定性算法。
对一个连续函数而言，“全局信息”包括稠密性、李普希兹常数、一致连续常数、有界的高阶导数、函数的水平集、全局最优值等等。通常我们只能知道函数的一些极限性质和方向导数等“局部信息”，对这些“局部信息”我们已有许多成熟的处理方法，而对“全局信息”至今还没有非常完善的处理方法。一般地，利用“全局信息”构造的算法，大多有比较好的收敛性质；而从“局部”到“全局”的方法，要解决其收敛性一般都较困难。由于“全局”性的要求，使得在求解总极值问题的算法的研究中存在着一定的难度，其主要的难点是：现有的非线性优化的方法一般只能求出局部的最优点，此外，还缺少一个好的评判标准来判定一个局部最优解是否是全局最优解，从而使得那些利用导数、梯度和次梯度求局部最优解的方法难以找到全局最优解。近几十年来，关于求总极值问题的研究取得了一定的进展，
2000年上海大学博士学位论文
Galperin、郑权和Falk分别提出了关于全局解的一个评判标准。
同时许多学者提出了不少求解总极值问题的算法，主要有这样
几种途径:一种是逐次逼近全局解，有外逼近方法、分支定界
方法、区间方法和积分方法等;另一种是从局部解转向全局解，
有隧道函数方法和填充函数方法等.我们将在第一章介绍这几
种求总极值的确定性算法。
郑权提出的求全局优化的积分型方法，有很好的理论性质
和计算效果。但是，其实现算法的收敛性至今没有解决，并被
认为是一个难问题。我们对郑权等提出的积分型求总极值算法
作了修正，讨论了用均值一水平集求总极值的算法，这些算法
既保留了仅需要计算目标函数值的优点，又是一个可实现的具
有全局收敛性的算法。首先，在2.2中我们给出一个离散均值-
水平集求总极值的实现算法，该算法的主要思想是:在函数值
较好的点的邻域中多取点，在函数值较坏的邻域中少取点。同
时给出算法的终止准则，证明了算法的收敛性。然后，在2.3
中给出一个修正的求总极值的积分一水平集算法，该算法在每
一次迭代中，构造一个新函数，它与原目标函数具有相同的总
极值;在算法的实现时，我们用数论中确定性的一致分布的数
值积分来逼近水平值和水平集，且不改变搜索区间，避免了郑
权的实现算法中因用Monte一Carlo方法逼近水平集，并收缩迭
代区间而容易丢失总极值点的弱点;并给出了总极值存在的条
件;证明了实现算法的收敛性。在2.4中讨论了求约束总极值的
算法。最后，在2.5中给出了一些数值例子，说明我们的算法
是有效的。
葛人傅提出的求全局优化填充函数方法，其填充函数有缺
点，如果参数选择不当，会丢失全局最优点，或者用填充函数
求总极值的某些确定性算法
求出的点不是目标函数的较小的极小点。我们给出一类辅助函
数，在适当的条件下，证明了它们是一类填充函数，且是性态
较好的填充函数;并以此构造算法来求一般的非线性规划和非
线性整规划的全局解。在3.2中，我们给出一个仅含一个参数
的填充函数P(x，x*，P);在33中给出另一个填充函数
P(x，二‘，p，川，用它来构造算法，求解非线性规划的总极值;数
值计算表明算法是有效的。对于非线性整规划的总极值问题缺
乏有效的算法，我们试图用填充函数法进行求解，在3.4中，
我们给出一个仅含一个参数的填充函数爪二，，二二’，P);在3.5中
给出另一个填充函数风二，，:;，，p，川，用它来求解非线性整规
划，数值结果表明算法是有效的。
The global optimization problem can be stated as follows: Given a nonempty, closed set D R" and a continuous functionf: A-R, where A R" is a suitable set containing D, find at least one point x * D satisfy ingf(x*) f(x) for all x
i.e.
There are many applications of the nonlinear global optimization in the field of science and technology, optimal design of engineering," economic managenent and so on. In this dissertation, we consider mainly some deterministic methods for solving global optimization problems.
In Chapter 1, a brief introduction is given to the main classes of global optimization problems that can be treated by deterministic methods. Some of these methods are successively to approximate global solution; most prominent examples are the outer approximation, the branch-and-bound method, the interval method and the integral method. Others are developed from the local minimum to the global minimum, such as the tunneling algorithm and the filled function method.
In Chapter 2, we modify Zheng's integral method and propose several algorithms to find the global solution of (P). They are implementable algorithms and have the merit, which only calculate
the values of the objective functions. The following is the organization of Chapter 2. In Section 2.2, we present an algorithm for solving the problem (P) by discrete level set-mean value. The main idea of this algorithm is that, at each iteration, we take more points on some regions in which the values of the function f(x) is smaller than those in other regions, and take fewer points on the regions in which the values of the function f(x) is bigger than those in other regions. In this way the efficiency of computation can be improved. Moreover, the termination rule for discrete level set-mean value is given and the convergence of the algorithm is proved. In Section 2.3, we propose a modified integral-level set algorithm for solving the global optimization. In each iterative process, we construct a new function, which has the same global optimum as that of the primitive function. The algorithm is implemented by applying the deterministic uniform distribution numerical integral in number theory to approach the level value and the level set. Because of not changing the search domain, we can avoide using Zheng's Monte-Carlo implemtable algorithm, which is maybe to lose of the global optimum, to approach the level set. Furthmore, we gain the optimality conditions and prove the convergence of the algorithm. Section 2.4 discusses how to solve the constrained global optimization. Several numerical examples are presented in Section 2.5, the priliminary numerical results show that our algorithms are effective.
In Chapter 3, we construct a class of auxiliary functions which correspond to a class of filled functions, and we propose some algorithms to find the global minimum for the unconstrained
2000
optimization and the nonlinear integer programming. The organization of Chapter 3 is as follows. Section 3.2 discusses a filled function with only one parameter. In Section 3.3 we show how using another filled function to construct an algorithm to solve the global unconstrained optimization. The computational results show that this algorithm is effective. There is no any algorithm for integer programming with quadratic constraints and linear objective function. Therefore, we assume that the domain of function is bounded when nonlinear integer programming is concerned. Even for this case, there is also lack of algorithms to solve it. We proposed an approach for finding the global minimum of nonlinear integer programming. Section 3.4 is devoted to study a filled function p(x1,x1',p)with only one parameter..In Section 3.5,we present the
other filled function p(x/,x*1, p,//) in order to solve the nonlinear
integer programming. The numerical test results show that the
algorithm is also effective.
对一个连续函数而言，“全局信息”包括稠密性、李普希兹常数、一致连续常数、有界的高阶导数、函数的水平集、全局最优值等等。通常我们只能知道函数的一些极限性质和方向导数等“局部信息”，对这些“局部信息”我们已有许多成熟的处理方法，而对“全局信息”至今还没有非常完善的处理方法。一般地，利用“全局信息”构造的算法，大多有比较好的收敛性质；而从“局部”到“全局”的方法，要解决其收敛性一般都较困难。由于“全局”性的要求，使得在求解总极值问题的算法的研究中存在着一定的难度，其主要的难点是：现有的非线性优化的方法一般只能求出局部的最优点，此外，还缺少一个好的评判标准来判定一个局部最优解是否是全局最优解，从而使得那些利用导数、梯度和次梯度求局部最优解的方法难以找到全局最优解。近几十年来，关于求总极值问题的研究取得了一定的进展，
2000年上海大学博士学位论文
Galperin、郑权和Falk分别提出了关于全局解的一个评判标准。
同时许多学者提出了不少求解总极值问题的算法，主要有这样
几种途径:一种是逐次逼近全局解，有外逼近方法、分支定界
方法、区间方法和积分方法等;另一种是从局部解转向全局解，
有隧道函数方法和填充函数方法等.我们将在第一章介绍这几
种求总极值的确定性算法。
郑权提出的求全局优化的积分型方法，有很好的理论性质
和计算效果。但是，其实现算法的收敛性至今没有解决，并被
认为是一个难问题。我们对郑权等提出的积分型求总极值算法
作了修正，讨论了用均值一水平集求总极值的算法，这些算法
既保留了仅需要计算目标函数值的优点，又是一个可实现的具
有全局收敛性的算法。首先，在2.2中我们给出一个离散均值-
水平集求总极值的实现算法，该算法的主要思想是:在函数值
较好的点的邻域中多取点，在函数值较坏的邻域中少取点。同
时给出算法的终止准则，证明了算法的收敛性。然后，在2.3
中给出一个修正的求总极值的积分一水平集算法，该算法在每
一次迭代中，构造一个新函数，它与原目标函数具有相同的总
极值;在算法的实现时，我们用数论中确定性的一致分布的数
值积分来逼近水平值和水平集，且不改变搜索区间，避免了郑
权的实现算法中因用Monte一Carlo方法逼近水平集，并收缩迭
代区间而容易丢失总极值点的弱点;并给出了总极值存在的条
件;证明了实现算法的收敛性。在2.4中讨论了求约束总极值的
算法。最后，在2.5中给出了一些数值例子，说明我们的算法
是有效的。
葛人傅提出的求全局优化填充函数方法，其填充函数有缺
点，如果参数选择不当，会丢失全局最优点，或者用填充函数
求总极值的某些确定性算法
求出的点不是目标函数的较小的极小点。我们给出一类辅助函
数，在适当的条件下，证明了它们是一类填充函数，且是性态
较好的填充函数;并以此构造算法来求一般的非线性规划和非
线性整规划的全局解。在3.2中，我们给出一个仅含一个参数
的填充函数P(x，x*，P);在33中给出另一个填充函数
P(x，二‘，p，川，用它来构造算法，求解非线性规划的总极值;数
值计算表明算法是有效的。对于非线性整规划的总极值问题缺
乏有效的算法，我们试图用填充函数法进行求解，在3.4中，
我们给出一个仅含一个参数的填充函数爪二，，二二’，P);在3.5中
给出另一个填充函数风二，，:;，，p，川，用它来求解非线性整规
划，数值结果表明算法是有效的。
The global optimization problem can be stated as follows: Given a nonempty, closed set D R" and a continuous functionf: A-R, where A R" is a suitable set containing D, find at least one point x * D satisfy ingf(x*) f(x) for all x
i.e.
There are many applications of the nonlinear global optimization in the field of science and technology, optimal design of engineering," economic managenent and so on. In this dissertation, we consider mainly some deterministic methods for solving global optimization problems.
In Chapter 1, a brief introduction is given to the main classes of global optimization problems that can be treated by deterministic methods. Some of these methods are successively to approximate global solution; most prominent examples are the outer approximation, the branch-and-bound method, the interval method and the integral method. Others are developed from the local minimum to the global minimum, such as the tunneling algorithm and the filled function method.
In Chapter 2, we modify Zheng's integral method and propose several algorithms to find the global solution of (P). They are implementable algorithms and have the merit, which only calculate
the values of the objective functions. The following is the organization of Chapter 2. In Section 2.2, we present an algorithm for solving the problem (P) by discrete level set-mean value. The main idea of this algorithm is that, at each iteration, we take more points on some regions in which the values of the function f(x) is smaller than those in other regions, and take fewer points on the regions in which the values of the function f(x) is bigger than those in other regions. In this way the efficiency of computation can be improved. Moreover, the termination rule for discrete level set-mean value is given and the convergence of the algorithm is proved. In Section 2.3, we propose a modified integral-level set algorithm for solving the global optimization. In each iterative process, we construct a new function, which has the same global optimum as that of the primitive function. The algorithm is implemented by applying the deterministic uniform distribution numerical integral in number theory to approach the level value and the level set. Because of not changing the search domain, we can avoide using Zheng's Monte-Carlo implemtable algorithm, which is maybe to lose of the global optimum, to approach the level set. Furthmore, we gain the optimality conditions and prove the convergence of the algorithm. Section 2.4 discusses how to solve the constrained global optimization. Several numerical examples are presented in Section 2.5, the priliminary numerical results show that our algorithms are effective.
In Chapter 3, we construct a class of auxiliary functions which correspond to a class of filled functions, and we propose some algorithms to find the global minimum for the unconstrained
2000
optimization and the nonlinear integer programming. The organization of Chapter 3 is as follows. Section 3.2 discusses a filled function with only one parameter. In Section 3.3 we show how using another filled function to construct an algorithm to solve the global unconstrained optimization. The computational results show that this algorithm is effective. There is no any algorithm for integer programming with quadratic constraints and linear objective function. Therefore, we assume that the domain of function is bounded when nonlinear integer programming is concerned. Even for this case, there is also lack of algorithms to solve it. We proposed an approach for finding the global minimum of nonlinear integer programming. Section 3.4 is devoted to study a filled function p(x1,x1',p)with only one parameter..In Section 3.5,we present the
other filled function p(x/,x*1, p,//) in order to solve the nonlinear
integer programming. The numerical test results show that the
algorithm is also effective.
引文
1 Cooper L. Location-Allocation Problems. Operations Research, 1963; 11: 331-343
2 Megiddo N., Supowit K.J. On The Complexity of Some Common Geometric Location Problems. SlAM Journal on Computing, 1984; 13: 182-196
3 Galperin E.A., Zheng Q. Nonlinear Observation.via Global Optimization Methods: Measure Theory Approach. Journal of Optimization Theory and Applications, 1987; 54:63-92
4 Falk J.E. Conditions for Global Optimality in Nonlinear Programming, 1973; 5:169-188
5 Gomory R.E. Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the Americal Mathematical Society, 1958; 64: 275-278
6 Gomory E. Solving Linear Programming Problems in Integers. In: Bellman R., Hall M.eds. Combinatorial Analysis, Providence, 1960:211-215
7 Cheney E.W., Goldstein A.A. Newton's Method for Convex Programming and Tchebycheff Approximation. Numerische Mathematik, 1959; 1: 253-268
8 Kelley J.E. The Cutting-Plane Method for Solving Convex Programs, Journal SIAM, 1960; 8:703-712
9 Hoffman K. L. A Method for Globally Minimizing Concave Functions over Convex Sets, Mathematical Programming, 1981; 20:22-32
10 Thieu T.V., Tam B.T., Ban V.T. An Outer Approximation Method for Globally Minimizing a Concave Function over a Compact Convex Set.
Acta Mathematica Vietnamica, 1983; 8:21-40
11 Thoai N.V. Verfahren zur Losung Konkaver Optimierung Saufgaben, Seminarbericht 53 der Humboldt Universitat Berlin. Sektion Mathematik, 1984
12 Tuy H. On Outer Approximation Methods for Solving Concave Minimization Probloms. Acta Mathematica Vietnamics, 1983; 8:3-34
13 Tuy H. Global Minimization of a Difference of Two Convex Functions. Mathematical Programming Study, 1987; 30:150-182
14 Thoai N.V. A Modified Version of Tuy's Method for Solving D.C. Programming Probloms. Optimization, 1988; 19:665-674
15 Tuy H. A General Deterministic Approach to Global Optimization via D.C. Programming, In: Hiriart-Urruty J.B. ed. Fermat Days 1985: Mathematics for Optimization, Amsterdam: Elsevier, 1986:137-162
16 Thach P.T., Tuy H. Global Optimization under Lipschitzian Constraints, Japan Journal of Applied Mathematics, 1987; 4:205-217
17 Horst R., Thoai N.V., Tuy H. Outer Approximation by Polyhedral Convex Sets. Operations Research Spektrum, 1987; 9:153-159
18 Horst R., Thoai N.V., Tuy H. On an Outer Approximation Concept in Global Optimization, Optimization, 1989; 20:255-265
19 Veinott A.F. The Supporting Hyperplane Method for Unimodal Programming, Operations Research, 1967; 15:147-152
20 Topkis D.M. Cutting Plane Methods without Nested Constraint Sets. Operations Research, 1970; 18:404-413
21 Eaves B.C., Zangwill W.I. Generalized Cutting Plane Algorithms, SIAM Journal on Control, (1971;9:529-542
22 Hogan W.W. Applications of a General. Convergence Theory for Outer Approximation Algorithms, Mathematical Programming, 1973; 5:151-168
23 Gonzaga C., Polak E. On Constraint Dropping Schemes and Optimality
Functions for a Class of Outer Approximation Algorithms. SIAM Journal on Control and Optimization, 1979; 17:477-493
24 Mayne D.Q., Polak E. Outer Approximation Algorithm for Nondifferentiable Optimization Problems. Journal of Optimization Theory and Applications, 1984; 42:19-30
25 Tuy H., Khachaturov V., Utkin S. A Class of Exhaustive Cone Splitting Procedures in Conical Algorithms for Concave Minimization. Optimization, 1987; 18:791-807
26 Horst R. A New Branch and Bound-Approach for Concave Minimization Problems. Lecture Notes in Computer Science, 1976; 41:330-337
27 Horst R. An Algorithm for Nonconvex Programming Problems. Mathematical Programming, 1976;10:312-321
28 Tuy H., Horst R. Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization Application to Concave Minimization and D.C. Optimization Problems. Mathematical Programming, 1989; 41:161-183
29 Horst R. A General Class of Branch-and-Bound Methods in Global Optimization with Some New Approaches for Concave Minimization. Journal of Optimization Theory and Applications, 1986; 51: 271-291
30 Tuy H., Thieu T.V., Thai N.Q. A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research, 1985; 10:498-514
31 Horst R. Deterministic Global Optimization with Partition Sets Whose Feasibility is Not Known, Application to Concave Minimization, DC-Programming Reverse Convex Constraints and Lipschitzian Optimization, Journal of Optimization Theory and Applieations, 1988; 58:11-37
32 Horst R. On Consistency of Bounding Operations in Deterministic Global Optimization. Journal of Optimization Theory and Applications, 1989; 61:
143-146
33 Horst R. Deterministic Methods in Contrained Global Optimization: Some Recent Advances and New Fields of Application. Naval Research Logistics, 1990; 37:433-471
34 Ratschek H., Rokne J. New Computer Methods for Global Optimization, Ellis Horwood Limited, 1988
35 Moore R.E. Interbal Analysis, Prentice-Hall, NJ: Englewood Cliffs, 1966
36 Skelboe S. Computation of Rational Interval Functions. BIT, 1974; 14:87-95
37 Moore R.E. On Computing the Range of Values of a Rational Function of n Variables Over a Bounded Region. Computing, 1976; 16:1-15
38 Ratschek H. Inclusion Functions and Global Optimization. Mathematical Programming, 1985; 33:300-317
39 Moore R.E., Ratschek H. Inclusion Functions and Global Optimization Ⅱ. Mathematical Programming, 1987
40 Ichida K., Fujii Y. An Interval Arithmetic Method for Global Optimization. Computing, 1979; 23:85-97
41 Hansen E.R. Global Optimization Using Interval Analysis-the Onedimensional Case. Journal of Optimization Theory and Applications, 1979; 29:331-344
42 Hansen E.R. Global Optimization Using Interval Analysis-the Multidimensional Case. Numerische Mathematik, 1980; 34:247-270
43 Sengupta S. Global Nonlinear Optimization. [Ph.D. Thesis], Washington State University, Pullman, Washington, 1981
44 Hansen E.R., Sengupta S. Global Constrained Optimization Using Interval Analysis. In: Nickel ed. 1980:25-47
45 Hansen E.R., Sengupta S. Summary and Steps of a Global Nonlinear Constrained Optimization Algorithm. LMSC-D889778, Sunnyvale, California: Lockheed Missiles and Space Co., 1983
46 Chew S.H., Zheng Q. Integral Global Optimization, Lecture Notes in Economics and Mathematical Systems, No.298, Springer-Verlag, 1988
47 Zheng Q., Zhuang D.M. Integral Global Minimization: Algorithms, Implementations and Numerical Tests. Journal of Global Optimization, 1995; 7(4): 421-454
48 郑权，蒋百川，庄松林．一个求总极值的方法．应用数学学报，1978；1(2)：161-173
49 Levy A.V., Montalvo A. The Tunneling Algorithm for the Global Minimization of Functions, SIAM Journal Sci. Stat. Comput., 1985; 6(1): 15-29
50 Yao Y. Dynamic Tunneling Algorithm for Global Optimization. IEEE Transactions on Systems, Man, and Cybernetics, 1989; 19(5): 1222-1230
51 Barhen J., Protopopescu V.,Reister D. TRUST: A Deterministic Algorithm for Global Optimization. Science, 1997; 276(16): 1094-1097
52 Cetin B.C., Barhen J., Burdick J.W. Terminal Repeller Unconstrained Subenergy Tunneling (TRUST) for Fast Global Optimization. Journal of Optimization Theory and Applications, 1993; 77(1): 97-126
53 Ge R.P. A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables. Paper Presented at the Dundee Biennial Conference on Numerical Analysis, Dundee, Scotland 1983
54 Ge R.P. The Theory of the Filled Function Method for Finding a Global Minimizer of a Nonlinearly Constrained Minimization Problem. Paper Presented at the SIAM Conference on Numerical Optimization, Boukder, Colorado., 1984
55 Ge R.P. A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables. Mathematical Programming, 1990; 46:191-204
56 Ge R.P., Qin Y.F.A Class of Filled Functions for Finding Global Minimizers of a Function of Several Variables. Journal of Optimization Theory and
Applications, 1987; 4(2): 241-252
57 Zhang L.S., Li D. Global Search in Nonlinear Integer Programming: Filled Function Approach. International Conference on Optimization Techniques and Applications, Perth, 1998:446-452
58 朱文兴，张连生非线性整数规划的一个近似算法．运筹学学报，1997：11：72-81
59 华罗庚，王元．数论在近似分析中的应用．科学出版社，1978
60 Schmidt W. M. Simultaneous Approximation to Algebraic Numbers by Rationals. Acta Mathematics, 1970; 125:189-201
61 Baker A. On Some Diophantine Inequalities Involving the Exponential Function. Canadian Journal of Mathematics, 1965; 17: 616-626
62 Zhang L.S. An Approach to Finding a Global Minimization with Equality and Inequality Constraints. Journal of Computational Mathematics, 1988; 6(4): 375-382
63 Ge R. P. A Continuous Approach to Nonlinear Integer Programming. Applied Mathematics and Computation, 1989; 34:39-60
64 Androulakis I.P., Maranas C.D., Floudas C.A. A Global Optimization Method for General Constrained Nonconvex Problems. Journal of Global Optimization, 1995; 7:337-363
65 Benson H.E On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems. Journal of Optimization Theory and Applications, 1982; 36:129-134
66 Benson H.P., Horst R. A Branch and Bound---Outer Approximation for Concave Minimization Over a Convex Set. Journal of Computers and Mathematics with Applications, 1991; 21:67-76
67 Ben-Tal A., Eiger G., Gershovitz V. Global Minimization by Reducing the Duality Gap. Mathematical Programming, 1994; 63:193-212
68 Floudas C.A., Aggarwal A. A Decomposition Strategy for Global Optimum
Search in the Pooling Problem. ORSA Journal on Computing, 1990: 2(3):225-235
69 Foulds L.R., Haugland D., Jornsten K. A Bilinear Approach to the Pooling Problem. Optimization, 1992; 24:165-180
70 Ge R.P., Jeroslow. There Can Not Be Any Algorithm for Integer Programming with Quadratic Constraints. Operations Research, 1973; 21:221-224
71 Hansen P., Jaunard B., Lu S.H. Global Optimization of Univariate Lipschitz Functions: 1. Survey and Properties. Mathematical Programming, 1992; 55:251-272
72 Hansen P., Jaunard B., Lu S.H, Global Optimization of Univariate Lipschitz Functions: Ⅱ. New Algorithms and Computational Comparison. Mathematical Programming, 1992; 55:273-292
73 Horst R. A Note on the Convergence of an Algorithm for Nonconvex Programming Problems. Mathematical Programming, 1980; 19:237-238
74 Horst R., Tuy H. Global Optimization (Deterministic Approaches), Berlin/New York: Springer-Verlag, 1996
75 Litinetski V.V., Abramzon B.M. MARS-A Multistart Adaptive Random Search Method for Global Constrained Optimization in Engineering Applications. Engineering Optimization, 1998; 30:125-154
76 Ryoo H.S., Sahinidis N.V. A Branch-and-Reduce Approach to Global Optimization. Journal of Global Optimization, 1996; 8:107-138
77 Thoai N.V., Tuy H. Convergent Algorithms for Minimizing a Concave Function. Mathematics of Operations Research, 1980; 5:556-566
78 Tuy H. Convex Analysis and Global Optimization. Noneonvex Optimization and Its Applications, Kluwer Academic Publishers, 1998; 22
79 Wood G.R. Multidimensional Bisection and Global Optimisation. Computers and Mathematics with Applications, 1991; 21:161-172
80 Wood G.RThe Bisection Method in Higher Dimeosions. Mathematical Programming, 1992; 55:319-337
81 Wood G.R., Zhang B.P. Estimation of the Lipschitz Coostant of a Function. Journal of Global Optimization, 1996; 8:91-103
82 Zhang B.P., Wood G.R., Baritompa W.R Multidimensional Bisection: the Performance and the Context. Journal of Global Optimization, 1993; 3: 337-358
83 Zheng Q., Zhang L.S. Global Minimization of Constrained Problems with Discontinuous Penalty Functions. Journal of Computers and Mathematics with Application, 1999; 37:41-58
84 方开泰，王元．数沦方法在统计中的应用．科学出版社，1996
85 许梦杰，张连生．用均值——水平集求多个总极值点的方法．运筹学杂志，1996；15(2)：25-29
86 张连生．精确罚函数和约束总极值问题．高校计算数学学报，1988；(2)：141-148
87 张连生，田蔚文，姚奕荣．积分——水平集总极值算法的另一实现途径，运筹学杂志，1996；15(1)：60-64
88 张连生，朱文兴．非线性整数规划的连续化途径．第二届全国最优化会议论文集，西安，1994
89 郑权，张连生．带不等式约束数学规划的总极值问题．自然杂志，1978；(3)
90 郑权，张连生．罚函数与带不等式约束的总极值问题．计算数学，1980；(3)：146-153
2 Megiddo N., Supowit K.J. On The Complexity of Some Common Geometric Location Problems. SlAM Journal on Computing, 1984; 13: 182-196
3 Galperin E.A., Zheng Q. Nonlinear Observation.via Global Optimization Methods: Measure Theory Approach. Journal of Optimization Theory and Applications, 1987; 54:63-92
4 Falk J.E. Conditions for Global Optimality in Nonlinear Programming, 1973; 5:169-188
5 Gomory R.E. Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the Americal Mathematical Society, 1958; 64: 275-278
6 Gomory E. Solving Linear Programming Problems in Integers. In: Bellman R., Hall M.eds. Combinatorial Analysis, Providence, 1960:211-215
7 Cheney E.W., Goldstein A.A. Newton's Method for Convex Programming and Tchebycheff Approximation. Numerische Mathematik, 1959; 1: 253-268
8 Kelley J.E. The Cutting-Plane Method for Solving Convex Programs, Journal SIAM, 1960; 8:703-712
9 Hoffman K. L. A Method for Globally Minimizing Concave Functions over Convex Sets, Mathematical Programming, 1981; 20:22-32
10 Thieu T.V., Tam B.T., Ban V.T. An Outer Approximation Method for Globally Minimizing a Concave Function over a Compact Convex Set.
Acta Mathematica Vietnamica, 1983; 8:21-40
11 Thoai N.V. Verfahren zur Losung Konkaver Optimierung Saufgaben, Seminarbericht 53 der Humboldt Universitat Berlin. Sektion Mathematik, 1984
12 Tuy H. On Outer Approximation Methods for Solving Concave Minimization Probloms. Acta Mathematica Vietnamics, 1983; 8:3-34
13 Tuy H. Global Minimization of a Difference of Two Convex Functions. Mathematical Programming Study, 1987; 30:150-182
14 Thoai N.V. A Modified Version of Tuy's Method for Solving D.C. Programming Probloms. Optimization, 1988; 19:665-674
15 Tuy H. A General Deterministic Approach to Global Optimization via D.C. Programming, In: Hiriart-Urruty J.B. ed. Fermat Days 1985: Mathematics for Optimization, Amsterdam: Elsevier, 1986:137-162
16 Thach P.T., Tuy H. Global Optimization under Lipschitzian Constraints, Japan Journal of Applied Mathematics, 1987; 4:205-217
17 Horst R., Thoai N.V., Tuy H. Outer Approximation by Polyhedral Convex Sets. Operations Research Spektrum, 1987; 9:153-159
18 Horst R., Thoai N.V., Tuy H. On an Outer Approximation Concept in Global Optimization, Optimization, 1989; 20:255-265
19 Veinott A.F. The Supporting Hyperplane Method for Unimodal Programming, Operations Research, 1967; 15:147-152
20 Topkis D.M. Cutting Plane Methods without Nested Constraint Sets. Operations Research, 1970; 18:404-413
21 Eaves B.C., Zangwill W.I. Generalized Cutting Plane Algorithms, SIAM Journal on Control, (1971;9:529-542
22 Hogan W.W. Applications of a General. Convergence Theory for Outer Approximation Algorithms, Mathematical Programming, 1973; 5:151-168
23 Gonzaga C., Polak E. On Constraint Dropping Schemes and Optimality
Functions for a Class of Outer Approximation Algorithms. SIAM Journal on Control and Optimization, 1979; 17:477-493
24 Mayne D.Q., Polak E. Outer Approximation Algorithm for Nondifferentiable Optimization Problems. Journal of Optimization Theory and Applications, 1984; 42:19-30
25 Tuy H., Khachaturov V., Utkin S. A Class of Exhaustive Cone Splitting Procedures in Conical Algorithms for Concave Minimization. Optimization, 1987; 18:791-807
26 Horst R. A New Branch and Bound-Approach for Concave Minimization Problems. Lecture Notes in Computer Science, 1976; 41:330-337
27 Horst R. An Algorithm for Nonconvex Programming Problems. Mathematical Programming, 1976;10:312-321
28 Tuy H., Horst R. Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization Application to Concave Minimization and D.C. Optimization Problems. Mathematical Programming, 1989; 41:161-183
29 Horst R. A General Class of Branch-and-Bound Methods in Global Optimization with Some New Approaches for Concave Minimization. Journal of Optimization Theory and Applications, 1986; 51: 271-291
30 Tuy H., Thieu T.V., Thai N.Q. A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research, 1985; 10:498-514
31 Horst R. Deterministic Global Optimization with Partition Sets Whose Feasibility is Not Known, Application to Concave Minimization, DC-Programming Reverse Convex Constraints and Lipschitzian Optimization, Journal of Optimization Theory and Applieations, 1988; 58:11-37
32 Horst R. On Consistency of Bounding Operations in Deterministic Global Optimization. Journal of Optimization Theory and Applications, 1989; 61:
143-146
33 Horst R. Deterministic Methods in Contrained Global Optimization: Some Recent Advances and New Fields of Application. Naval Research Logistics, 1990; 37:433-471
34 Ratschek H., Rokne J. New Computer Methods for Global Optimization, Ellis Horwood Limited, 1988
35 Moore R.E. Interbal Analysis, Prentice-Hall, NJ: Englewood Cliffs, 1966
36 Skelboe S. Computation of Rational Interval Functions. BIT, 1974; 14:87-95
37 Moore R.E. On Computing the Range of Values of a Rational Function of n Variables Over a Bounded Region. Computing, 1976; 16:1-15
38 Ratschek H. Inclusion Functions and Global Optimization. Mathematical Programming, 1985; 33:300-317
39 Moore R.E., Ratschek H. Inclusion Functions and Global Optimization Ⅱ. Mathematical Programming, 1987
40 Ichida K., Fujii Y. An Interval Arithmetic Method for Global Optimization. Computing, 1979; 23:85-97
41 Hansen E.R. Global Optimization Using Interval Analysis-the Onedimensional Case. Journal of Optimization Theory and Applications, 1979; 29:331-344
42 Hansen E.R. Global Optimization Using Interval Analysis-the Multidimensional Case. Numerische Mathematik, 1980; 34:247-270
43 Sengupta S. Global Nonlinear Optimization. [Ph.D. Thesis], Washington State University, Pullman, Washington, 1981
44 Hansen E.R., Sengupta S. Global Constrained Optimization Using Interval Analysis. In: Nickel ed. 1980:25-47
45 Hansen E.R., Sengupta S. Summary and Steps of a Global Nonlinear Constrained Optimization Algorithm. LMSC-D889778, Sunnyvale, California: Lockheed Missiles and Space Co., 1983
46 Chew S.H., Zheng Q. Integral Global Optimization, Lecture Notes in Economics and Mathematical Systems, No.298, Springer-Verlag, 1988
47 Zheng Q., Zhuang D.M. Integral Global Minimization: Algorithms, Implementations and Numerical Tests. Journal of Global Optimization, 1995; 7(4): 421-454
48 郑权，蒋百川，庄松林．一个求总极值的方法．应用数学学报，1978；1(2)：161-173
49 Levy A.V., Montalvo A. The Tunneling Algorithm for the Global Minimization of Functions, SIAM Journal Sci. Stat. Comput., 1985; 6(1): 15-29
50 Yao Y. Dynamic Tunneling Algorithm for Global Optimization. IEEE Transactions on Systems, Man, and Cybernetics, 1989; 19(5): 1222-1230
51 Barhen J., Protopopescu V.,Reister D. TRUST: A Deterministic Algorithm for Global Optimization. Science, 1997; 276(16): 1094-1097
52 Cetin B.C., Barhen J., Burdick J.W. Terminal Repeller Unconstrained Subenergy Tunneling (TRUST) for Fast Global Optimization. Journal of Optimization Theory and Applications, 1993; 77(1): 97-126
53 Ge R.P. A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables. Paper Presented at the Dundee Biennial Conference on Numerical Analysis, Dundee, Scotland 1983
54 Ge R.P. The Theory of the Filled Function Method for Finding a Global Minimizer of a Nonlinearly Constrained Minimization Problem. Paper Presented at the SIAM Conference on Numerical Optimization, Boukder, Colorado., 1984
55 Ge R.P. A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables. Mathematical Programming, 1990; 46:191-204
56 Ge R.P., Qin Y.F.A Class of Filled Functions for Finding Global Minimizers of a Function of Several Variables. Journal of Optimization Theory and
Applications, 1987; 4(2): 241-252
57 Zhang L.S., Li D. Global Search in Nonlinear Integer Programming: Filled Function Approach. International Conference on Optimization Techniques and Applications, Perth, 1998:446-452
58 朱文兴，张连生非线性整数规划的一个近似算法．运筹学学报，1997：11：72-81
59 华罗庚，王元．数论在近似分析中的应用．科学出版社，1978
60 Schmidt W. M. Simultaneous Approximation to Algebraic Numbers by Rationals. Acta Mathematics, 1970; 125:189-201
61 Baker A. On Some Diophantine Inequalities Involving the Exponential Function. Canadian Journal of Mathematics, 1965; 17: 616-626
62 Zhang L.S. An Approach to Finding a Global Minimization with Equality and Inequality Constraints. Journal of Computational Mathematics, 1988; 6(4): 375-382
63 Ge R. P. A Continuous Approach to Nonlinear Integer Programming. Applied Mathematics and Computation, 1989; 34:39-60
64 Androulakis I.P., Maranas C.D., Floudas C.A. A Global Optimization Method for General Constrained Nonconvex Problems. Journal of Global Optimization, 1995; 7:337-363
65 Benson H.E On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems. Journal of Optimization Theory and Applications, 1982; 36:129-134
66 Benson H.P., Horst R. A Branch and Bound---Outer Approximation for Concave Minimization Over a Convex Set. Journal of Computers and Mathematics with Applications, 1991; 21:67-76
67 Ben-Tal A., Eiger G., Gershovitz V. Global Minimization by Reducing the Duality Gap. Mathematical Programming, 1994; 63:193-212
68 Floudas C.A., Aggarwal A. A Decomposition Strategy for Global Optimum
Search in the Pooling Problem. ORSA Journal on Computing, 1990: 2(3):225-235
69 Foulds L.R., Haugland D., Jornsten K. A Bilinear Approach to the Pooling Problem. Optimization, 1992; 24:165-180
70 Ge R.P., Jeroslow. There Can Not Be Any Algorithm for Integer Programming with Quadratic Constraints. Operations Research, 1973; 21:221-224
71 Hansen P., Jaunard B., Lu S.H. Global Optimization of Univariate Lipschitz Functions: 1. Survey and Properties. Mathematical Programming, 1992; 55:251-272
72 Hansen P., Jaunard B., Lu S.H, Global Optimization of Univariate Lipschitz Functions: Ⅱ. New Algorithms and Computational Comparison. Mathematical Programming, 1992; 55:273-292
73 Horst R. A Note on the Convergence of an Algorithm for Nonconvex Programming Problems. Mathematical Programming, 1980; 19:237-238
74 Horst R., Tuy H. Global Optimization (Deterministic Approaches), Berlin/New York: Springer-Verlag, 1996
75 Litinetski V.V., Abramzon B.M. MARS-A Multistart Adaptive Random Search Method for Global Constrained Optimization in Engineering Applications. Engineering Optimization, 1998; 30:125-154
76 Ryoo H.S., Sahinidis N.V. A Branch-and-Reduce Approach to Global Optimization. Journal of Global Optimization, 1996; 8:107-138
77 Thoai N.V., Tuy H. Convergent Algorithms for Minimizing a Concave Function. Mathematics of Operations Research, 1980; 5:556-566
78 Tuy H. Convex Analysis and Global Optimization. Noneonvex Optimization and Its Applications, Kluwer Academic Publishers, 1998; 22
79 Wood G.R. Multidimensional Bisection and Global Optimisation. Computers and Mathematics with Applications, 1991; 21:161-172
80 Wood G.RThe Bisection Method in Higher Dimeosions. Mathematical Programming, 1992; 55:319-337
81 Wood G.R., Zhang B.P. Estimation of the Lipschitz Coostant of a Function. Journal of Global Optimization, 1996; 8:91-103
82 Zhang B.P., Wood G.R., Baritompa W.R Multidimensional Bisection: the Performance and the Context. Journal of Global Optimization, 1993; 3: 337-358
83 Zheng Q., Zhang L.S. Global Minimization of Constrained Problems with Discontinuous Penalty Functions. Journal of Computers and Mathematics with Application, 1999; 37:41-58
84 方开泰，王元．数沦方法在统计中的应用．科学出版社，1996
85 许梦杰，张连生．用均值——水平集求多个总极值点的方法．运筹学杂志，1996；15(2)：25-29
86 张连生．精确罚函数和约束总极值问题．高校计算数学学报，1988；(2)：141-148
87 张连生，田蔚文，姚奕荣．积分——水平集总极值算法的另一实现途径，运筹学杂志，1996；15(1)：60-64
88 张连生，朱文兴．非线性整数规划的连续化途径．第二届全国最优化会议论文集，西安，1994
89 郑权，张连生．带不等式约束数学规划的总极值问题．自然杂志，1978；(3)
90 郑权，张连生．罚函数与带不等式约束的总极值问题．计算数学，1980；(3)：146-153
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |