摘要
本文主要研究求解无约束、简单约束优化问题的并行算法.针对现有的并行变量分布算法(PVD)及并行变量转换算法(PVT),进行了一些研究工作.本文分别在第二、三及四章中,基于上述两种并行算法给出了三种改进的算法:线性不可分约束的PVD型算法,无约束问题的异步PVT算法及针对线性约束的大规模问题的部分异步PVT算法.由于模式搜索法在实际应用中十分有效,并且有潜在的并行性,为此在第五、六章中研究了无约束模式搜索法的并行算法以及边界约束的并行模式搜索算法.
在第二章中,针对不可分的线性约束,给出了两个求解约束优化问题的PVD型算法.利用简约梯度来作为并行机上的PVD方向,使得计算更加简单.特别针对不等式线性约束优化问题,为了保证算法的收敛性,每步通过采取转轴运算来确定有效约束集合,得到拓广的简约梯度,找到一个下降的可行方向,我们以此方向作为PVD方向,得到了一般线性约束的PVD算法.这两个算法比M. V. Solodov提出的用投影梯度剩余函数作为PVD方向的计算简单,而且能够得到全局收敛性结果.
在第三章中,我们对M. Fukushima针对无约束优化问题提出的同步并行变量转换算法(PVT)框架进行了研究.PVT算法是对PVD算法的推广,PVD算法可以看做是PVT算法的特殊情况.PVT算法不需要将变量分为主要变量和辅助变量,只需要选择合适的变换矩阵将问题的变量空间变换到多个维数较小的变量子空间上,分解为多个子问题,进而进行并行计算.但是目前的此类方法,处理机相互独立处理各自的子问题,要等待所有的子问题都处理完毕后,才能执行同步,进入下一步迭代.这种算法很大程度上浪费了计算机的资源,不能有效实现计算和消息传递重叠的算法思想,因此我们研究了异步算法,使得求解过程中只要有一个子问题满足收敛条件,整个算法即可终止,节约了同步时间,从数值试验看出,改进算法大大提高了并行算法的效率.
在第四章中,我们在第三章的算法基础上,给出了一个求解大规模线性约束优化问题的异步并行变量转换算法.此算法利用了Fischer函数,将线性约束问题转化为与之等价的无约束优化问题,利用第三章中的无约束异步并行变量转换算法,得到了线性约束的PVT算法,文中证明了算法的全局收敛性,并且针对特殊化的问题,得到不依赖于处理机个数的线性收敛速度,充分体现了异步算法的优点,而原始的同步PVT算法的线性收敛速度与处理机个数成反比.
在第五章和第六章中,我们根据实际应用中往往出现函数的精确导数或近似导数不可求等问题,研究了直接搜索算法中的一类,模式搜索法.第五章中,我们针对无约束优化问题,将模式搜索方法应用于异构的分布式集群系统之上,研究了其并行算法,算法主要实现了搜索方向的并行,而不是单纯的函数值并行,经过数值实验的模拟,本算法是针对分布式异构并行系统的有效的并行模式搜索算法.
此外,针对边界约束的模式搜索算法,我们比较了它与无约束模式搜索算法之间的区别,指明了模式取法的不同,以及搜索方向的不同选择,将第五章中的并行算法进行推广,文章还给出了并行化算法的可行性证明,以及收敛性的说明.
最后,针对现有的一些优化问题的新算法,包括本文没有解决的问题,我们提出了进一步研究的课题.
This thesis is mainly on the study of parallel algorithm on unconstrained and sim-ple constrained optimization. Researches are carried through concerning the existing Parallel Variable Distribution algorithm (PVD) and Parallel Variable Transformation algorithm (PVT). On the ground of the former two parallel algorithms, the thesis demonstrates three improving algorithms in chapter two, three and four:PVD algo-rithm with linear inseparable constraints, asynchronous PVT algorithm with uncon-straint and partial asynchronous PVT algorithm on the large-scale linear constrained optimization. In chapter five and six, parallel algorithms on unconstrained pattern search method and on pattern search method with bound constraint are researched owing to pattern search method's effectiveness in dealing with actual problems, and its potential parallelism.
In chapter two, two type-PVD algorithms of inseparable linear constraint optimiza-tion are presented. We make reduced gradient as PVD direction in parallel computers to lessen computation. In order to maintain convergence of the new algorithm, we get the active constraint set by computing of coordinate rotation at every step, through which we have the expanding reduced gradient, a feasible descending direction. Then we take it as the PVD direction, and work out the PVD algorithm on general linear constraint optimization of inequation. These two algorithms are easier than projected gradient residual function proposed by Solodov, and we can have the whole convergence of the original problem.
We discuss M. Fukushima's PVT algorithm frame about unconstrained optimiza-tion in chapter three. PVT algorithm is the extension of PVD algorithm, which can also be viewed as the special case of PVT algorithm. PVT algorithm doesn't need to divide the variable into main variable and secondary variable. It just selects suit- able transforming matrix and transforms the variable space of the problem into multi variable subspaces of smaller dimension. Consequently, original problem is parted into multi sub-problems, which are processed parallel computation. But only after the processor finishes processing all the sub-problems respectively, is it able to carry out synchronously and get to next iteration point. This algorithm wastes computing re-sources extensively, and can not achieve computing and message-sending at the same time. So we study an asynchronous algorithm which means that as long as one of the sub-problems satisfies the condition of convergence, the whole computation will stop. This asynchronous algorithm saves synchronous time. From numerical experiments, we can see that the reformed algorithm improves the efficiency of parallel computation greatly.
Chapter four is devoted to a new asynchronous PVT algorithm on large-scale linear constrained optimization based on chapter three. The method adopts Fischer's function, and changes the linear constrained problem into the equivalent unconstrained optimization. We obtain the asynchronous PVT algorithm on the linear constrained problem. The thesis proves the whole convergence of the algorithm. And we get linear convergence rate independent of the number of processors pointing to the specialized problem. Compared with the original synchronous PVT, whose linear convergence rate is inversely proportional to the number of processors, this new algorithms shows the advantage of asynchronous algorithm.
Chapters five and six are concerned with pattern search method which is one type of the direct search methods. Pattern search method is meant to solve the problem in which accurate or approximate gradient of function is difficult to obtain. In chapter five, for unconstrained optimization, we apply pattern search method on distributed cluster system with asynchronous architecture, and work out its parallel algorithm. The algorithm mainly achieves parallelism of search directions, but not simple parallelism of function value. Through the simulation of numerical experiment, the algorithm is proved to be an effective parallel pattern search method on the cluster system with asynchronous architecture.
In addition, we compare the distinguishing features of bound constraint pattern search method with those of unconstraint pattern search method, and present the differences of mesh, and different choices of search direction. Then the parallel method mentioned in chapter five is expanded. Besides, the feasibility of this parallel method in chapter six is proved and convergence is illustrated in the thesis.
The last part is concerned with some topics that need further studies in the light of some new methods of the existing optimization problems including the unsolved ones in this thesis.
引文
[1]R. FLECHER, Practical Methods Of Optimization,2nd ed., John Wiley and Sons, Chichester, New York,1987.
[2]PH. E. GILL, W. MURRAY AND M. H. WRIGHT, Practical Optimization, Academic Press, New York,1982.
[3]A. FRIENDLANDER, J. M. MARTINEZ AND S. A. SANTOS, On the Resolution Of Linearly Constrained Convex Minimization Problems, SIAM J. Optimization, 1994, Vol.4, pp.331-339.
[4]C. KANZOW, An Unconstrained Optimization Technique For Large-Scale Lin-early Constrained Minimization Problems, Computing,1994, Vol.53, pp.101-117.
[5]M. C. FERRIS AND O. L. MANGASARIAN, Parallel Variable Distribution, SIAM J. Optimization,1994, Vol.4, pp.815-832.
[6]M. V. SOLODOV, New Inexact Parallel Variable Distribution Algorithms, Com-put. Optim. Appl.,1997, Vol.7, pp.165-182.
[7]M. V. SOLODOV, On The Convergence Of Constrained Parallel Variable Dis-tribution Algorithms, SIAM J. Optimization,1998, Vol.8, pp.187-196.
[8]C. A. SAGASTIZABAL AND M. V. SOLODOV, Parallel Variable Distribution For Constrained Optimization, Comput. Optim. Appli.,2002, Vol.22, pp.111-131.
[9]M. FUKUSHIMA, Parallel Variable Transformation In Unconstrained Optimiza-tion, SIAM J. Optimization,1998, Vol.8, pp.658-672.
[10]A. FISCHER, A Special Newton-type Optimization Method, Optimization,1992, Vol.24, pp.269-284.
[11]J. M. ORTEGA, Numerical Analysis, Second ed., Academic Press,1972.
[12]E. YAMAKAWA AND M. FUKUSHIMA, Testing Parallel Variable Transforma-tion, Comput. Optim. Appl.,1999, Vol.13, pp.1-22.
[13]L. P. PANG AND Z. Q. XIA, A PVT-TYPE Algorithm For Minimization A Nonsmooth Convex Function, Serdica Math. J.,2003, Vol.29, pp.11-32.
[14]S. P. HAN, Optimization By Updated Conjugate Subspaces, Numerical Analysis: Pitman Research Notes Mathematics Series 140,(Eds D. F. Griffiths, G. A. Watson)Longman Scientific and Technical, Burnt Mill, England,1986, Vol.5, pp.82-97.
[15]S. P. HAn AND G. Lou, A Parallel Algorithm For A Class Of Convex Pro-grams, SIAM J. Control Optim.,1988, Vol.26, pp.346-355.
[16]D. P. BERTSEKAS AND J. N. TSITSIKLIS, Parallel And Distributed Computa-tion:Numerical Methods, Prentize-Hall:Englewood Cliffs, New Jersey,1989.
[17]C. S. LIU AND C. H. TSENG, Parallel Synchronous And Asynchronous Space-decomposition Algorithms For Large-scale Minimization, Comput. Optim. Appl., 2000, Vol.17, pp.85-107.
[18]V. TORCZON, On the Convergence Of Pattern Search Algorithms, SIAM J. Optimization,1997, Vol.17, pp.1-25.
[19]D. LEVINE, Users Guide To The PGAPack Parallel Genetic Algorithm Library, Tech. Rep. ANL-95/18, Argonne National Laboratory, Argonne, Illinois,1995.
[20]V. TORCZON, PDS:Direct Search Methods For Unconstrained Optimization On Either Sequential Or Parallel Machines, Tech. Rep.92-09, Rice University, De-partment of Computation and Applied Mathematics, Houston, Texas,1991.
[21]P. D. HOUGH, T. G. KOLDA AND V. J. TORCZON, Asynchronous Parallel Pattern Search For Nonlinear Optimization, SIAM J. SCI. Comput.,2001, Vol. 23, pp.134-156.
[22]C. DAVIS, Theory Of Positive Linear Dependence, Amer. J. Math.,1954, Vol. 76, pp.733-746.
[23]M. SNIR, S. OTTO, S. HUSS-LEDERMAN, D. WALKER AND J. DONGARRA, MPI:The Complete Reference, The MIT Press, Cambridge, Massachusetts, Lon-don, England,1996.
[24]N. M. ALEXANDROV AND R. M. LEWIS, Comparative Properties Of Collab-orative Optimization To Mdo, Technical Report 99-14, ICASE, NASA Langley Research Center, Hampton, VA, July,1999.
[25]E. ANDERSON, Z. BAI, C. BIACHOF, J. DEMMEL, J. DONGARRA, J. Du CROZ, A. GREENBAUM, S. HAMMARLING, A. McKENNEY, S. OSTROUCHOV AND D. SORENSEN, LAPACK Users' Guide, SIAM Publications,1995.
[26]C. AUDET, Convergence Results For Pattern Search Algorithms Are Tight, Technical Report CRPC-TR98779, CRPC, Rice University,1998.
[27]B. M. AVERICK AND J. J. MORE, Evaluation Of Large-scale Optimization Problems On Vector And Parallel Architectures, SIAM J. Optimization,1994, Vol.4, pp.708-721.
[28]S. BALAY, W. GROPP, L. MCINNES AND B. SMITH, Efficient Management Of Parallelism In Object-oriented Numerical Software Libraries, In E. Arge, A. M. Bruaset and H. P. Langtangen, editors, Modern Software Tools in Scientific Computing. Birkhauser Press,1997.
[29]R. E. BIXBY AND A. MARTIN, Parallelizing The Dual Simplex Method, Tech-nical Report CRPC-TR95706, CRPC, Rice University,1997.
[30]L. S. BLACKFORD, J. CHOI, A. CLEARY, E. D'AZEVEDO, J. DEMMEL, I. DHILLON, J. DONGARRA, S. HAMMARLING, G. HENRY, A. PETITET, K. STAN-LEG, D. WALKER AND R. C. WHALEY, SCALAPACK Users' Guide, SIAM Publishers,1997.
[31]S. H. BOKHARI AND D. J. MAVRIPLIS, The Tera Multithreaded Architec-ture And Unstructured Meshes, Technical Report ICASE Interim Report No.33, ICASE, NASA Langeley Research Center, Hampton, VA,1998.
[32]R. H. BYRD, R. B. SCHNABEL AND M. H. SHULTZ, Parallel Quasi-newton Methods For Unconstrained Optimization, Technical Report, Department of Computer Science, University of Colorado, Boulder, CO,1990.
[33]T. F. COLEMAN, J. CZYZYK, C. SUN, M. WAGNER AND S. J. WRIGHT, PPCX:Parallel Software For Linear Programming, Proceedings of the Eighth SIAM Conference on Parallel Processing in Scientific Computing, SIAM Publi-cations,1997.
[34]J. E. DENNIS, JR. AND R. M. LEWIS, Problem Formulation And Other Op-timization Issues In Multidisciplinary Optimization, Technical Report CRPC-TR94469, CRPC, Rice University, Houston, TX,1994.
[35]J. FEO, S. KAHAN AND Z. Wu, Crash Analysis On The Tera MTA, Compu-tational Science and Enyineeriny,1998, Vol.5, pp.53-59.
[36]M. C. FERRIS AND O. L. MANGASARIAN, Parallel Constraint Distribution, SIAM Journal on Optimization,1991, Vol.1, pp.487-500.
[37]M. T. JONES AND P. E. PLASSMANN, An Efficient Parallel Iterative Solver For Large Sparse Linear Systems, Graph Theory and Sparse Matrix Computation, Springer-Verlag,1993, pp.229-245.
[38]M. T. JONES AND P. E. PLASSMANN, Scalable Iterative Solution Of Sparse Linear Systems, Parallel Computing,1994, pp.753-773.
[39]M. T. JONES AND P. E. PLASSMANN, Algorithm 740:Fortran Subroutines To Compute Improved Incomplete Cholesky Factorizations, ACM Trans, on Math-ematical Software,1995, pp.18-19.
[40]M. T. JONES AND P. E. PLASSMANN, An Improved Incomplete Cholesky Fac-torization, ACM Trans, on Mathematical Software,1995, pp.5-17.
[41]R. M. LEWIS AND V. J. TORCZON, A Globally Convergent Augmented La-grangian Pattern Search Algorithm For Optimization With General Constraints
And Simple Bounds, Technical Report 98-31, Institute for Computer Appli-cations in Science and Engineering, NASA Langley Research Center, Hamp-ton,VA,1998.
[42]J. J. MORE, B. WALENZ AND Z. Wu, Configuration Of Large, Confined Ionic Systems By Potential Energy Minimization, Working paper, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL,1996.
[43]J. SCHNEIDER AND T. H. WISE, Airline Crew Scheduling:Supercomputers And Algorithms, Greg Astfalk, editor, Applications on Advanced Architecture Computers, SIAM Publications,1996.
[44]V. TORCZON, Multi-directional Search:A Direct Search Algorithm For Par-allel Machines, Ph.D. Thesis 90-7, Department of Computational and Applied Mathematics, Rice University, Houston, TX,1990.
[45]V. TORCZON, On The Convergence Of The Multidirectional Search Algorithm, SIAM J. Optimization,1991, Vol.1, pp.123-145.
[46]C. AUDET AND J. E. DENNIS, A Pattern Search Filter Method For Nonlinear Programming Without Derivatives, SIAM J. Optim.,2004, Vol.14, pp.980-1010.
[47]R. M. LEWIS AND V. TORCZON, Pattern Search Algorithms For Bound Con-strained Minimization, SIAM J. Optim.,1999, Vol.19, pp.1082-1099.
[48]T. G. KOLDA, R. M. LEWIS AND V. TORCZON, Optimization By Direct Search:New Perspectives On Some Classical And Modern Methods, SIAM Re-view,2003, Vol.45, pp.385-482.
[49]T. G. KOLDA AND V. J. TORCZON, On The Convergence Of Asynchronous Parallel Pattern Search, SIAM J. Optim.,2004, Vol.14, pp.939-964.
[50]T. G. KOLDA AND V. J. TORCZON, Understanding Asynchronous Parallel Pattern Search, High Performance Algorithms and Software For Nonlinear Op-timization, G. DiPillo and A. Murli, eds., Kluwer Academic, Boston,2003, pp.316-335.
[51]R. M. LEWIS AND V. TORCZON, Pattern Search Methods For Linearly Con-strained Minimization, SIAM J. Optim.,2000, Vol.10, pp.917-941.
[52]C. AUDET AND J. E. DENNIS JR., Analysis Of Generalized Pattern Searches, SIAM J. Optimi.,2003, Vol.13, pp.889-903.
[53]T. G. KOLDA, Revisiting Asynchronous Parallel Pattern Search For Nonlinear Optimization, SIAM J. Optim.,2005, Vol.16, pp.563-586.
[54]W. TING AND S. LINPING, A Filter-Based Pattern Search Method For Uncon-strained Optimization, Numerical Math. J. of Chinese Universities,2006, Vol.15, pp.209-216.
[55]P. LIPING, S. JIE AND W. WEI, Two Parallel Distribution Algorithms For Convex Constrained Minimization Problems, Appl. Math, and Comput.,2007, Vol.186, pp.1762-1771.
[56]G. ZANGHIRATI AND L. ZANNI, A Parallel Solver For Large Quadratic Pro-grams In Training Support Vector Machines, Parallel Computing,2003, Vol.29, pp.535-551.
[57]M. YAMASHITA, K. FUJISAWA AND M. KOJIMA, SDPARA:SemiDefinite Programming Algorithm Parallel Version, Parallel Computing,2003, Vol.29, pp.1053-1067.
[58]K. NAKATA, M. YAMASHITA, K. FuJISAWA AND M. KOJIMA, A Parallel Primal-dual Interior-point Method For Semidefinite Programs Using Positive Definite Matrix Completion, Parallel Computing,2006, Vol.32, pp.24-43.
[59]C. DURAZZI, V. RUGGIERO AND G. ZANGHIRATI, Some Applications Via A Parallel Interior-Point Method, Science and Supercomputing at CINECA-Report,2001, pp.418-424.
[60]C. DURAZZI, V. RUGGIERO AND G. ZANGHIRATIi, Parallel Interior-point Method For Linear And Quadratic Programs With Special Structure, Journal of Optimization Theory and Application,2001, Vol.110, pp.289-313.
[61]C. DURAZZI AND V. RUGGIERO, Numerical Solution Of Special Linear And Quadratic Programs Via A Parallel Interior-point Method, Parallel Computing, 2003, Vol.29, pp.485-503.
[62]M. D'APUZZO AND M. MARINO, Parallel Computational Issues Of An Interior Point Method For Solving Large Bound-Constrained Quadratic Programming Problems, Parallel Computing,2003, Vol.29, pp.467-483.
[63]J. E. DENNIS, JR. AND V. TORCZON, Direct Search Methods On Parallel Machines, SIAM J. Optimization,1991, Vol.1, pp.448-474.
[64]R. FLECHER AND SVEN LEYFFER, Nonlinear Programming Without A Penalty Function, Mathematical Programming,2002, Vol.91, pp.239-269.
[65]I. D. COOPE AND M.S. MACKLEM, Parallel Jacobi Methods for Derivative-free Optimization on Parallel Or Distributed Processors, Australian and New Zealand Industrial and Applied Mathematics Journal,2005, Vol.46(E), pp. C719-C731.
[66]L. ZASLAVSKY, S. KAHAN, B. ELTON, K. MACSHOFF AND L. STERN, A Scalable Approach For Solving Irregular Sparse Linear Systems On The Tera MTA Multithreaded Parallel Shared-memory Computer, In The Proceed-inys of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, SIAM Publications,1999.
[67]J. E. DENNIS AND M. LEWIS, Problem Formulation And Other Optimization Issues In Multidisciplinary Optimization, Technical Report CRPC-TR92277, CRPC, Rice University,1992.
[68]S. A. SANTOS AND D. C. SORENSEN, A New Matrix-free Algorithm For The Large-scale Trust-region Subproblem, Technical Report TR95-20, Department of Computational and Applied Mathematics, Rice University, Houston, TX,1995.
[69]F. RENDL AND H. WOLKOWICZ, A Semidefinite Framework To Trust-region Subproblem With Applications To Large-scale Minimization, Technical Report CORR 94-32, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada,1994.
[70]S. G. NASH AND A. SOFER, A General Purpose Parallel Algorithm For Un-constrained Optimization, SIAM J. Optimization,1991, Vol.1, pp.530-547.
[71]S. G. NASH AND A. SOFER, Block Truncated-newton Methods For Parallel Optimization, Mathematical Programming,1989, Vol.45, pp.529-546.
[72]R. M. LEWIS AND V. TORCZON, A Global Convergent Augmented Lagrangian Pattern Search Algorithm For Optimization With General Constraints And Sim-ple Bounds, Technical Report TR 98-31, ICASE NASA Langley Research Cen-ter,1998.
[73]C. AUDET AND J. E. DENNIS, On the Convergence Of Mixed Integer Pattern Search Algorithms, Technical Report CRPC-TR98785, CRPC, Rice University, 1999.
[74]C. AUDET AND J. E. DENNIS, A Pattern Search Filter Method For Nonlinear Programming Without Derivatives, SIAM J. Optim.,2004, Vol.14, pp.980-1010.
[75]P. D. HOUGH AND J. C. MEZA, A Class Of Trust-region Methods For Paral-lel Optimization, Technical Report Sand98-8245, Sandia National Laboratories, 1998.
[76]A. J. BOOKER, J. E. DENNIS, Jr., P. D. FRANK, D. B. SERAFINI, V. TORCZON AND M. TROSSET, A Rigorous Framework For Optimization Of Ex-pensive Functions By Surrogates, Structural Optimization,1999.
[77]O. L. MANGASARIAN, Parallel Gradient Distribution In Unconstrained Opti-mization, SIAM Journal on Control and Optimization,1995, Vol.33, pp.1916-1925.
[78]席少霖编,非线性最优化方法,高等教育出版社,1990.
[79]简金宝,线性约束规划拓广的既约梯度法及其收敛性,经济数学,1993,Vol.1,pp.70-78.
[80]J. J. MORe, B. S. GRABOW AND K. E. HILLATROM, Testing Unconstrained Optimization Software, ACM Trans. Math. Software,1981, Vol.7, pp.17-41.
[81]S. G. NASH, Newton-type Minimization Via The Lanczos Method, SIAM J. on Numerical Analysis,1984, Vol.7, pp.770-788.
[82]S. S. OREN, Self-scaling Variable Metric (SSVM) Algorithms Part 2:Imple-mentation and Experiments, Management Science,1974, Vol.20, pp.863-874.
[83]A. R. CONN AND P. L. TOINT, An Algorithm Using Quadratic Interpolation For Unconstrained Derivative Free Optimization, Nonlinear Optimization and Applications, G. Di Pillo and F. Giannessi, eds., Kluwer Academic/Plenum Publishers, Vew York,1996, pp.27-47.
[84]I. COOPE AND C. PRICE, Frame-based Methods For Unconstrained Optimiza-tion, J. Optim Theory Appl.,2000, Vol.107, pp.261-274.
[85]I. D. COOPE AND C. J. PRICE, A Direct Search Conjugate Directions Algo-rithm For Unconstrained Minimization, ANZIAM J.2000, Vol.42, pp. C478-479.
[86]U. M. GAKCIA AND J. F. RODRIGUEZ, New Sequential Parallel Derivative-free Algorithms For Unconstrained Minimization, SIAM J. Optim.,2002, Vol. 13, pp.79-96.
[87]P. E. GILL, W. MURRAY AND M. H. WRIGHT, Practical Optimization, Aca-demic Press, London,1981.
[88]R. HOOKE AND T. A. JEEVES, Direct Search Solution Of Numerical And Statistical Problems, J.ACM,1961, Vol.8, pp.21-229.
[89]R. M. LEWIS AND TORCZON, Rank Ordering And Positive Bases In Pattern Search Algorithms, Technical Report 96-71, ICASE, NASA Langley Research Center, Hampton, VA,1996.
[90]R. M. LEWIS, V. TORCZON AND M. W. TROSSET, Direct Search Methods: Then And Now, Comput. Appl. Math.,2000, Vol.124, pp.191-207.
[91]S. LUCIDI AND M. SCIANDRONE, On The Global Convergence Of Derivative-free Methods For Unconstrained Optimization, SIAM J. Optim.,2002, Vol.13, pp.97-116.
[92]S. G. NASH AND E. SOFER, Linear And Nonlinear Programming, McGraw-Hill, New York,1996.
[93]J. NOCEDAL, Theory Of Algorithms For Unconstrained Optimization, Acta Nu-mer.,1992, Vol.1, pp.199-242.
[94]J. NOOEDAL AND S. WRIGHT, Numerical Optimization, Springer Ser. Oper. Res., Springer-Verlag, New York,1999.
[95]W. H. SWANN, Direct Search Methods, Numerical Methods for Unconstrained Optimization, W. Murray, ed., Academic Press, London, NewYork,1972, pp.13-28.
[96]V. TORCZON, On The Convergence Of The Multidirectional Search Algorithm, SIAM J. Optim.,1991, Vol.1, pp.123-145.
[97]P. WOLFE, Convergence Conditions For Ascent Methods, SIAM Rev.,1969, Vol.11, pp.226-235.
[98]W. Yu, Positive Basis And A Class Of Direct Search Techniques, Scientia Sinica, Special Issue of Mathematics,1979, Vol.1, pp.53-67.
[99]H. H. ROSENBROOK, An Automatic Method For Finding The Greatest Or Least Value Of A Function, Comput. J.,1960, Vol.3, pp.175-184.
[100]J. E. DENNIS, JR. AND J. WOODS, Optimization On Microcom-puters:The Nelder-Mead Simplex Algorithm, New Computing Environ-ments:Microcomputers in Large-Scale Computing, A. Wouk, ed., SIAM, Philadelphia,1987, pp.116-122.
[101]S. N. DEMING AND S. L. MORGAN, Simplex Optimization Of Variables In Analytical Chemistry, Analytical Chem.,1973, Vol.45, pp.278A-283A.
[102]L. ARILIIJO, Minimization Of Functions Having Lipschitz Continous First Partial Derivatives, Pacific J. Math.,1966, Vol.16, pp.1-3.
[103]A. A. GOLDSTEN, Constructive Real Analysis, Harper and Row, New York, 1967.
[104]G. E. P. Box, Evolutionary Operation:A Method For Increasing Industrial Productivity, Applied Statistics,1957, Vol.6, pp.81-101.
[105]M. J. Box, D. DAVIES AND W. H. SWANN, Non-Linear Optimization Tech-niques, ICI Monograph No.5, Oliver and Boyd, Edinburgh,1969.
[106]E. D. DOLAN, Pattern Search Behavior In Nonlinear Optimization, Hon-ors Thesis, Department of Computer Science, College of William and Mary, Williamsburg, VA, May 1999.
[107]A. R. CONN, N. I. M. GOULD AND P.L.TOINT, Trust-region Methods, MPS/SIAM Ser. Optim.1, SIAM, Philadelphia,2000.
[108]J. C. DUNN, Global And Asymptotic Convergence Rate Estimates For A Class Of Projected Gradient Processes, SIAM J. Control Optim.,1981, Vol.19, pp.368-400.
[109]W. YONGLI, C. LIFENG AND H. GUOPING, Sequential Systems Of Linear Equations Methods For General Constrained Optimization Problems without Strict Complemetarity, Journal of Computational and Applied Mathematics, 2005, Vol.182, pp.447-471.
[110]C. LIFENG, W. YONGLI AND H. GUOPING, A Feasible Active Set QP-FREE Method For Nonlinear Programming, SIAM. J. Optim.,2006, Vol.17, pp.401-429.