Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (3): 53-56.

Previous Articles     Next Articles

Efficient optimization method for line search

LI Jiongcheng, XIAO Henghui, LI Guiyu   

  1. The Key Wireless Network Optimization Center of Guangzhou, Guangdong Planning and Designing Institute of Telecommunications Company, Guangzhou 510630, China
  • Online:2013-02-01 Published:2013-02-18

高效的线搜索寻优方法

李炯城,肖恒辉,李桂愉   

  1. 广东省电信规划设计院有限公司 广州市无线网络优化重点工程中心,广州 510630

Abstract: In the engineering fields of computer optimization, multi-function of optimization is needed to apply. Line search is the key technology to solve the optimal step on which the search direction is known in multi variables function optimization. Aiming at proposing an efficient line search method, line search is researched in detail, and a new line search optimization method is proposed which is Cantor-Like method. The main method is that the limitation that two test points must be kept in Fibonacci method is removed. The search range is divided into three same ranges. Two ranges are decided to be remored according to the derivative of test points. Proved by theory and experience, the proposed method is more efficient than the two methods mentioned above, achieving higher converging rate. One of the most important conclusions is that the converging rate of Cantor-Like is high-order infinitesimal of the two methods. On the occasion of requiring high accuracy, the proposed method can be more advantageous. Furthermore, this method is very adaptive, not only for convex function, but also for concave function.

Key words: optimization method, Cantor-Like method, 0.618 method, Fibonacci method, line search

摘要: 在涉及计算机寻优等许多工程领域,都需要使用多元函数的最优化。线搜索是多元函数的最优化中已知搜索方向求最优步长的关键技术。为了提出一种高效的线搜索算法,对线搜索进行详细研究,提出一种新的线搜索寻优方法——类康托法。主要方法是去除了Fibonacci法中两个试探点必须保留一个的限制,每次把搜索区间三等分,根据试探点的导数值,来决定去除哪两个子区间。通过理论和实例的证明,结果发现类康托法比0.618法和Fibonacci法更高效,计算速度更快。其中最重要的结论是类康托法为这两种方法收敛速度的高阶无穷小。特别是在精度要求很高的时候,类康托法比这两种算法具有更明显的优势。此外,该方法具有较强的适用性,不但能用于凸函数,也能用于凹函数。

关键词: 寻优方法, 类康托法, 0.618法, 斐波那契法, 线搜索