非线性半定规划问题的逐次线性化方法
|
摘要
半定规划是线性与非线性规划的一种推广,在组合优化、控制论、系统论、滤波器的设计、临床医学等方面都有很广泛的应用.研究非线性半定规划问题的算法及其理论具有重要的理论意义和应用价值.
许多线性与非线性规划的算法被成功地推广应用于求解非线性半定规划问题,例如光滑与非光滑牛顿法、势下降方法、原始对偶内点法、序列半定规划方法和增广拉格朗日方法等,这些方法有一个共同点：借助于某个罚函数作为效益函数来判断当前尝试步是否可以接受,即要求效益函数值有充分下降,但罚因子的选取是一个复杂而困难的问题Fletcher等人提出的过滤方法是不使用罚函数的一种新方法,其基本原理类似于多目标规划的处理方法,这种思想在处理非线性半定规划问题时,滤子集的存储是一个值得考虑的问题.
本文对非线性不等式约束半定规划问题提出一种新的逐次线性化方法,新算法既不要求罚函数单调下降,也不使用过滤技巧,从而避免了迭代过程中滤子集的存储.另外,尝试步的接受准则仅仅依赖于目标函数和约束违反度,因此,罚函数中对应于成功迭代点的罚因子不需要单调增加.为了判断尝试步是否可以接受,新算法或者要求违反约束的度量有足够改善,或者在约束违反度的一个合理范围内要求目标函数值充分下降,在通常的假设条件下,分析了新算法的适定性及全局收敛性.最后,给出了非线性半定规划问题的数值试验结果,结果表明了新算法的有效性.
Semidefnite programming is an extension of linear and nonlinear programming.There are very extensive applications in many felds, such as combinatorial optimiza-tion, control theory, system theory, design of flter, clinical medicine, etc. Therefore,the research of the algorithms and their theory for nonlinear semidefnite programmingis of great theoretical signifcance and application value.
Many algorithms for linear and nonlinear programming are successfully appliedto solve nonlinear semidefnite programming problems, for example, smooth and nons-mooth Newton methods, potential reduction methods, primal-dual interior point meth-ods, sequential semidefnite programming methods and augmented Lagrangian meth-ods, etc. There is a common feature of the above methods: using some penalty functionas merit function to decide whether the current trial step is accepted or not. But theselection of the penalty factor is a complex and difcult problem. Filter techniquepresented by Fletcher et al is a new method without using penalty function. Its basicprinciple is similar to the processing of multiobjective programming. The storage offlter set is a problem when it is applied to solve nonlinear semidefnite programming.
A new successive linearization method is presented to solve nonlinear semidefniteprogramming with nonlinear inequality constraints. The new method does not requirethe penalty function to be reduced and does not use flter technique. The storage offlter set is avoided. The penalty parameter sequence corresponding to the successfuliterate point does not increase monotonically. To decide whether the trial step can beaccepted or not, the new method requires the measure of constraint violation to be im-proved or the objective function value to be improved within the measure of feasibilitycontrol. Under the usual assumptions, we prove that the algorithm is welldefned andconvergent. Finally, the preliminary numerical results are reported.
许多线性与非线性规划的算法被成功地推广应用于求解非线性半定规划问题,例如光滑与非光滑牛顿法、势下降方法、原始对偶内点法、序列半定规划方法和增广拉格朗日方法等,这些方法有一个共同点：借助于某个罚函数作为效益函数来判断当前尝试步是否可以接受,即要求效益函数值有充分下降,但罚因子的选取是一个复杂而困难的问题Fletcher等人提出的过滤方法是不使用罚函数的一种新方法,其基本原理类似于多目标规划的处理方法,这种思想在处理非线性半定规划问题时,滤子集的存储是一个值得考虑的问题.
本文对非线性不等式约束半定规划问题提出一种新的逐次线性化方法,新算法既不要求罚函数单调下降,也不使用过滤技巧,从而避免了迭代过程中滤子集的存储.另外,尝试步的接受准则仅仅依赖于目标函数和约束违反度,因此,罚函数中对应于成功迭代点的罚因子不需要单调增加.为了判断尝试步是否可以接受,新算法或者要求违反约束的度量有足够改善,或者在约束违反度的一个合理范围内要求目标函数值充分下降,在通常的假设条件下,分析了新算法的适定性及全局收敛性.最后,给出了非线性半定规划问题的数值试验结果,结果表明了新算法的有效性.
Semidefnite programming is an extension of linear and nonlinear programming.There are very extensive applications in many felds, such as combinatorial optimiza-tion, control theory, system theory, design of flter, clinical medicine, etc. Therefore,the research of the algorithms and their theory for nonlinear semidefnite programmingis of great theoretical signifcance and application value.
Many algorithms for linear and nonlinear programming are successfully appliedto solve nonlinear semidefnite programming problems, for example, smooth and nons-mooth Newton methods, potential reduction methods, primal-dual interior point meth-ods, sequential semidefnite programming methods and augmented Lagrangian meth-ods, etc. There is a common feature of the above methods: using some penalty functionas merit function to decide whether the current trial step is accepted or not. But theselection of the penalty factor is a complex and difcult problem. Filter techniquepresented by Fletcher et al is a new method without using penalty function. Its basicprinciple is similar to the processing of multiobjective programming. The storage offlter set is a problem when it is applied to solve nonlinear semidefnite programming.
A new successive linearization method is presented to solve nonlinear semidefniteprogramming with nonlinear inequality constraints. The new method does not requirethe penalty function to be reduced and does not use flter technique. The storage offlter set is avoided. The penalty parameter sequence corresponding to the successfuliterate point does not increase monotonically. To decide whether the trial step can beaccepted or not, the new method requires the measure of constraint violation to be im-proved or the objective function value to be improved within the measure of feasibilitycontrol. Under the usual assumptions, we prove that the algorithm is welldefned andconvergent. Finally, the preliminary numerical results are reported.
引文
[1] Todd M.J., Semidefnite optimization, Acta Numer.,2001,10:515-560.
[2] Vandenberghe L., Boyd S., Semidefnite programming, SIAM Review,1996,38:49-95.
[3] Wolkowicz H., Saigal R., Vandenberghe L., eds., Handbook of Semidefnite Program-ming, Boston-Dordrecht-London: Kluwer Academic Publishers,2000.
[4] Kanzow C., Nagel C., Kato H., et al., Successive linearization methods for nonlinearsemidefnite programs, Comput. Optim. Appl.,2005,31:251-273.
[5] Li C.J., Sun W.Y., On flter-successive linearization methods for nonlinear semidefniteprogramming, Sci. China Ser. A,2009,52:2341-2361.
[6] Toh K.C., Tutuncu R.H., Todd M.J., SDPT3version4.0-a MATLAB software forsemidefnite-quadratic-linear programming.http://www.math.nus.edu.sg/mattohkc/sdpt3.html,2009.2.
[7] Toh K.C., Tutuncu R.H., Todd M.J., On the implementation and usage of SDPT3-aMATLAB software package for semidefnite-quadratic-linear programming version4.0(Draft), http://www.math.nus.edu.sg/mattohkc/guide4-0-draft.pdf,17July,2006.
[8] Tutuncu R.H., Toh K.C., Todd M.J., Solving semidefnite-quadratic-linear programsusing SDPT3, Math. Prog.,2003,95:189-217.
[9] Correa R., Ramirez H., A global algorithm for nonlinear semidefnite programming,SIAM J. Optim.,2004,15:303-318.
[10] Li C.J., Sun W.Y., A flter-sequential semidefnite programming method for nonlinearsemidefnite programming, Technical Report Opt-07-03, School of Mathematics andComputer Science, Nanjing Normal University,2007.
[11] Nie J.W., Yuan Y.X., A potential reduction algorithm for an extended SDP problem,Sci. China Ser. A,2000,43:35-46.
[12] Sun J., Sun D.F., Qi L.Q., A squared smoothing Newton method for nonsmooth matrixequations and its applications in semidefnite optimization problems, SIAM J. Optim.,2004,14:783-806.
[13] Jerre F., An interior method for nonconvex semidefnite programs, Optim. Eng.,2000,1:347-372.
[14] Yamashita H., Yabe H., Harada K., A primal-dual interior point method for nonlinearsemidefnite programming, Technical report, Department of Mathematical InformationScience, Faculty of Science, Tokyo University of Science,2007.
[15] Li C.J., Sun W.Y., A Nonsmooth Newton-Type Method for Nonlinear SemidefniteProgramming, J. Nanjing Norm. Univ. Nat. Sci. Ed.,2008,31(2):1-7.
[16] Sun D., Sun J., Zhang L., The rate of convergence of the augmented Lagrangian methodfor nonlinear semidefnite programming, Math. Prog.,2008,114:349-391.
[17]李成进,孙文瑜,非凸半定规划的广义Fakars引理及最优性条件,高校计算数学学报,2008,30：184-192.
[18]Shapiro A., First and second order analysis of nonlinear semidefinite programs, Math. Prog.,1997,77:301-320.
[19]Bonnans J.F., Commintti R., Shapiro A., Sensitivity analysis of optimization problem under second order regularity constraints, Math. Oper. Res.,1998,23:803-832.
[20]Fletcher R., Leyffer S., Nonlinear programming without a penalty function, Math. Prog.,2002,91:239-269.
[21]Fletcher R., Leyffer S., Toint Ph.L., A brief history of filter methods, Optimization Online, September26,2006(revised October9,2006).
[22]Walter G., Hector R., A filter algorithm for nonlinear semidefinite programming, Com-put. Appl. Math.,2010,29(2):297-328.
[23]Zoppke-Donaldson C., A tolerance-tube approach to sequential quadratic programming with applications, PhD Thesis, Department of Mathematics and Computer Science, University of Dundee, Dundee, Scotland, UK,1995.
[24]Ulbrich M., Ulbrich S., Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function, Math. Prog.,2003,95:103-135.
[25]Chen Z.W., A penalty-free-type nonmonotone trust-region method for nonlinear con-strained optimization, Appl. Math. and Comput.,2006,173:1014-1046.
[26]Gould N.I.M., Toint Ph.L., Nonlinear programming without a penalty function or a filter, Math. Prog.,2010,122:155-196.
[27]焦玉洁,约束优化问题的一类新的无惩罚型方法,苏州大学,硕士论文,2011.
[28]Borchers B., SDPLIB1.2, a library of semidefinite programming test problems, Optim. Methods Softw.,1999,11:597-611.
[2] Vandenberghe L., Boyd S., Semidefnite programming, SIAM Review,1996,38:49-95.
[3] Wolkowicz H., Saigal R., Vandenberghe L., eds., Handbook of Semidefnite Program-ming, Boston-Dordrecht-London: Kluwer Academic Publishers,2000.
[4] Kanzow C., Nagel C., Kato H., et al., Successive linearization methods for nonlinearsemidefnite programs, Comput. Optim. Appl.,2005,31:251-273.
[5] Li C.J., Sun W.Y., On flter-successive linearization methods for nonlinear semidefniteprogramming, Sci. China Ser. A,2009,52:2341-2361.
[6] Toh K.C., Tutuncu R.H., Todd M.J., SDPT3version4.0-a MATLAB software forsemidefnite-quadratic-linear programming.http://www.math.nus.edu.sg/mattohkc/sdpt3.html,2009.2.
[7] Toh K.C., Tutuncu R.H., Todd M.J., On the implementation and usage of SDPT3-aMATLAB software package for semidefnite-quadratic-linear programming version4.0(Draft), http://www.math.nus.edu.sg/mattohkc/guide4-0-draft.pdf,17July,2006.
[8] Tutuncu R.H., Toh K.C., Todd M.J., Solving semidefnite-quadratic-linear programsusing SDPT3, Math. Prog.,2003,95:189-217.
[9] Correa R., Ramirez H., A global algorithm for nonlinear semidefnite programming,SIAM J. Optim.,2004,15:303-318.
[10] Li C.J., Sun W.Y., A flter-sequential semidefnite programming method for nonlinearsemidefnite programming, Technical Report Opt-07-03, School of Mathematics andComputer Science, Nanjing Normal University,2007.
[11] Nie J.W., Yuan Y.X., A potential reduction algorithm for an extended SDP problem,Sci. China Ser. A,2000,43:35-46.
[12] Sun J., Sun D.F., Qi L.Q., A squared smoothing Newton method for nonsmooth matrixequations and its applications in semidefnite optimization problems, SIAM J. Optim.,2004,14:783-806.
[13] Jerre F., An interior method for nonconvex semidefnite programs, Optim. Eng.,2000,1:347-372.
[14] Yamashita H., Yabe H., Harada K., A primal-dual interior point method for nonlinearsemidefnite programming, Technical report, Department of Mathematical InformationScience, Faculty of Science, Tokyo University of Science,2007.
[15] Li C.J., Sun W.Y., A Nonsmooth Newton-Type Method for Nonlinear SemidefniteProgramming, J. Nanjing Norm. Univ. Nat. Sci. Ed.,2008,31(2):1-7.
[16] Sun D., Sun J., Zhang L., The rate of convergence of the augmented Lagrangian methodfor nonlinear semidefnite programming, Math. Prog.,2008,114:349-391.
[17]李成进,孙文瑜,非凸半定规划的广义Fakars引理及最优性条件,高校计算数学学报,2008,30：184-192.
[18]Shapiro A., First and second order analysis of nonlinear semidefinite programs, Math. Prog.,1997,77:301-320.
[19]Bonnans J.F., Commintti R., Shapiro A., Sensitivity analysis of optimization problem under second order regularity constraints, Math. Oper. Res.,1998,23:803-832.
[20]Fletcher R., Leyffer S., Nonlinear programming without a penalty function, Math. Prog.,2002,91:239-269.
[21]Fletcher R., Leyffer S., Toint Ph.L., A brief history of filter methods, Optimization Online, September26,2006(revised October9,2006).
[22]Walter G., Hector R., A filter algorithm for nonlinear semidefinite programming, Com-put. Appl. Math.,2010,29(2):297-328.
[23]Zoppke-Donaldson C., A tolerance-tube approach to sequential quadratic programming with applications, PhD Thesis, Department of Mathematics and Computer Science, University of Dundee, Dundee, Scotland, UK,1995.
[24]Ulbrich M., Ulbrich S., Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function, Math. Prog.,2003,95:103-135.
[25]Chen Z.W., A penalty-free-type nonmonotone trust-region method for nonlinear con-strained optimization, Appl. Math. and Comput.,2006,173:1014-1046.
[26]Gould N.I.M., Toint Ph.L., Nonlinear programming without a penalty function or a filter, Math. Prog.,2010,122:155-196.
[27]焦玉洁,约束优化问题的一类新的无惩罚型方法,苏州大学,硕士论文,2011.
[28]Borchers B., SDPLIB1.2, a library of semidefinite programming test problems, Optim. Methods Softw.,1999,11:597-611.