【作者】 刘丽霞；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2011， 博士

【摘要】 对称锥互补问题（SCCP）是一类重要的均衡优化问题,具有内容新、理论丰富和应用背景广泛等特点.他为标准非线性互补问题（NCP）、二阶锥互补问题（SOCCP）、半定互补问题（SDCP）提供了统一框架,与组合优化、鲁棒优化、不确定优化、博弈与均衡理论等分支有密切的联系.本论文主要利用欧几里德若当代数技术,建立了求解几类SCCP的光滑牛顿法,包括求解单调SCCP、其特殊情形单调SOCCP和非单调SCCP.另外,讨论了SCCP价值函数的一些性质.光滑牛顿法求解SCCP,首先利用互补函数,如常见的最小值函数或者FB互补函数,将SCCP转化为一个非光滑非线性方程组.然后在互补函数中引入一个光滑因子构造出一个光滑函数,利用此光滑化互补函数来逼近以前的互补函数.通过求解光滑方程组来达到求解原非光滑方程组的目的,其中光滑因子作为光滑方程组中的一个变量.最后利用牛顿法求解所转化的光滑方程组.本论文取得的主要结果可概括为如下:对于单调SCCP,基于对称扰动Chen-Harker-Kanzow-Smale（CHKS）光滑函数提出一个预估校正光滑牛顿法.证明算法所生成的点列在解集仅为非空的条件下有界,因而得到算法的全局收敛性.在适当的假设下,证明了算法的局部超线性收敛性.另外将一类二阶锥规划的新光滑函数推广到SCCP中,研究了该类新光滑函数的性质,并基于此光滑函数建立求解单调SCCP的一步光滑牛顿法,分析了算法的适定性以及全局和局部超线性收敛性.对于单调SOCCP,基于一类含参数互补函数的光滑函数,提出了求解SOCCP的一步光滑牛顿法.分析了算法适定性和收敛性,并且通过一个数值矩阵例子,说明光滑牛顿法在求解非单调的P₀-SOCCP时,牛顿方程可能会无解.最后,通过数值试验分析了参数对数值效果的影响.对于非单调具有笛卡尔P性质的对称锥线性互补问题（SCLCP）,基于CHKS光滑函数提出一个求解该类非单调SCLCP的光滑牛顿法,分析了在函数P满足Cartesain P₀性质时牛顿方程的可解性,证明了迭代点的邻域在函数P满足Cartesain性质时的有界性.从而得到算法的适定性和收敛性.对于非单调具有笛卡尔P₀性质的SCLCP,基于CHKS光滑函数提出一个求解该类非单调SCLCP的正则光滑牛顿法,分析了算法适定性和收敛性.另外,基于对称扰动Fischer-Burmeister（FB）光滑函数提出了一个光滑牛顿法,当函数P满足Cartesain P₀性质时,证明了牛顿方程的可解性和目标函数的强制性.从而,得到算法所生成点列的有界性.最后分析了算法的适定性和收敛性.基于欧几里德若当代数技术,提出了SCCP的一类新价值函数,在适当条件下讨论了该类价值函数水平集的有界性,并且基于该类价值函数建立了SCCP解的一个全局误差界.这两个性质可以提供算法停止的准则和分析算法收敛性.另外,对于一类已有价值函数,本文提出了比已有条件更弱的条件,在该条件下这些价值函数的水平集有界,且基于这些价值函数建立了SCCP解得全局误差界.更多还原

【Abstract】 Symmetric Cone Complementarity Problem（SCCP） is a class of important equilib-rium optimization problems with new content, abundant theory, and extensive applica-tion. The SCCP provides a simple uni?ed framework for various existing complementarityproblems such as nonlinear complementarity problem （NCP）, second-order cone comple-mentarity problem （SOCCP）, and the semide?nite complementarity problem （SDCP）. Italso has close relation with the combination optimization, robust optimization, uncertainoptimization, and game and equilibrium theory.This thesis is devoted to study the smoothing Newton method for solving severalclass of SCCP, including the monotone SCCP, the special case of monotone SCCP andtwo classes of nonmonotone SCCP, and to investigate some properties of the merit functionof SCCP by the tool of Euclidean Jordan algebras. When the smoothing Newton methodis used to solve SCCP, we ?rst reformulate it into a nonlinear system of non-smooth equa-tions by the complementarity function, such as the minimum complementarity functionand the Fischer-Burmeister（FB） complementarity function. And then a smooth factor isintroduced into the complementary function. So the non-smooth reformulation equationsare smoothed, seeming the smooth factor as a variable. Finally, the Newton method isused to solve the nonlinear system of smooth equation. The main contributions are listedas follows:For the monotone SCCP, we proposed a predictor-corrector smoothing Newtonmethod based on the symmetrically perturbed smoothing function. Under a mild as-sumption that the solution set of the problem concerned is just nonempty, we prove theglobal convergence of the proposed algorithm. And the local superlinear convergence isobtained under the suitable assumption. Also, we extended a class of new smoothingfunction of second order cone complementarity function to the SCCP, and researched theproperties of the new smoothing function. Based on this new smoothing function, we pro-posed a one step smoothing Newton method for monotone SCCP. The well-de?nednessof the method and the global convergence and the local superlinear convergence wereobtained.For the monotone SOCCP, we presented a one step smoothing Newton methodbased on a class of parametric smoothing function. The well-de?nedness and the con- vergence were researched. We also give a numerical example about 2×2 P₀-matrix,which implies that the smoothing Newton method based on Chen-Harker-Kanzow-Smale（CHKS） smoothing function （when P = 0） can not be used for solving the class of non-monotone P₀-SOCCP. At last, the preliminary numerical results are also reported to showthe in?uence of the parametric to the numerical e?ect.For the nonmonotone Symmetric Cone Linear Complementary Problem（SCLCP）with the Cartesian P-property, we proposed a smoothing Newton method based on theCHKS smoothing function. We proved the nonsingularity of Jacobian matrices under thecondition of the Cartesian P₀-property and the boundedness of neighborhood of iteratesgenerated by the smoothing Newton method. Hence, the well-de?nedness and the globaland local quadratic convergence were obtained.For the nonmonotone SCLCP with the Cartesian P₀-property, based the CHKSsmoothing function we presented a regularization smoothing Newton method, and thewell-de?nedness and the convergence are analyzed. Based on the famous symmetric per-turbed Fischer-Burmeister smoothing function, a smoothing Newton method is proposed.We proved the nonsingularity of Jacobian matrices （which implies the solvability of New-ton’s equation） and the coerciveness of the target function （which implies the boundednessof the neighborhood of iterates） under the condition of Cartesian P₀-property. Moreover,the global convergence is obtained under a nonsingularity assumption.Based on the Euclidean Jordan algebra, we proposed a new merit function forSCCP, studied the condition under which the level set of the merit function is boundedand the merit function provided a global error bound for the solution to the SCCP. Thetwo properties can be used to provide the stop criterion and to analyzed the convergenceof the algorithm. Also, for the existing merit function, a weaker condition under whichthe existing merit function have the above two properties was proposed.更多还原