从数值最优化方法到学习最优化方法

doi:10.15960/j.cnki.issn.1007-6093.2019.04.001

摘要/Abstract

摘要： 传统最优化问题的求解方法主要是以梯度法为基础的数值最优化方法，它是解析与数值计算相结合的迭代求解方法，是一种基于固定模式的最优化方法.算法的迭代过程实质上是对迭代点进行非线性变换的过程，该非线性变换是通过一系列方向和步长来实现.对于最优化问题的每一个实例，都需要从头到尾执行整个算法，计算复杂度是固定的.一旦算法被程序实现，算法的效率（计算精度和复杂度）就被固定.人工智能解决问题的方法都具有学习功能.随着人工智能，特别是深度学习的兴起，学习类方法在一些领域取得了巨大的成功，如图像识别（特别是人脸识别、车牌识别、手写字符识别等）、网络攻击防范、自然语言处理、自动驾驶、金融、医疗等.本文从新的视角研究传统的数值最优化方法和智能优化方法，分析其特点，由此引出学习最优化方法，并对它们进行了对比，提出了学习最优化方法的设计思路.最后，以组合最优化为例，对该类方法的设计原理进行阐述.

关键词: 人工智能, 深度学习, 数值最优化方法, 学习最优化方法

Abstract: The traditional optimization method based on the gradient solver is mainly the numerical optimization method. It is an iterative solution method combining analytical and numerical calculation and is an optimization method based on fixed mode. The iterative process of the numerical optimization algorithm is essentially the process of nonlinear transformation of the iterative point, which is realized by a series of directions and steps. For every instance of optimization problem, the whole algorithm needs to be executed from the beginning to the end, and the computational complexity is fixed. Once the algorithm is programmed, the efficiency (accuracy and complexity) of the algorithm is fixed. With the development of artificial intelligence, especially deep learning, learning methods have made great success in some fields, such as image recognition (especially face recognition, license plate recognition, handwritting recognition, etc.), network attack prevention, natural language processing, automatic driving, finance, medical treatment, etc. This paper studies the traditional numerical optimization method and intelligent optimization method from a new perspective, analyzes their characteristics respectively. Then we not only propose the learning optimization method but also put forward the design idea of learning optimization method. Finally, we take combinatorial optimization as an example to explain the design principle of this kind of method.

Key words: artificial intelligence, deep learning, numerical optimization, learning optimization

中图分类号:

郭田德, 韩丛英. 从数值最优化方法到学习最优化方法[J]. 运筹学学报, 2019, 23(4): 1-12.

GUO Tiande, HAN Congying. From numerical optimization method to learning optimization method[J]. Operations Research Transactions, 2019, 23(4): 1-12.

参考文献

