摘要
本文对两类全局优化算法(填充函数法和区间算法)作了比较深入的研究，在此基础上对这些算法作了进一步的推广和应用，取得了较为满意的结果，主要内容如下：
在已有的填充函数法的基础上，针对一类非光滑问题提出了一类改进的双参数填充函数法，此填充函数形式简洁，运算量低，大量的数值实验表明与已有相关文献比较该方法的精度和运算效率都有所提高。
对于Lipschitz规划，针对双参数填充函数法在参数选取时的局限性，本文构造了一类应用更广的单参数填充函数，提高了算法的执行效率，理论分析和数值试验均表明该算法比已有的相关算法优越。
利用线性加权法将多目标规划转化为单目标规划，根据其特点，构造了一种新的填充函数法，并利用此算法求得该单目标规划的全局最优解，即原规划的最小弱有效解，数值试验表明该算法是可行有效的，且能保证得到全局最优解。
此外，对离散的minimax问题，通过引入拟偏导数的概念，建立了目标函数的区间扩张和无解区域删除检验原则，基于Moore的区间二分原则提出了求解离散的minimax问题的区间算法．理论分析和数值结果均表明该算法是有效的，在给定精度内能求出全部最优解。
This thesis is devoted to two global optimization algorithms, such as a filled function method and an interval algorithm. Their properties and extended applications are discussed on emphasis and the satisfactory results are achieved. The main work of the dissertation can be summarized as follows:Based on some existing filled function methods in the references, a modified filled function method with two adjustable parameters is constructed for nonsmooth optimization. This method is simple and feasible. Theoretical analyses and a large amount of numerical results show that this method is better than other methods in the aspects such as accuracy, runtime and iterative number.The filled function with two parameters has some disadvantages, especially, the excessive restriction on the choices of the parameter values. So a modified filled function with only one parameter is proposed with much improved performance for a Lipschitz programming. Numerical experiments show that the method is efficient.This paper deals with the transformation of a multiple objective programming into a single objective programming. By the character of the single objective programming, a novel filled function method is described. Global optimal solutions of the single objective programming are obtained by the method, i.e., the minimal weakly efficient solutions to the original programming. The numerical tests show that it is practical and effective. Moreover, our filled function guarantees its minimum to be always achieved at a point where its function value is not higher than the function value of the current minimum.Besides all of the above, as to a discrete minimax problem, the interval extension of objective function and region deletion test rules are discussed via quasi-partial derivative. An interval algorithm is described based on the bisection rule of Moore. Theoretical analyses and numerical results show that the algorithm is efficient and that all global optimal points can be found in the given accuracy.
引文
[1] Jiang L., Xue G L.. Optimization of similarity index with application to biomolecules. Journal of Global Optimization. 1999,14:299-312.
[2] Bajirov A. M., Rubinov A. M.. Global optimization of marginal functions with applications to economic equilibrium. Journal of Global Optimization. 2001,20:215-237.
[3] Sherali H. D., Smith E. P.. A global optimization approach to a water distributing network design problem. Journal of Global Optimization. 1997,11:107-132.
[4] Falk J. E., Cardona E. L.. The surgical separation of sets. Journal of Global Optimization. 1997,11:433-462.
[5] Adjiman C. S., Androulakis L. P.. Global optimization of MINLP problems in process synthesis and design. Computers and Chemical Engineering. 1997,21:445-450.
[6] Zhigljavsky A. A.. Theory of Global Random Search. Kluwer Academic Publishers, Dordrecht, 1991.
[7] F. H.Clarke. Optimization and Nonsmooth Analysis. New York: John Wiley & Sons. 1983.
[8] Lemarechal C. An Introduction to the Theory of Nonsmooth Optimization. Optimization, 1986,17(6):827-858.
[9] Zowe J.. The BT-Algorithm for minimizing a Nonsmooth Functional Subject to Linear Constraints, In:Nonsmooth Optimization and Related Topics, F H Clarke,V P Demyanov and F Giannessieds.,Plenum Press, New York 1989:459-480.
[10] Miff R. Semi-smooth and semi-convex function in constrained optimization. SIAM Journal on Control and Optimization, 1977,15(6): 959-972.
[11] Ge R. P.. A filled function for finding global minimizer of a function several variables. Paper presented at the Dundee Biennial Conference on numerical analysis, Dundee, Scotland, 1983.
[12] Wang D. Y. and Sheng S. B.. A modified filled function method for finding a global minimizer of a function of several variables. Journal of Computational Mathematics. 1992:60-65.
[13] Sherali H. D.. A global optimization algorithm for polynomial programming problems using a reformulation-linearzation technique. Journal of Global Optimization. 1992,2:101-112.
[14] 孔敏，庄建南．求多变量非光滑函数总体极小点的一类改进的填充函数法．高等学校计算数学学报．1996，18(2)：165-174．
[15] 李宝秀，沈愉．Lipschitz规划的填充函数法．系统科学．1991，11(4)：346-348．
[16] 张乐友，刘三阳，葛泽慧．求解Lipschitz型规划全局极小点的改进的填充函数法．高等学校计算数学学报．2003，25(2)：153-159．
[17] Ge R. P.. The theory of the filled function method for finding a global minimizer of a nonlinear constraints problem. Journal of Computational Mathematics. 1987, 5 (1): 1-9.
[18] Ge R. P. and Qin Y. F.. A class of filled function for finding global minimizer of a nonlinear constraints problem. Journal of Optimization Theory and Applications. 1987, 154 (2): 241-252.
[19] Zhang X.. Filled functions for unconstrained global optimization. Journal of Global Optimization. 2001, 20: 49-65.
[20] Ge R. P.. A filled function method for finding global minimizers of a function of several variables. Mathematical Programming. 1990, 46: 191-204.
[21] Zhuang J. N.. A generalized filled function method for finding the global minimizer of a function of several variables. Numerical Mathematics-A Journal of Chinese Universities. 1994, 16 (3): 279-287.
[22] Liu X.. Finding global minimal with a computable filled function. Journal of Global Optimization. 2001, 19: 151-161.
[23] Zhang L. S., Li D. and Tian W. W.. A new filled function method for global optimization. Journal of Global Optimization. 2004, 28: 17-43.
[24] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社．1997．
[25] 陈开周．最优化计算方法．西安：西安电子科技大学出版社．1984．
[26] 应玫茜，魏权龄．非线性规划及其理论．北京：中国人民大学出版社．1994．
[27] Zhu W. X., Fu Q. X.. A sequential convexification method (SCM) for continuous global optimization. Journal of Global Optimization. 2003, 26: 167-182.
[28] Barhen J., V Protopopescu and D Reister. TRUST: a deterministic algorithm for global optimization. Science: 1997 (276): 1094-1097.
[29] Pardalos P. M., Rosen J. B.. Constrained Global Optimization: Algorithms and Applications. Springer, Berlin. 1987.
[30] Horst R., Pardalos P. M. and Thoai N. V.. Introduction to global optimization. Kluwer Academic Publishers, Dordrecht. 1995.
[31] Xu Z., Huang H. X., Pardalos, Panos M. and Xu C. X.. Filled functions for unconstrained global optimization. J. of Global Optimization. 2001, 20: 49-65.
[32] Cetin B. C., Barhen J. and Burdick J. W.. Terminal repeller uncounstrained subenergy tunneling (TRUST) for fast global optimization. Journal of Optimization and Applicatione. 1993, (77): 97-126.
[33] Li D., Sun X. L., Biswal M. P. and Gao F.. Convexification, concavifition and monotonization in global minimization. Annals of Operations Research. 2001 (105).
[34] Sun X. L., Mckinnon K. I. M. and Li D.. Convexification method for a class of global optimization problems with applications to reliability optimization. Journal of Global Optimization. 2001, 21: 185-199.
[35] Dixon L. C. W., Gomulka J. and Herson S. E.. Reflection on global optimization problems, in L. C. W. Dixon (ed.), Optimization in action. Academic press. New York. 1976: 398-435.
[36] Yao Y.. Dynamic tunneling algorithm for global optimization: IEEE Transactions on Systems. Man and Cybernetics. 1989, 19: 1222-1230.
[37] Zheng Q. and Zhuang D.. Integral global minimization: algorithm, implementations and numerical tests. Journal of Global Optimization. 1995, 7 (4): 421-454.
[38] 孔敏．一类改进的非光滑规划的填充函数法．系统科学与数学，2000，20(2)：149-154．
[39] 林锉云，董加礼．多目标优化方法和理论．长春：吉林教育出版社，1992．
[40] 李兴斯．非线性极大极小问题的凝聚函数法．计算力学及其应用，8(1)，1991：85-92．
[41] 王海鹰，张乃良．带约束条件的离散Minimax问题的区间极大熵方法．高等学校计算数学学报．2000，15(3)：369-376．
[42] Zhang L. W., Tang H. W.. A maximum entropy algorithm with parameters for sloving minimax problem. Archives of Control Sciences. 6 (1-2), 1997: 47-54.
[43] Templemen A. B., Li X. S.. A maximum entropy approach to constrained nonlinear programming. Engineering Optimization. 12, 1987 (b): 191-205.
[44] Polak E., Higgins J. E. and Mayne D. Q.. A barrier function method for minimax problems. Mathematical Programming. 1992, 54: 155-176.
[45] Tang H. W., Zhang L. W., Wang X. H.. Maximum entropy methods for constrained optimization and minimax problem. Systems Science and Mathematical Science. 9 (1), 1996: 1-4.
[46] Shen Z. H., Huang Z. Y. and Wolfe M. A.. An interval maximum entropy method for a discrete minimax problem. Applied Math. And Comput. 1997, 87: 49-68.
[47] Cao D. X,, Huang Z. Y.. An interval algorithm for a discrete minimax problem. Journal of Nanjing University Mathematical Biquarterly. 1997, 14: 74-82.
[48] Moore R. E.. Method and application of interval analysis. SIAM, Philadelphia. 1979.
[49] Dietmar Ratz. A nonsmooth global ptimization technique using slopes: the one-dimensional case. Journal of Global Optimization. 1999, 14: 365-393.
[50] Shen Z. H. and Eiermann M. C.. Interval-Majorant. method and global optimization. Computing. 1998, 43: 85-92.
[51 ] Zhang L. S. and Wolfe M. A.. An interval algorithm for nondifferentiable global optimization. Applied Math. And Comput. 1994, 63: 101-122.
[52] Casado L. G, Csendes T.. A Heuristic rejection criterion in interval global optimization algorithms. BIT. 2001, 41 (4): 683-692.
[53] Csendes T., Ratz D.. Subdivision direction selection in interval global optimization. SIAM J. Numer. Anal.. 1997, 34 (3): 922-938.
[54] Shen Z. H., Moore M. A.. On interval enclosures using slope arithmetic. Applied Mathematics and Computation. 1990, 39: 89-105.
[55] Shen P. P., Zhang K. C. and Wang Y. J.. Applications of interval arithmetic in non-smooth global optimiz ation. Applied Mathematics and Computation. 2003, 144 (2-3): 413-431.
[56] Ratschek H. and Rokne J.. Efficiency of a global optimization algorithm. SIAM J. Numer. Anal.. 1987, 24 (5): 1191-1201.
[57] 申培萍，张可村．求一类多元多峰函数全局极小的区间斜率方法．计算数学．2003，25(3)：333-346．
[58] Shen P. P., Zhang K. C.. An interval method for nonsmooth global optimization problem. OR Transactions. 2002, 6 (2): 9-18.
[59] Casado L. G, Garcia I., Csendes T. A new multisection technique in interval methods for global optimization. Computing. 2000, 65: 263-269.
[60] Wolfe M. A.. An interval algorithm for oozed global optimization. Journal of Comput and Appl Math. 1994, 50: 605-612.
[61] Markot M. Cs., Csendes T. Multisection in interval branch-and-bound methods for global optimization I: theoretical results. Journal of Gllbal Optimization. 2000, 16: 371-392.
[62] Casado L. G, Gareia I., Martinez J. A.. Experiments with a new selection criterion in a fast interval optimization algorithm. Journal of Global Optimization. 2001, 19: 247-264.
[63] Shen Z. H. and Zhu Y. R.. An interval version of Shubert's iterative method for the localization of the global maximum. Computing. 1987, 38: 275-280.
[64] Shen Z. H., Neumaierand A, Eiennann M C. Solving minimax problems by interval methods. BIT. 1990, 30: 742-751.
[65] Kearfott R. B.. Interval extensions of non-smooth functions for global optimization and nonlinear systems solvers. Computing. 1996, 57: 149-162.
[66] Caprani O. and Madsen K.. Mean value forms in interval analysis. Computing. 1980, 25: 147-154.
[67] Ratschek H. and Rokne J.. New computer methods for global optimization. Ellis Horwood: Chichester, 1998.
[68] Ratschek H. and Rokne J.. Efficiency of a global optimization algorithm. SIAM J. Numer. Anal.. 1987, 24(5): 1191-1201.
[69] Krawczyk R. and Neumaier A.. Interval slopes for rational functions and associated centered forms. SIAM J. Numer. Anal., 1985, 22 (3): 604-616.
[70] Shen P. P.. An interval algorithm for finding all global minimizers of nonsmooth functions. Chinese J. Numer. Anal., 1999, 21 (3): 15-20.
[71] Ratschek H., Voller R. L.. Global optimization over unbounded domains. SIAM J. Contral and Optimization. 1990, 28: 528-539.
[72] Fogel D. B.. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks. 1994, 5(1): 3-14.
[73] Sherali H. D., Wang H. J.. Global optimization of nonconvex factorabal programming problems. Math Programming. 2001, 80: 450-478.
[74] Falk J. E., Soland R. M.. An algorithm for separable nonconvex programming problems. Management Sci.. 1996, 15: 550-569.
[75] Hansen E.. Global Optimization Using Interval Analysis. New York: Marcel Dekker Inc. 1992.
[76] Jacobsen S. E., Torabi M.. A global minimization algorithm for a class of one dimensional functions. J. of Mathematical and Applications. 1978, 62: 310-324.
[77] Asaithambi N. S., Shen Z., Moore R E. On computing the range of values. Computing. 1982, 28: 225-237.
[78] Ratschek H., Rokne J.. Handbook of Global Optimization. Dordrecht: Kluwer. 1993: 751-828.
[79] 张乐友，刘三阳，吴青．求解非线性方程组的路径跟踪算法．西安电子科技大学学报．2002，29(4)，558-560．
[80] 吴青，刘三阳，张乐友．求一类非光滑规划全局极小点的改进的(单参)填充函数法．应用数学．2004，Vol．17：36-40．
[81] 吴青，刘三阳，张乐友．求非光滑规划全局极小点的一类改进的(双参)填充函数法．数值计算与计算机应用(已录用)．
[82] 吴青，刘三阳，张乐友．求解多目标规划最小弱有效解的一种填充函数法．应用数学(已录用)．
[83] 吴青，刘三阳，张乐友．离散minimax问题的一类区间算法．数学的实践与认识(已录用)．
[84] Wu Q., Liu S. Y. and Zhang L. Y.. A modified filled function method for finding global minimizers of a nonsmooth programming. Chinese J. Numer. Math. and Appl. (已录用).
[85] 吴青，刘三阳，张乐友．Minimax问题的调节熵函数法．运筹与管理(已录用)．
[86] Wu Q., Liu S. Y. and Zhang L. Y.. A modified filled function method for a lipschitz programming. OR Transactions (通过一审).