求解半定约束二次规划逆问题的数值方法
|
摘要
本论文研究了一类由半定约束二次规划问题产生的逆优化问题。此逆问题通过尽量小地调整半定二次规划问题的目标函数的参数,使得已知的可行解为调整后的问题的最优解。我们将此逆问题转化为带有半正定矩阵锥约束的极小化问题,并且经推导可知其对偶问题为一个带有线性半正定矩阵锥约束的半光滑可微凸问题。并且当问题的规模很大时,对偶问题变量的维数远小于原问题变量的维数,所以本论文的中心就是研究如何求解此对偶问题。
本论文的内容概括如下:
1.在第一章中,首先介绍了逆优化问题的背景及其研究现状,然后提出了本文所要研究的一类产生于半定二次规划问题的逆问题,并通过一系列等价转化得到其对偶问题ISDQD(A,B)。
2.第二章研究了用增广拉格朗日方法求解半定二次规划逆问题的对偶问题.首先概述了增广拉格朗日方法的背景和发展历史,接着回顾了半光滑分析的一些知识和半正定矩阵锥的一些性质。然后在一定的假设条件下,给出了增广拉格朗日方法求解问题ISDQD(A,B)的全局收敛性和线性收敛速度。最后给出数值实验结果。
3.第三章的主要内容是用光滑化牛顿法求解半定二次规划逆问题的对偶问题的Karush-Kuhn-Tucker系统。首先介绍了一种光滑化函数以及它的一些性质。然后运用此光滑化函数将问题ISDQD(A,B)的Karush-Kuhn-Tucker系统转化为一个光滑方程组,接着用光滑化牛顿法求解此方程组,然后给出了光滑化牛顿法的收敛性和收敛速度。最后由数值实验说明了此方法的有效性。
4.第四章探讨了由光滑化牛顿法改进得到的非精确光滑化牛顿法求解对偶问题ISDQD(A,B)的Karush-Kuhn-Tucker系统。首先引入了矩阵值函数的一些知识,然后在严格互补和非退化性条件成立的假设下,给出了非精确光滑化牛顿法的收敛结果。最后我们对几种求解ISDQD(A,B)的方法进行了数值实验,并对其结果进行了比较和分析。
We consider an inverse optimization problem raised from the semi-definite quadratic programming (SDQP) problem.In the inverse problem,the parameters in the objective function of a given SDQP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one.We formulate this problem into a minimization problem with a positive semi-definite cone constraint,and its dual problem is a linearly positive semi-definite cone constrained semismoothly differentiable convex programming problem with fewer variables than the original one.Therefore this thesis is focused on solving the dual problem.
The main results of this dissertation are summarized as follows:
1.Chapter 1 first gives the introduction,background and current research of inverse optimization. Then we describe the inverse semi-definite quadratic programming problems studied in this thesis,and derive its dual problem ISDQD(A,B).
2.Chapter 2 deals with the augmented Lagrangian method for the dual problem of the inverse semi-definite quadratic programming problems.In this chapter we first describe the background of the augmented Lagrangian method.Following a preliminary review of semismooth analysis and the positive semi-definite cone,we present the convergence analysis of augmented Lagrangian method for solving the dual problem.In the end,we report our numerical results.
3.The contents of Chapter 3 are mainly about the smoothing Newton method for the Karush-Kuhn -Tucker system of problem ISDQD(A,B).First we introduce a smoothing function and study its properties.Then we present the convergence analysis of smoothing Newton method for the smooth linear system which is a smoothing approximation of the referred Karush-Kuhn-Tucker system.In the end of Chapter 3,our numerical experiment results show that this method is very effective.
4.In Chapter 4,we discuss the inexact smoothing Newton method which is based on the smoothing Newton method.Following some preliminaries on matrix valued functions, we apply the inexact smoothing Newton method to solve problem ISDQD(A,B).Under the strict complementary and nondegeneracy assumptions,we give the convergence results of the inexact smoothing Newton method.Finally,in our numerical experiment we measure the numerical performance of four numerical methods for solving problem ISDQD(A,B).
本论文的内容概括如下:
1.在第一章中,首先介绍了逆优化问题的背景及其研究现状,然后提出了本文所要研究的一类产生于半定二次规划问题的逆问题,并通过一系列等价转化得到其对偶问题ISDQD(A,B)。
2.第二章研究了用增广拉格朗日方法求解半定二次规划逆问题的对偶问题.首先概述了增广拉格朗日方法的背景和发展历史,接着回顾了半光滑分析的一些知识和半正定矩阵锥的一些性质。然后在一定的假设条件下,给出了增广拉格朗日方法求解问题ISDQD(A,B)的全局收敛性和线性收敛速度。最后给出数值实验结果。
3.第三章的主要内容是用光滑化牛顿法求解半定二次规划逆问题的对偶问题的Karush-Kuhn-Tucker系统。首先介绍了一种光滑化函数以及它的一些性质。然后运用此光滑化函数将问题ISDQD(A,B)的Karush-Kuhn-Tucker系统转化为一个光滑方程组,接着用光滑化牛顿法求解此方程组,然后给出了光滑化牛顿法的收敛性和收敛速度。最后由数值实验说明了此方法的有效性。
4.第四章探讨了由光滑化牛顿法改进得到的非精确光滑化牛顿法求解对偶问题ISDQD(A,B)的Karush-Kuhn-Tucker系统。首先引入了矩阵值函数的一些知识,然后在严格互补和非退化性条件成立的假设下,给出了非精确光滑化牛顿法的收敛结果。最后我们对几种求解ISDQD(A,B)的方法进行了数值实验,并对其结果进行了比较和分析。
We consider an inverse optimization problem raised from the semi-definite quadratic programming (SDQP) problem.In the inverse problem,the parameters in the objective function of a given SDQP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one.We formulate this problem into a minimization problem with a positive semi-definite cone constraint,and its dual problem is a linearly positive semi-definite cone constrained semismoothly differentiable convex programming problem with fewer variables than the original one.Therefore this thesis is focused on solving the dual problem.
The main results of this dissertation are summarized as follows:
1.Chapter 1 first gives the introduction,background and current research of inverse optimization. Then we describe the inverse semi-definite quadratic programming problems studied in this thesis,and derive its dual problem ISDQD(A,B).
2.Chapter 2 deals with the augmented Lagrangian method for the dual problem of the inverse semi-definite quadratic programming problems.In this chapter we first describe the background of the augmented Lagrangian method.Following a preliminary review of semismooth analysis and the positive semi-definite cone,we present the convergence analysis of augmented Lagrangian method for solving the dual problem.In the end,we report our numerical results.
3.The contents of Chapter 3 are mainly about the smoothing Newton method for the Karush-Kuhn -Tucker system of problem ISDQD(A,B).First we introduce a smoothing function and study its properties.Then we present the convergence analysis of smoothing Newton method for the smooth linear system which is a smoothing approximation of the referred Karush-Kuhn-Tucker system.In the end of Chapter 3,our numerical experiment results show that this method is very effective.
4.In Chapter 4,we discuss the inexact smoothing Newton method which is based on the smoothing Newton method.Following some preliminaries on matrix valued functions, we apply the inexact smoothing Newton method to solve problem ISDQD(A,B).Under the strict complementary and nondegeneracy assumptions,we give the convergence results of the inexact smoothing Newton method.Finally,in our numerical experiment we measure the numerical performance of four numerical methods for solving problem ISDQD(A,B).
引文
[1]Tarantola A.Inverse Problem Theory:Methods for Data Fitting and Model Parameter Estimation[M].Amsterdam:Elsevier,1987.
[2]Marlow B.Inverse problems[EB/OL].http://www.inverse-problems.com/.
[3]Engl H W,Hanke M,Neubauer A.Regularization of Inverse Problems[M].Dordrecht:Kluwer Academic Publishers Group,1996.
[4]Dial R B.Minimal-revenue congestion pricing part Ⅰ:A fast algorithm for the single-origin case[J].Transportation Research,1999,33:189-202.
[5]Dial R B.Minimal-revenue congestion pricing part Ⅱ:An efficient algorithm for the general case[J].Transportation Research,2000,34:645-665.
[6]Burton D,Toint Ph L.On an instance of the inverse shortest paths problem[J].Math.Prog.,1992,53:45-61.
[7]Burton D,Toin Ph L.On the use of an inverse shortest paths algorithm for recovering linearly correlated costs[J].Math.Prog.,1994,63:1-22.
[8]Carr S C,Lovejoy W S.The inverse newsvendor problem:Choosing an optimal demand portfolio for capacitated resources[R].Department of Industrial and Operations Engineering,University of Michigan,1997.
[9]Dembo R,Merkoulovitch L,Rosen D.Images from a portfolio[R].Algorithmics Research Working Paper,Algorithmics,Inc.,Canada,1998.
[10]Ahuja R K,Orlin J B.A faster algorithm for the inverse spanning tree problem[J].J.Algorithms,2000,34:177-193.
[11]Ahuja R K,Orlin J B.Combinatorial algorithms for inverse network flow problems[J].Networks,2002,40:181-187
[12]Ahuja R K,Orlin J B.Inverse optimization[J].Operations Research,2001,49:771-783.
[13]Burkard R E,Lin Y,Zhang J.Weight reduction problems with certain bottleneck objectives[J].European J.Open Res.,2004,153:191-199.
[14]Cai M,Yang X,Zhang J.The complexity analysis of the inverse center location problem[J].J.Glob.Optim.,1999,15:213-218.
[15]Zhang J,Ma Z.Solution structure of some inverse combinatorial optimization problems[J].J.Comput.Appl.Math.,1999,3:127-139.
[16]Heuberger C.Inverse combinatorial optimization:a survey on problems,methods and results[J].J.Combin.Optim.,2004,8:329:361.
[17]Zhang J,Liu Z.Calculating some inverse linear programming problems[J].J.Comput.Appl.Math.,1996,72:261-273.
[18]Zhang J,Liu Z.A further study on inverse linear programming problems[J].J.Comput.Appl.Math.,1999,106:345-359.
[19]Zhang J,Zhang L.An augmented Lagrangian method for a type of inverse quadratic programming problems[R].City University of Hong Kong,2006.
[20]Ednonds J,Giles R.A min-max relation for submodular functions on graphs[J].Ann.of Discrete Math.,1977,1:185-204.
[21]Schrijver A.Total dual integrality from directed graphs,crossing families,and sub- and super-modular functions[C].Progress in combinatorial optimization.Toronto:Academic Press,1984:315-361.
[22]Cai M C,Yang X G,Li Y.Inverse problems of submodular functions on digraphs[J].J.Optim.Theo.Appl.,2000,104:559-575.
[23]Ahuja R K,Magnanti Th L,Orlin J B.Network flows:theory,algorithms,and applications[M].New York:Prentice Hall Inc,1993.
[24]Zhang J,Liu Z.A general model of some inverse optimization problems and its solution method under l_∞ norm[J].J.Comb.Optim.,2002,6:207-227.
[25]Zhang J,Ma Z,Yang C.A column generation method for inverse shortest path problems[J].Math.Methods Oper.Res.,1995,41:347-358.
[26]Hu Z,Liu Z.A strongly polynomial algorithm for the inverse shortest arborescence problem[J].Discrete Appl.Math.,1998,82:135-154.
[27]Xu S,Zhang J.An inverse problem of the weighted shortest path problem[J].Japan J.Indust.Appl.Math.,1995,12:47-59.
[28]Yang C.Some inverse optimization problems and extensions[D].Hong Kong:City University of Hong Kong,1997.
[29]Zhang J,Ma Z.A network flow method for solving some inverse combinatorial optimization problems [J].Optimization,1996,37:59-72.
[30]Yang X.Complexity of partial inverse assignment problem and partial inverse cut problem[J].RAIRO Oper.Res.,2001,35:117-126.
[31]Cai M C,Li Y.Inverse matroid intersection problem[J].Math.Methods Oper.Res.,1997,45:235-243.
[32]Cai M C.Inverse problems of matroid intersection[J].J.Comb.Optim.,1999,3:465-474.
[33]Dell'Amico M,Maffioli F,Malucelli F.The base-matroid and inverse combinatorial optimization problems [J].Discrete Appl.Math.,2003,128:337-353.
[34]Zhang J,Xu S,Ma Z.An algorithm for inverse minimum spanning tree problem[J].Optim.Methods Software,1997,8:69-84.
[35]Sokkalingam P T,Ahuja R K,Orlin J B.Solving inverse spanning tree problems through network flow techniques[J].Oper.Res.,1999,47:291-298.
[36]Yang C,Zhang J,Ma Z.Inverse maximum flow and minimum cut problems[J].Optimization,1997,40:147-170.
[37]Zhang J,Cai M.Inverse problem of minimum cuts[J].Math.Methods Oper.Res.,1998,47:51-58.
[38]Liu Z,Zhang J.On inverse problems of optimum perfect matching[J].J.Comb.Optim.,2003,7:215-228.
[39]Zhang J,Liu Z,Ma Z.Some reverse location problems[J].Eur.J.Oper.Res.,2000,124:77-88.
[40]Berman O,Ingco D I,Odoni A.Improving the location of minimax facilities through network modification [J].Networks,1994,24:31-41.
[41]Yang C,Zhang J.Inverse maximum capacity problems[J].OR Spectrum,1998,20:97-100.
[42]Huang S,Liu Z.On the inverse problem of linear programming and its application to minimum weight perfect k-matching[J].Eur.J.Oper.Res.,1999,112:421-426.
[43]Zhang J,Zhang L.A perturbation approach for an inverse quadratic programming problem[R].City University of Hong Kong,2006.
[44]Bonnans J F,Shapiro A.Perturbation Analysis of Optimization Problems[M].New York:Springer,2000.
[45]张立卫译,最优化问题的扰动分析[M].北京:科学出版社,2008.
[46]Rockafellar R T.Conjugate Duality and Optimization[M].Philadelphia:SIAM,1974.
[47]Zarantonello E H.Projections on convex sets in Hilbert space and spectral theory Ⅰ and Ⅱ[C]//Contributions to Nonlinear Functional Analysis.New York:Academic Press,1971:237-424.
[48]Arrow K J,Solow R M.Gradient methods for constrained maxima with weakened assumptions[C]//Studies in Linear and Nonlinear Programming.Stanford:Standford University Press,1958:165-176.
[49]Hestenes M R.Multiplier and gradient methods[J].J.of Optim.Theory and App.,1969,4:303-320.
[50]Powell M J D.A method for nonlinear constraints in minimization problems[C]// Optimization.New York:Academic Press,1972:283-298.
[51]Rockafellar R T.A dual approach to solving nonlinear programming problems by unconstrained optimization [J].Math.Prog.,1973,5:354-373.
[52]Rockafellar R T.The multiplier method of Hestenes and Powell applied to convex programming[J].J.Optim.Theo.App.,1973,12:555-562.
[53]Tretyakov N V.A method of penalty estimates for convex programming problems[J].(?)konomika i Matematicheskie Metody,1973,9:525-540.
[54]Bertsekas D P.On penalty and multiplier methods for constrained minimization[J].SIAM J.Con.Optim.,1976,14:216-235.
[55]Bertsekas D P.Constrained Optimization and Lagrange Multiplier Methods[M].New York:Academic Press,1982.
[56]Conn A R,Gould N I M,Toint Ph L.A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds[J].SIAM J.Num.Anal.,1991,28:545-572.
[57]Contesse-Becker L.Extended convergence results for the method of multipliers for non-strictly binding inequality constraints[J].J.Optim.Theo.App.,1993,79:273-310.
[58]Ito K,Kunisch K.The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces[J].Math.Prog.,1990,46:341-360.
[59]Golshtein E G,Tretyakov N V.Modified Lagrangian and Monotone Maps in Optimization[M].New York:John Wiley and Sons,1989.
[60]Rockafellar R T.Lagrange multipliers and optimality[J].SIAM Review,1993,35:183-238.
[61]Sun D F,Sun J,Zhang L W.The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming[J].Math.Prog.,2008,114:349-391.
[62]Clarke F H.Optimization and Nonsmooth Analysis[M].New York:John Wiley and Sons,1983.
[63]Mifflin R.Semismooth and semiconvex functions in constrained optimization[J].SIAM J.Control and Optim.,1977,15:957-972.
[64]Qi L,Sun J.A nonsmooth version of Newton's method[J].Math.Prog.,1993,58:353-367.
[65]Sun D.A further result on an implicit function theorem for locally Lipschitz functions[J].Operations and Research Letters,2001,28:193-198.
[66]Kummer B.Lipschitzian inverse functions,directional derivatives,and applications in C~(1,1) optimization [J].J.Optim.Theo.Appl.,1991,70:559-580.
[67]Facchinei F.Minimizing of SC~1 functions and the Maratos effect[J].Operations and Research Letters,1995,17:131-137.
[68]Facchinei F,Pang J S.Finite-Dimensional Variational Inequalities and Complementarity Problems,Vol.Ⅰ and Ⅱ[M].New York:Springer-Verlag,2003.
[69]Hiriart-Urruty J B,Strodiot J J,Nguyen V H.Generalized Hessian Matrix and second-order optimality conditions for problems with C~(1,1) data[J].Appl.Math.Optim.,1984,11:43-56.
[70]Meng F,Sun D,Zhao G.Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization[J].Math.Prog.,2005,104:561-581.
[71]Sun D,Sun J.Semismooth matrix valued functions[J].Math.Oper.Res.,2002,27:150-169.
[72]Chen X,Qi H,Tseng P.Analysis of nonsmooth symmetric-matrix-valued functions with applications to semidefinite complementarity problems[J].SIAM J.Optim.,2003,13:960-985.
[73]Robinson S M.Local structure of feasible sets in nonlinear programming,Part Ⅱ:Nondegeneracy[J].Math.Prog.Study,1984,22:217-230.
[74]Hiriart-Urruty J B,Lemar(?)chal C.Convex Analysis and Minimization Algorithms[M].Berlin:Springer-Verlag,1993.
[75]Rockafellar R T,Wets R J-B.Variational Analysis[M].Berlin:Springer-Verlag,1998.
[76]Goishtein E G,Tretyakov N V.Modified Lagrangians and Monotone Maps in Optimization[M].New York:John Wiley and Sons,1996.
[77]Shapiro A.On concepts of directional differentiability[J].J.Optim.Theo.Appl.,1990,66:477-487.
[78]Fukushima M,Qi L.Reformulation:Nonsmooth,Piecewise Smooth,Semismooth and Smoothing Methods[M].Dortrecht:Kluwer Academic Publishers,1999.
[79]Qi L,Sun D,Zhou G.A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities[J].Math.Prog.,2000,87:1-35.
[80]Sun J,Sun D,Qi L.A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems[J].SIAM J Optim.,2003,14:783-806.
[81]Chen X,Tseng P.Non-interior continuation methods for solving semidefinite complentarity problems [J].Math.Prog.,2003,95:431-474.
[82]Huang Z,Sun D,Zhao G.A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming[J].Comput.Optim.Appl.,2006,35:199-237.
[83]Sonneveld P.CGS:A fast Lanczos-type solver for nonsymmetric linear systems[J].SIAMJ.Sci.Statist.Comput.,1989,10:36-52.
[84]Gao Y,Sun D.Calibrating least squares covariance matrix problems with equality and inequality constraints [J/OL].Optimization online,2008.http://www.optimization-online.org/DB-HTMI/2008/06/2023.html
[85]Schwertman N C,Allen D M.Smoothing an indefinite variance-covariance matrix[J].J.Statis.Comput.Simul.,1979,9:183-194.
[86]Horn R A,Johnson C R.Matrix Analysis[M].Cambridge:Cambridge University Press,1985.
[87]Bhatia R.Matrix Analysis[M].New York:Springer-Verlag,1997.
[88]L(o|)wner K.Uber monotone matrixfunktionen[J].Mathematische Zeitschrift,1934,38:177-216.
[89]Ravindran G,Gowda M S.Regularization of P_0-function in box variational inequality problems[J].SIAM J.Optim.,2000,11:748-760.
[90]Kojima M,Shida M,Shindoh S.Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs[J].Math.Prog.,1998,80:129-160.
[91]Flegel M L,Kanzow C.Equivalence of two nondegeneracy conditions for semidefinite programs[J].J.Optim.Theo.Appl.,2007,135:381-397.
[92]Alizadeh F,Haeberly J.Overton M L.Complementarity and nondegeneracy in semidefinite programming [J].Math.Prog.,1997,77:111-128.
[93]van der Vorst H A,BI-CGSTAB:a fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems[J].SIAM J.Sci.Stat.Compu.,1992,13:631-644.
[94]T(u|¨)t(u|¨)nc(u|¨) H A,Toh K C,Todd M J.Solving semidefinite-quadratic-linear programs using SDPT3[J].Math.Prog.,2003,95:189-217.
[95]Sturm Jos F.Using SeDuMi 1.02,a MATLAB toolbox for optimization over symmetric cones[J].Optim.Methods Softw.,1999,11:625-653.
[2]Marlow B.Inverse problems[EB/OL].http://www.inverse-problems.com/.
[3]Engl H W,Hanke M,Neubauer A.Regularization of Inverse Problems[M].Dordrecht:Kluwer Academic Publishers Group,1996.
[4]Dial R B.Minimal-revenue congestion pricing part Ⅰ:A fast algorithm for the single-origin case[J].Transportation Research,1999,33:189-202.
[5]Dial R B.Minimal-revenue congestion pricing part Ⅱ:An efficient algorithm for the general case[J].Transportation Research,2000,34:645-665.
[6]Burton D,Toint Ph L.On an instance of the inverse shortest paths problem[J].Math.Prog.,1992,53:45-61.
[7]Burton D,Toin Ph L.On the use of an inverse shortest paths algorithm for recovering linearly correlated costs[J].Math.Prog.,1994,63:1-22.
[8]Carr S C,Lovejoy W S.The inverse newsvendor problem:Choosing an optimal demand portfolio for capacitated resources[R].Department of Industrial and Operations Engineering,University of Michigan,1997.
[9]Dembo R,Merkoulovitch L,Rosen D.Images from a portfolio[R].Algorithmics Research Working Paper,Algorithmics,Inc.,Canada,1998.
[10]Ahuja R K,Orlin J B.A faster algorithm for the inverse spanning tree problem[J].J.Algorithms,2000,34:177-193.
[11]Ahuja R K,Orlin J B.Combinatorial algorithms for inverse network flow problems[J].Networks,2002,40:181-187
[12]Ahuja R K,Orlin J B.Inverse optimization[J].Operations Research,2001,49:771-783.
[13]Burkard R E,Lin Y,Zhang J.Weight reduction problems with certain bottleneck objectives[J].European J.Open Res.,2004,153:191-199.
[14]Cai M,Yang X,Zhang J.The complexity analysis of the inverse center location problem[J].J.Glob.Optim.,1999,15:213-218.
[15]Zhang J,Ma Z.Solution structure of some inverse combinatorial optimization problems[J].J.Comput.Appl.Math.,1999,3:127-139.
[16]Heuberger C.Inverse combinatorial optimization:a survey on problems,methods and results[J].J.Combin.Optim.,2004,8:329:361.
[17]Zhang J,Liu Z.Calculating some inverse linear programming problems[J].J.Comput.Appl.Math.,1996,72:261-273.
[18]Zhang J,Liu Z.A further study on inverse linear programming problems[J].J.Comput.Appl.Math.,1999,106:345-359.
[19]Zhang J,Zhang L.An augmented Lagrangian method for a type of inverse quadratic programming problems[R].City University of Hong Kong,2006.
[20]Ednonds J,Giles R.A min-max relation for submodular functions on graphs[J].Ann.of Discrete Math.,1977,1:185-204.
[21]Schrijver A.Total dual integrality from directed graphs,crossing families,and sub- and super-modular functions[C].Progress in combinatorial optimization.Toronto:Academic Press,1984:315-361.
[22]Cai M C,Yang X G,Li Y.Inverse problems of submodular functions on digraphs[J].J.Optim.Theo.Appl.,2000,104:559-575.
[23]Ahuja R K,Magnanti Th L,Orlin J B.Network flows:theory,algorithms,and applications[M].New York:Prentice Hall Inc,1993.
[24]Zhang J,Liu Z.A general model of some inverse optimization problems and its solution method under l_∞ norm[J].J.Comb.Optim.,2002,6:207-227.
[25]Zhang J,Ma Z,Yang C.A column generation method for inverse shortest path problems[J].Math.Methods Oper.Res.,1995,41:347-358.
[26]Hu Z,Liu Z.A strongly polynomial algorithm for the inverse shortest arborescence problem[J].Discrete Appl.Math.,1998,82:135-154.
[27]Xu S,Zhang J.An inverse problem of the weighted shortest path problem[J].Japan J.Indust.Appl.Math.,1995,12:47-59.
[28]Yang C.Some inverse optimization problems and extensions[D].Hong Kong:City University of Hong Kong,1997.
[29]Zhang J,Ma Z.A network flow method for solving some inverse combinatorial optimization problems [J].Optimization,1996,37:59-72.
[30]Yang X.Complexity of partial inverse assignment problem and partial inverse cut problem[J].RAIRO Oper.Res.,2001,35:117-126.
[31]Cai M C,Li Y.Inverse matroid intersection problem[J].Math.Methods Oper.Res.,1997,45:235-243.
[32]Cai M C.Inverse problems of matroid intersection[J].J.Comb.Optim.,1999,3:465-474.
[33]Dell'Amico M,Maffioli F,Malucelli F.The base-matroid and inverse combinatorial optimization problems [J].Discrete Appl.Math.,2003,128:337-353.
[34]Zhang J,Xu S,Ma Z.An algorithm for inverse minimum spanning tree problem[J].Optim.Methods Software,1997,8:69-84.
[35]Sokkalingam P T,Ahuja R K,Orlin J B.Solving inverse spanning tree problems through network flow techniques[J].Oper.Res.,1999,47:291-298.
[36]Yang C,Zhang J,Ma Z.Inverse maximum flow and minimum cut problems[J].Optimization,1997,40:147-170.
[37]Zhang J,Cai M.Inverse problem of minimum cuts[J].Math.Methods Oper.Res.,1998,47:51-58.
[38]Liu Z,Zhang J.On inverse problems of optimum perfect matching[J].J.Comb.Optim.,2003,7:215-228.
[39]Zhang J,Liu Z,Ma Z.Some reverse location problems[J].Eur.J.Oper.Res.,2000,124:77-88.
[40]Berman O,Ingco D I,Odoni A.Improving the location of minimax facilities through network modification [J].Networks,1994,24:31-41.
[41]Yang C,Zhang J.Inverse maximum capacity problems[J].OR Spectrum,1998,20:97-100.
[42]Huang S,Liu Z.On the inverse problem of linear programming and its application to minimum weight perfect k-matching[J].Eur.J.Oper.Res.,1999,112:421-426.
[43]Zhang J,Zhang L.A perturbation approach for an inverse quadratic programming problem[R].City University of Hong Kong,2006.
[44]Bonnans J F,Shapiro A.Perturbation Analysis of Optimization Problems[M].New York:Springer,2000.
[45]张立卫译,最优化问题的扰动分析[M].北京:科学出版社,2008.
[46]Rockafellar R T.Conjugate Duality and Optimization[M].Philadelphia:SIAM,1974.
[47]Zarantonello E H.Projections on convex sets in Hilbert space and spectral theory Ⅰ and Ⅱ[C]//Contributions to Nonlinear Functional Analysis.New York:Academic Press,1971:237-424.
[48]Arrow K J,Solow R M.Gradient methods for constrained maxima with weakened assumptions[C]//Studies in Linear and Nonlinear Programming.Stanford:Standford University Press,1958:165-176.
[49]Hestenes M R.Multiplier and gradient methods[J].J.of Optim.Theory and App.,1969,4:303-320.
[50]Powell M J D.A method for nonlinear constraints in minimization problems[C]// Optimization.New York:Academic Press,1972:283-298.
[51]Rockafellar R T.A dual approach to solving nonlinear programming problems by unconstrained optimization [J].Math.Prog.,1973,5:354-373.
[52]Rockafellar R T.The multiplier method of Hestenes and Powell applied to convex programming[J].J.Optim.Theo.App.,1973,12:555-562.
[53]Tretyakov N V.A method of penalty estimates for convex programming problems[J].(?)konomika i Matematicheskie Metody,1973,9:525-540.
[54]Bertsekas D P.On penalty and multiplier methods for constrained minimization[J].SIAM J.Con.Optim.,1976,14:216-235.
[55]Bertsekas D P.Constrained Optimization and Lagrange Multiplier Methods[M].New York:Academic Press,1982.
[56]Conn A R,Gould N I M,Toint Ph L.A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds[J].SIAM J.Num.Anal.,1991,28:545-572.
[57]Contesse-Becker L.Extended convergence results for the method of multipliers for non-strictly binding inequality constraints[J].J.Optim.Theo.App.,1993,79:273-310.
[58]Ito K,Kunisch K.The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces[J].Math.Prog.,1990,46:341-360.
[59]Golshtein E G,Tretyakov N V.Modified Lagrangian and Monotone Maps in Optimization[M].New York:John Wiley and Sons,1989.
[60]Rockafellar R T.Lagrange multipliers and optimality[J].SIAM Review,1993,35:183-238.
[61]Sun D F,Sun J,Zhang L W.The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming[J].Math.Prog.,2008,114:349-391.
[62]Clarke F H.Optimization and Nonsmooth Analysis[M].New York:John Wiley and Sons,1983.
[63]Mifflin R.Semismooth and semiconvex functions in constrained optimization[J].SIAM J.Control and Optim.,1977,15:957-972.
[64]Qi L,Sun J.A nonsmooth version of Newton's method[J].Math.Prog.,1993,58:353-367.
[65]Sun D.A further result on an implicit function theorem for locally Lipschitz functions[J].Operations and Research Letters,2001,28:193-198.
[66]Kummer B.Lipschitzian inverse functions,directional derivatives,and applications in C~(1,1) optimization [J].J.Optim.Theo.Appl.,1991,70:559-580.
[67]Facchinei F.Minimizing of SC~1 functions and the Maratos effect[J].Operations and Research Letters,1995,17:131-137.
[68]Facchinei F,Pang J S.Finite-Dimensional Variational Inequalities and Complementarity Problems,Vol.Ⅰ and Ⅱ[M].New York:Springer-Verlag,2003.
[69]Hiriart-Urruty J B,Strodiot J J,Nguyen V H.Generalized Hessian Matrix and second-order optimality conditions for problems with C~(1,1) data[J].Appl.Math.Optim.,1984,11:43-56.
[70]Meng F,Sun D,Zhao G.Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization[J].Math.Prog.,2005,104:561-581.
[71]Sun D,Sun J.Semismooth matrix valued functions[J].Math.Oper.Res.,2002,27:150-169.
[72]Chen X,Qi H,Tseng P.Analysis of nonsmooth symmetric-matrix-valued functions with applications to semidefinite complementarity problems[J].SIAM J.Optim.,2003,13:960-985.
[73]Robinson S M.Local structure of feasible sets in nonlinear programming,Part Ⅱ:Nondegeneracy[J].Math.Prog.Study,1984,22:217-230.
[74]Hiriart-Urruty J B,Lemar(?)chal C.Convex Analysis and Minimization Algorithms[M].Berlin:Springer-Verlag,1993.
[75]Rockafellar R T,Wets R J-B.Variational Analysis[M].Berlin:Springer-Verlag,1998.
[76]Goishtein E G,Tretyakov N V.Modified Lagrangians and Monotone Maps in Optimization[M].New York:John Wiley and Sons,1996.
[77]Shapiro A.On concepts of directional differentiability[J].J.Optim.Theo.Appl.,1990,66:477-487.
[78]Fukushima M,Qi L.Reformulation:Nonsmooth,Piecewise Smooth,Semismooth and Smoothing Methods[M].Dortrecht:Kluwer Academic Publishers,1999.
[79]Qi L,Sun D,Zhou G.A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities[J].Math.Prog.,2000,87:1-35.
[80]Sun J,Sun D,Qi L.A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems[J].SIAM J Optim.,2003,14:783-806.
[81]Chen X,Tseng P.Non-interior continuation methods for solving semidefinite complentarity problems [J].Math.Prog.,2003,95:431-474.
[82]Huang Z,Sun D,Zhao G.A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming[J].Comput.Optim.Appl.,2006,35:199-237.
[83]Sonneveld P.CGS:A fast Lanczos-type solver for nonsymmetric linear systems[J].SIAMJ.Sci.Statist.Comput.,1989,10:36-52.
[84]Gao Y,Sun D.Calibrating least squares covariance matrix problems with equality and inequality constraints [J/OL].Optimization online,2008.http://www.optimization-online.org/DB-HTMI/2008/06/2023.html
[85]Schwertman N C,Allen D M.Smoothing an indefinite variance-covariance matrix[J].J.Statis.Comput.Simul.,1979,9:183-194.
[86]Horn R A,Johnson C R.Matrix Analysis[M].Cambridge:Cambridge University Press,1985.
[87]Bhatia R.Matrix Analysis[M].New York:Springer-Verlag,1997.
[88]L(o|)wner K.Uber monotone matrixfunktionen[J].Mathematische Zeitschrift,1934,38:177-216.
[89]Ravindran G,Gowda M S.Regularization of P_0-function in box variational inequality problems[J].SIAM J.Optim.,2000,11:748-760.
[90]Kojima M,Shida M,Shindoh S.Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs[J].Math.Prog.,1998,80:129-160.
[91]Flegel M L,Kanzow C.Equivalence of two nondegeneracy conditions for semidefinite programs[J].J.Optim.Theo.Appl.,2007,135:381-397.
[92]Alizadeh F,Haeberly J.Overton M L.Complementarity and nondegeneracy in semidefinite programming [J].Math.Prog.,1997,77:111-128.
[93]van der Vorst H A,BI-CGSTAB:a fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems[J].SIAM J.Sci.Stat.Compu.,1992,13:631-644.
[94]T(u|¨)t(u|¨)nc(u|¨) H A,Toh K C,Todd M J.Solving semidefinite-quadratic-linear programs using SDPT3[J].Math.Prog.,2003,95:189-217.
[95]Sturm Jos F.Using SeDuMi 1.02,a MATLAB toolbox for optimization over symmetric cones[J].Optim.Methods Softw.,1999,11:625-653.