[1] Papadimitriou C H, Steiglitz K. 组合最优化算法和复杂性[M]. 刘振宏, 蔡茂诚, 译. 北京:高等教育出版社, 1988.
[2] Fletcher R. Practical Methods of Optimization[M]. Chichester:John Wiley & Sons, 2008.
[3] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京:科学出版社, 2007.
[4] 袁亚湘. 非线性优化计算方法[M]. 北京:科学出版社, 2008.
[5] Nesterov Y. A method of solving a convex programming problem with convergence rate O(1/√k)[J]. Soviet Mathematics Doklady, 1983, 27:372-376.
[6] Fletcher R, Powell M J D. A rapid convergent descent method for minimization[J]. The Computer Journal, 1963, 6:163-168.
[7] Broyden C G. A class of methods for solving nonlinear simultaneous equations[J]. Mathematics of Computation, 1965, 19:577-593.
[8] Liu D, Nocedal J. On the limited memory method for large scale optimization[J]. Mathematical Programming, 1989, 45(3):503-528.
[9] Li D H, Fukushima M. A modified BFGS method and its global convergence in nonconvex minimization[J]. Journal of Computational and Applied Mathematics, 2001, 129:15-35.
[10] Yuan Y. An example of only linearly convergence of trust region algorithms for nonsmooth optimization[J]. IMA Journal of Numerical Analysis, 1984, 4:327-335.
[11] Yuan Y. Conditions for convergence of trust region algorithms for nonsmooth optimization[J]. Mathematical Programming, 1985, 31:220-228.
[12] Yuan Y. On the superlinear convergence of a trust region algorithm for nonsmooth optimization[J]. Mathematical Programming, 1985, 31:269-285.
[13] Dai Y, Yuan Y. A nonlinear conjugate gradient method with a strong global convergence property[J]. SIAM Journal on Optimization, 1999, 10(1):177-182.
[14] Lemaréchal C, Strodiot J J, Bihain A. On a bundle algorithm for nonsmooth optimization[J]. Nonlinear Programming, 1981, 4:245-282.
[15] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1):183-202.
[16] Glowinski R, Marroco A. On the solution of a class of nonlinear Dirichlet problems by a penalty-duality method and finite elements of order one[J]. ESAIM:Mathematical Modelling and Numerical Analysis, 1975, 9(R2):41-76.
[17] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximations[J]. Computers and Mathematics with Applications, 1976, 2(1):17-40.
[18] Boyd S, Parikh N, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1):1-122.
[19] 何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1):1-31.
[20] Bottou, Léon, et al. Optimization methods for large-scale machine learning[J]. SIAM Review 60, 2018, 223-311.
[21] Schrijver A. Combinatorial Optimization:Polyhedron and Efficiency[M]. Berlin:Springer-Verlag, 2003.
[22] Korte B, Vygen J. Combinatorial Optimization:Theory and Algorithm[M]. Berlin:Springer-Verlag, 2012.
[23] Vazirani V V. Approximation Algorithms[M]. Berlin:Springer-Verlag, 2001.
[24] Williamson D P, Shmoys D B. The Design of Approximation Algorithms[M]. New York:Cambridge University Press, 2011.
[25] Arora S, Barak B. Computational Complexity:A Modern Approach[M]. New York:Cambridge University Press, 2009.
[26] Eiben A E, Smith J E. Introduction to Evolutionary Computing[M]. New York:Springer, 2003.
[27] 郭田德, 韩丛英, 李明强. 逐层数据再表达的前后端融合学习的理论及其模型和算法[J]. 中国科学(信息科学), 2019, 49(6):739-759.
[28] Lecun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[C]//Proceedings of the IEEE, 1998, 86(11):2278-2324.
[29] Yoshua Bengio, Andrea Lodi, Antoine Prouvost. Machine learning for combinatorial optimization:a methodological tour d'horizon[J]. arXiv:1811.06128, 2018.
[30] Elias Boutros Khalil, Pierre Le Bodic, Song L, et al. Learning to branch in mixed integer programming[C]//Proceeding of the Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[31] Léon Bottou, Frank E Curtis, Jorge Nocedal. Optimization methods for large-scale machine learning[J]. SIAM Review, 2018, 60(2):223-311.
[32] Marcin Andrychowicz, Misha Denil, Sergio Gomez, et al. Learning to learn by gradient descent by gradient descent[J]. Advances in Neural Information Processing Systems, 2016:3981-3989.
[33] Alejandro Marcos Alvarez, Quentin Louveaux, Louis Wehenkel. A machine learning-based approximation of strong branching[J]. INFORMS Journal on Computing, 2017, 29(1):185-195.
[34] He He, Hal Daume III, Jason M Eisner. Learning to search in branch and bound algorithms[J]. Advances in Neural Information Processing Systems, 2014:3293-3301.
[35] Anton Milan, Seyed Hamid Rezatofighi, Ravi Garg, et al. Data-driven approximations to np-hard problems[C]//Proceedings of the Conference on Artificial Intelligence, San Francisco, 2017:1453-1459.
[36] Oriol Vinyals, Meire Fortunato, Navdeep Jaitly. Pointer networks[C]//Proceedings of the Advances in Neural Information Processing Systems, Montreal, 2015:2692-2700.
[37] Irwan Bello, Hieu Pham, Quoc V Le, et al. Neural combinatorial optimization with reinforcement learning[J]. arXiv:1611.09940, 2016.
[38] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, et al. Reinforcement learning for solving the vehicle routing problem[J]. Advances in Neural Information Processing Systems, 2018:9839-9849.
[39] Elias Khalil, Dai H J, Zhang Y Y, et al. Learning combinatorial optimization algorithms over graphs[C]// Proceedings of the Advances in Neural Information Processing Systems, Long Beach, 2017:6348-6358.
[40] 唐思琦. 基于深度学习的组合优化问题求解及其应用[M]. 北京:中国科学院大学, 2019.
[41] Ilya Sutskever, Oriol Vinyals, Quoc V Le. Sequence to sequence learning with neural networks[C]//Proceedings of the Advances in Neural Information Processing Systems, Montreal, 2014:3104-3112.
[42] Kyunghyun Cho, Bart Van MerriÄenboer, Caglar Gulcehre, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[J]. arXiv:1406.1078, 2014.
[43] Dzmitry Bahdanau, Kyunghyun Cho, Yoshua Bengio. Neural machine translation by jointly learning to align and translate[J]. arXiv:1409.0473, 2014.
[44] 郭田德, 韩丛英, 唐思琦. 组合优化的机器学习求解方法[M]. 北京:科学出版社, 2019.