Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities 论文

摘要

The smoothing Newton method for solving a system of nonsmooth equations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F left-parenthesis x right-parenthesis equals 0"> <mml:semantics> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">F(x)=0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , which may arise from the nonlinear complementarity problem, the variational inequality problem or other problems, can be regarded as a variant of the smoothing method. At the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> th step, the nonsmooth function <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F"> <mml:semantics> <mml:mi>F</mml:mi> <mml:annotation encoding="application/x-tex">F</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is approximated by a smooth function <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis dot comma epsilon Subscript k Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo> ⋅ </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi> ε </mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f(\cdot , \varepsilon _k)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and the derivative of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis dot comma epsilon Subscript k Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo> ⋅ </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi> ε </mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f(\cdot , \varepsilon _k)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> at <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x Superscript k"> <mml:semantics> <mml:msup> <mml:mi>x</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">x^k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is used as the Newton iterative matrix. The merits of smoothing methods and smoothing Newton methods are global convergence and convenience in handling. In this paper, we show that the smoothing Newton method is also superlinearly convergent if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F"> <mml:semantics> <mml:mi>F</mml:mi> <mml:annotation encoding="application/x-tex">F</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is semismooth at the solution and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f"> <mml:semantics> <mml:mi>f</mml:mi> <mml:annotation encoding="application/x-tex">f</mml:annotation> </mml:semantics> </mml:math> </inline-formula> satisfies a Jacobian consistency property. We show that most common smooth functions, such as the Gabriel-Moré function, have this property. As an application, we show that for box constrained variational inequalities if the involved function is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P"> <mml:semantics> <mml:mi>P</mml:mi> <mml:annotation encoding="application/x-tex">P</mml:annotation> </mml:semantics> </mml:math> </inline-formula> –uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).