一种非单调滤子信赖域算法解线性不等式约束优化
A Nonmonotone Filter-trust-region Algorithm for Linear Inequality Constrained Optimization
本文给出了一种新的多维滤子算法结合非单调信赖域策略解线性约束优化.目标函数及其投影梯度的分量组成了新的多维滤子,并且与信赖域半径有关.当信赖域半径充分小时,新的滤子能接受试探点,避免算法无限循环.非单调信赖域策略保证了新算法的整体收敛性.目前为止,多维滤子算法局部收敛性分析仍然没有解决,在合理假设下,我们分析了新算法的局部超线性收敛性.数值结果验证了算法的有效性.
We propose a new multidimensional filter algorithm with a nonmonotone trust-region strategy for linear inequality constrained optimization. The objective function and the components of its projection gradient constitute a new multidimensional filter which is related to the trust-region radius. When the trust-region radius is small enough, the new filter can accept the trial point to avoid the infinite cycle of the algorithm. The nonmonotone trust-region strategy maintains global convergence of the new algorithm. The analysis of local convergence on multidimensional filter algorithms is a problem that has not been solved so far. We analyze the local superlinear convergence of the new algorithm under some suitable conditions. Numerical results show that the new approach is efficient.
线性不等式约束优化 / 多维滤子 / 非单调信赖域策略 / 局部收敛性 {{custom_keyword}} /
linear inequality constrained optimization / multidimensional filter / nonmonotone trust-region strategy / local convergence {{custom_keyword}} /
[1] Andrei N., An unconstrained optimization test functions collection, Adv. Model. Optim., 2008, 10:147-161.
[2] Bai Y. Q., Wang G. Q., Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, Acta Mathematica Sinica, English Series, 2007, 23:2027-2042.
[3] Bai Y. Q., Guo J. L., Roos C., A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms, Acta Mathematica Sinica, English Series, 2009, 25:2169-2178.
[4] Chen Y., Sun W., A dwindling filter line search method for unconstrained optimization, Math. Comput., 2015, 84:187-208.
[5] Coleman T. F., Li Y., A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints, Math. Program. Ser. A, 2000, 88:1-31.
[6] Conn A. R., Gould N. I. M., Toint Ph. L., Trust Region Methods, MPS/SIAM Ser. Optim. 1, SIAM, Philadelphia, 2000.
[7] Dolan E. D., Moré J. J., Benchmarking optimization software with performance profiles, Math. Program., 2002, 91:201-213.
[8] Fatemi M., Mahdavi-Amiri N., A filter trust-region algorithm for unconstrained optimization with strong global convergence properties, Comput. Optim. Appl., 2012, 52:239-266.
[9] Fletcher R., Leyffer S., Nonlinear programming without a penalty function, Math. Program., 2002, 91:239-269.
[10] Gould N. I. M., Toint Ph. L., Sainvitu C., A filter-trust-region method for unconstrained optimization, SIAM J. Optim., 2005, 16:341-357.
[11] Gould N. I. M., Leyffer S., Toint Ph. L., A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares, SIAM J. Optim., 2004, 15:17-38.
[12] Gould N. I. M., Orban D., Toint Ph. L., CUTEr, a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 2003, 29:373-394.
[13] Grippo L., Lampariello F., Ludidi S., A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 1986, 23:707-716.
[14] Gu R., Yuan Y. X., A partial first-order affine-scaling method, Acta Mathematica Sinica, English Series, 2019, 35:1-16.
[15] Gu C., Zhu D., Convergence of a three-dimensional dwindling filter algorithm without feasibility restoration phase, Numerical Functional Analysis and Optimization, 2016, 37:324-341.
[16] Su K., Liu Y., A modified filter trust region method for nonlinear programming, Acta Mathematica Sinica, Chinese Series, 2009, 52:1157-1164.
[17] Yuan G. L., Wei Z. X., The superlinear convergence analysis of a nonmonotone BFGS algorithm on convex objective functions, Acta Mathematica Sinica, English Series, 2008, 4:35-42.
[18] Zhu D., A new affine scaling interior point algorithm for nonlinear optimization subject to linear equality and inequality constraints, J. Comput. Appl. Math., 2003, 161:1-25.
[19] Zhu D., Superlinearly convergent affine scaling interior trust-region method for linear constrained LC1 minimization, Acta Mathematica Sinica, English Series, 2008, 24:2081-2100.
[20] Zhu Z. B., Jian J. B., An improved feasible QP-free algorithm for inequality constrained optimization, Acta Mathematica Sinica, English Series, 2012, 28:2475-2488.
国家自然科学基金资助项目(11971302);上海立信会计金融学院序伦学者培养计划
/
〈 | 〉 |