一类二次规划反问题解法的数值比较
|
摘要
在一般的优化模型中，通常都假定与目标函数决策变量相关的参数值或约束集合的参数值是已知的，我们求解一个优化问题就是在已知这些参数值的条件下，找到问题的最优解。然而在实际应用中有很多例子，我们只能知道参数的估计值以及从试验，观察，经验中获得的最优解，需要计算出参数的精确值。本文所要讨论的二次规划反问题就是在已知问题参数估计值的前提下，尽可能小的调整给定二次规划问题的参数值，使己知的可行解成为最优解。尽管对于反问题很多学者进行了深入的研究，做了很多工作，取得了令人瞩目的成就，但大多是组合优化发面的研究，在连续优化反问题方面进展比较小，本文对[1]中提出的一类二次规划反问题的数值求解进行探讨。
在第一章介绍了这个问题的最小化模型，它是一个正半定锥约束模型。
在第二章推导这个二次规划反问题的对偶问题，它是一个线性约束半光滑可微的凸规划问题，变量的个数比原反问题的少的多，只需求这个对偶问题的最优解就可以得到原问题的最优解。我们采用了[1]中的增广拉格朗日方法求解对偶问题，集中比较子问题的不同数值方法的求解对计算效果的影响。我们采用拟牛顿法和牛顿法两个方法对子问题求解，比较它们的数值试验的结果，发现采用拟牛顿法求解子问题的方法比采用牛顿法求解子问题的方法的计算效果好得多。
在第三章中，我们用障碍函数法重新解这个二次规划反问题的对偶问题。首先给出了关于问题的凸性的证明，说明采用障碍函数法的合理性，在障碍函数的子问题求解中，我们同样采用拟牛顿法的BFGS算法配合Armijo线搜索。同样对于这个算法也给出了数值试验检验该算法的有效性，数值结果表明障碍函数法在求解此问题时没有增广拉格朗日方法有效。
In an optimization model there are parameters associated with decision variables in theobjective function or in the constraint set. When solving the optimization problem, we usuallyassume that these parameter values are known and we need to find an optimal solution to it.However, there are many instances in the practice, in which we only know some estimates forparameter values, but we may have certain optimal solutions from experience, observations orexperiments. An inverse optimization problem is to find values of parameters which make theknown solutions optimal and which differ from the given estimates as little as possible. Thereare many important contributions to inverse optimization and a large number of inversecombinatorial optimization problems have been studied, but for continuous optimization, wedo not see much study on their inverse problem. In this paper, our concern is the numericalcomparison of different methods for solving a type of inverse quadratic programmingproblems introduced in[1].
Chapter 1 introduces the inverse quadratic programming problem, which is aminimization problem with a positive semidefinite cone constraint.
Chapter 2 derives the dual of the inverse quadratic programming problem, which is alinearly constrained semismoothly differentiable convex programming problem with fewervariables than the original one. Importantly, we adopt the augmented Lagrangian method,given in [1], for the dual problem with subproblems being solved by the Quasi-Newtonmethod and the Newton method, respectively. We focus on the comparison of numericalresults implemented by these two approaches. The numerical results show that the methodusing the Quasi-Newton method is much more effective than the one using the Newtonmethod.
In chapter 3, we use the barrier function method for solving the inverse quadraticprogramming problems and the subproblems are solved by the Quasi-Newton method withArmijo line search. We report the numerical experiments that show the efficiency of thebarrier function method, but the barrier function method is less effective than the augmentedLagrangian method for solving this problem.
在第一章介绍了这个问题的最小化模型，它是一个正半定锥约束模型。
在第二章推导这个二次规划反问题的对偶问题，它是一个线性约束半光滑可微的凸规划问题，变量的个数比原反问题的少的多，只需求这个对偶问题的最优解就可以得到原问题的最优解。我们采用了[1]中的增广拉格朗日方法求解对偶问题，集中比较子问题的不同数值方法的求解对计算效果的影响。我们采用拟牛顿法和牛顿法两个方法对子问题求解，比较它们的数值试验的结果，发现采用拟牛顿法求解子问题的方法比采用牛顿法求解子问题的方法的计算效果好得多。
在第三章中，我们用障碍函数法重新解这个二次规划反问题的对偶问题。首先给出了关于问题的凸性的证明，说明采用障碍函数法的合理性，在障碍函数的子问题求解中，我们同样采用拟牛顿法的BFGS算法配合Armijo线搜索。同样对于这个算法也给出了数值试验检验该算法的有效性，数值结果表明障碍函数法在求解此问题时没有增广拉格朗日方法有效。
In an optimization model there are parameters associated with decision variables in theobjective function or in the constraint set. When solving the optimization problem, we usuallyassume that these parameter values are known and we need to find an optimal solution to it.However, there are many instances in the practice, in which we only know some estimates forparameter values, but we may have certain optimal solutions from experience, observations orexperiments. An inverse optimization problem is to find values of parameters which make theknown solutions optimal and which differ from the given estimates as little as possible. Thereare many important contributions to inverse optimization and a large number of inversecombinatorial optimization problems have been studied, but for continuous optimization, wedo not see much study on their inverse problem. In this paper, our concern is the numericalcomparison of different methods for solving a type of inverse quadratic programmingproblems introduced in[1].
Chapter 1 introduces the inverse quadratic programming problem, which is aminimization problem with a positive semidefinite cone constraint.
Chapter 2 derives the dual of the inverse quadratic programming problem, which is alinearly constrained semismoothly differentiable convex programming problem with fewervariables than the original one. Importantly, we adopt the augmented Lagrangian method,given in [1], for the dual problem with subproblems being solved by the Quasi-Newtonmethod and the Newton method, respectively. We focus on the comparison of numericalresults implemented by these two approaches. The numerical results show that the methodusing the Quasi-Newton method is much more effective than the one using the Newtonmethod.
In chapter 3, we use the barrier function method for solving the inverse quadraticprogramming problems and the subproblems are solved by the Quasi-Newton method withArmijo line search. We report the numerical experiments that show the efficiency of thebarrier function method, but the barrier function method is less effective than the augmentedLagrangian method for solving this problem.
引文
[1] Zhang J Z, Zhang L W. An augmented Lagrangian method for a type of inverse quadratic programming problems. Report of City University of Hong Kong, 2006.
[2] Ahuja R K, Orlin J B. Inverse optimization. Operations Research, 2001, 49:771-183.
[3] Ahuja R K, Orlin J B. Combinatorial algorithms for inverse network flow problems. Networks, 40:181-187,2002.
[4] Burkard R E, Lin Y, Zhang J Z. Weight reduction problems with certain bottleneck objectives. European J. Operations Research, 2004, 153:191-199.
[5] Burton W R, Toint Ph L. On an instance of the inverse shortest paths problem. Mathematical Programming, 1992, 53:45-61.
[6] Cai M C, Yang X G, Zhang J. The complexity analysis of the inverse center location problem. J. Global Optimization, 1992, 15:213-218.
[7] Clarke F H. Optimization and nonsmooth analysis. John Wiley and Sons, New York, 1983.
[8] Facchinei F. Minimization of SCI functions and the Maratos effect. Operations Research Letters, 1995 17:1BI-137.
[9] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementarity problems, Vol. Ⅰ and Vol. Ⅱ. Sringer-Verlag, New York, 2003.
[10] Golshtein E G, Tretyakov N V. Modified lagrangians and monotone maps in optimization. John Wiley and Sons, New York, 1989.
[11] Tarantola A. Inverse problem theory: methods for data fitting and model parameter estimation. The Netherlands, Amesterdam: Elseier Science B V, 1987.
[12] Burton D, Toint P L. On an instance of the inverse shortest paths problem. Mathematical Programming, 1992,53:45-61.
[13] Burton W R, Ioint P L. On the shortest path problem. Doctoral dissertration, Facultes Universitaires Notre-Dame de la Paix de Namur, Department de Mathematique. Namur, Belgium, 1993.
[14] Heuberger C. Inverse combinatorial optimization: a survey on problem, methods, and result. Journal of combinatorial optimization, 2004,8:329-361.
[15] Ahuja R K, Orlin J B. Inverse optimization. Operations Reseach, 2001,49:771-783.
[16] Zhang J, Liu Z. Calculating some inverse linear programming problems. J. Comput. Appl. Math., 1996,72:261-273.
[17] Zhang J, Liu Z. A further study on inverse linear programming problems. J. Comput. Appl. Math., 1999,106:345-359.
[18] 刁在筠，戎晓霞．解一般线性规划逆问题的一个O(n~3 L)算法．运筹学报，1998，2(4)：64-72．
[19] 关秀翠，刁在筠．求解一般线性规划问题的预校正内点法．山东大学学报(自然科学版)，2000，35(1)：24-30．
[20] Bertsekas D P. Constrained optimization Lagrange multiplier methods. Academic Press, New York, 1982.
[21] Hiriart-Urruty J B, Lemarechal C. Convex analysis and minimization algorithms. Springer-Verlag, Berlin, New Yourk, 1993.
[22] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1997．
[23] Zhang L P, Lai Y L. A globally and supperlinearly convergent trust region method for LC~1optimization problem. Apll. Math. J. Chinese Univ. Ser. B, 2001,16(1):72-82.
[24] Sun W Y. Tow algorithms for LC~1unconstrained optimization. Journal of Computational Mathematics, 2000,18:621-632.
[25] Chen X J. Convergent of the BFGS method for LC~1 convex constrained optimization. SIAM Jounal on Control and Optimization, 1996, 34:2051-2063.
[26] Pang J S, Qi L. A globally convergent Newton method for convex LC~1 minimization problems. Journal of Optimization Theory and Application, 1995, 85:633-648.
[27] 李董辉，童小娇，万中．数值最优化．科学出版社，2005．
[28] 袁亚湘．非线性规划数值方法．上海科学技术出版社，1992．
[29] 张连生，白延琴．精确罚函数和极大极小问题．运筹学学报，2001，5(1)．
[2] Ahuja R K, Orlin J B. Inverse optimization. Operations Research, 2001, 49:771-183.
[3] Ahuja R K, Orlin J B. Combinatorial algorithms for inverse network flow problems. Networks, 40:181-187,2002.
[4] Burkard R E, Lin Y, Zhang J Z. Weight reduction problems with certain bottleneck objectives. European J. Operations Research, 2004, 153:191-199.
[5] Burton W R, Toint Ph L. On an instance of the inverse shortest paths problem. Mathematical Programming, 1992, 53:45-61.
[6] Cai M C, Yang X G, Zhang J. The complexity analysis of the inverse center location problem. J. Global Optimization, 1992, 15:213-218.
[7] Clarke F H. Optimization and nonsmooth analysis. John Wiley and Sons, New York, 1983.
[8] Facchinei F. Minimization of SCI functions and the Maratos effect. Operations Research Letters, 1995 17:1BI-137.
[9] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementarity problems, Vol. Ⅰ and Vol. Ⅱ. Sringer-Verlag, New York, 2003.
[10] Golshtein E G, Tretyakov N V. Modified lagrangians and monotone maps in optimization. John Wiley and Sons, New York, 1989.
[11] Tarantola A. Inverse problem theory: methods for data fitting and model parameter estimation. The Netherlands, Amesterdam: Elseier Science B V, 1987.
[12] Burton D, Toint P L. On an instance of the inverse shortest paths problem. Mathematical Programming, 1992,53:45-61.
[13] Burton W R, Ioint P L. On the shortest path problem. Doctoral dissertration, Facultes Universitaires Notre-Dame de la Paix de Namur, Department de Mathematique. Namur, Belgium, 1993.
[14] Heuberger C. Inverse combinatorial optimization: a survey on problem, methods, and result. Journal of combinatorial optimization, 2004,8:329-361.
[15] Ahuja R K, Orlin J B. Inverse optimization. Operations Reseach, 2001,49:771-783.
[16] Zhang J, Liu Z. Calculating some inverse linear programming problems. J. Comput. Appl. Math., 1996,72:261-273.
[17] Zhang J, Liu Z. A further study on inverse linear programming problems. J. Comput. Appl. Math., 1999,106:345-359.
[18] 刁在筠，戎晓霞．解一般线性规划逆问题的一个O(n~3 L)算法．运筹学报，1998，2(4)：64-72．
[19] 关秀翠，刁在筠．求解一般线性规划问题的预校正内点法．山东大学学报(自然科学版)，2000，35(1)：24-30．
[20] Bertsekas D P. Constrained optimization Lagrange multiplier methods. Academic Press, New York, 1982.
[21] Hiriart-Urruty J B, Lemarechal C. Convex analysis and minimization algorithms. Springer-Verlag, Berlin, New Yourk, 1993.
[22] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1997．
[23] Zhang L P, Lai Y L. A globally and supperlinearly convergent trust region method for LC~1optimization problem. Apll. Math. J. Chinese Univ. Ser. B, 2001,16(1):72-82.
[24] Sun W Y. Tow algorithms for LC~1unconstrained optimization. Journal of Computational Mathematics, 2000,18:621-632.
[25] Chen X J. Convergent of the BFGS method for LC~1 convex constrained optimization. SIAM Jounal on Control and Optimization, 1996, 34:2051-2063.
[26] Pang J S, Qi L. A globally convergent Newton method for convex LC~1 minimization problems. Journal of Optimization Theory and Application, 1995, 85:633-648.
[27] 李董辉，童小娇，万中．数值最优化．科学出版社，2005．
[28] 袁亚湘．非线性规划数值方法．上海科学技术出版社，1992．
[29] 张连生，白延琴．精确罚函数和极大极小问题．运筹学学报，2001，5(1)．