jagomart
digital resources
picture1_Solving Quadratic Equations Pdf 174559 | 2145 8472 Rein 39 02 191


 128x       Filetype PDF       File size 0.24 MB       Source: www.scielo.org.co


File: Solving Quadratic Equations Pdf 174559 | 2145 8472 Rein 39 02 191
h revistaintegracion escuela de matematicas universidad industrial de santander vol 39 n 2 2021 pag 191 215 aglobal jacobian smoothing algorithm for nonlinear complementarity problems wilmer sancheza rosana perezb hector ...

icon picture PDF Filetype PDF | Posted on 27 Jan 2023 | 2 years ago
Partial capture of text on file.
                            H RevistaIntegración
                                       Escuela de Matemáticas
                                       Universidad Industrial de Santander
                                       Vol. 39, N◦ 2, 2021, pág. 191–215
                                  Aglobal Jacobian smoothing algorithm for
                                         nonlinear complementarity problems
                               Wilmer Sáncheza, Rosana Pérezb , Héctor J. Martínezc
                                        a,b Universidad del Cauca, Departamento de Matemáticas, Popayán, Colombia.
                                            c Universidad del Valle, Departamento de Matemáticas, Cali, Colombia.
                                  Abstract. In this paper, we use the smoothing Jacobian strategy to propose
                                  a new algorithm for solving complementarity problems based on its reformu-
                                  lation as a nonsmooth system of equations. This algorithm can be seen as a
                                  generalization of the one proposed in [18]. We develop its global convergence
                                  theory and under certain assumptions, we demonstrate that the proposed
                                  algorithm converges locally and, q-superlinearly or q-quadratically to a solu-
                                  tion of the problem. Some numerical experiments show a good performance
                                  of this algorithm.
                                  Keywords: Nonlinear complementarity problems, complementarity function,
                                  generalized Newton methods, Jacobian smoothing method, global conver-
                                  gence, superlinear convergence, quadratic convergence.
                                  MSC2010: 49M15, 90C06, 90C30.
                                   Un algoritmo global con jacobiano suavizado para
                                         problemas de complementariedad no lineal
                                  Resumen. En este artículo, usamos la estrategia del jacobiano suavizado para
                                  proponer un nuevo algoritmo para resolver problemas de complementariedad
                                  no lineal basado en su reformulación como un sistema de ecuaciones no li-
                                  neales. Este algoritmo puede verse como una generalización del propuesto en
                                  [18]. Desarrollamos su teoría de convergencia global y bajo ciertas hipótesis,
                                  demostramos que el algoritmo converge local y q superlineal o q cuadráti-
                                  camente a la solución del problema. Pruebas numéricas muestran un buen
                                  desempeño del algoritmo propuesto.
                                  Palabras clave: Complementariedadnolineal,funcióndecomplementariedad,
                                  método de Newton generalizado, Jacobiano suavizado, convergencia global,
                                  convergencia superlineal, convergencia cuadrática.
                              0   E-mail: wilmersanchez@unicauca.edu.coa, rosana@unicauca.edu.cob, hector.martinez@correounivalle.edu.coc.
                                  Received: 11 october 2020, Accepted: 14 june 2021.
                                  To cite this article: W. Sánchez, R. Pérez & H. J. Martínez, A global Jacobian smoothing algorithm
                                  for nonlinear complementarity problems, Rev. Integr. Temas Mat., 39 (2021), No. 2, 191-215. doi:
                                  10.18273/revint.v39n2-20210004
                                                                             191
                        192               Wilmer Sánchez, Rosana Pérez & Héctor J. Martínez
                        1.    Introduction
                        TheNonlinearComplementarityProblem, (NCP),whichinsomecontextsissynonymous
                        with system in equilibrium, arises among others, in applications to Physics, Engineering,
                        and Economics [3], [8], [14], [19]. The problem is to find a vector x ∈ Rn such that
                                                T                       n      n
                        x≥0,F(x)≥0 and x F(x)=0, with F: R →R continuously differentiable. Here,
                        a vector is nonnegative if all its components are nonnegative. A widely used technique
                        for solving the NCP is to reformulate it as a system of nonlinear equations using a
                        complementarity function φ: R2 → R such that
                                                  φ(a,b) = 0 ⇐⇒ a ≥ 0, b ≥ 0, ab = 0.                            (1)
                        Then, we consider Φ: Rn → Rn and define the nonlinear system of equations
                                                              φ(x1,F1(x)) 
                                                                      .       
                                                     Φ(x)=            .        = 0,                            (2)
                                                                       .
                                                                 φ(x ,F (x))
                                                                     n  n
                        whichis a nondifferentiable system due to the lack of smoothness of φ. From (1), a vector
                        x is a solution of (2), if, and only if, x   it is a solution of the NCP. To solve (2) and
                          ∗                                        ∗
                        thus, to solve the NCP, a nonsmooth algorithms type Newton [27], [29] and quasi-Newton
                        [20], [21], among others [1], [6], [22], [26], [31] have been proposed. The natural merit
                                            n                              1        2
                        function [24] Ψ: R     →R, defined by Ψ(x) =          ∥Φ(x)∥ , is used in the globalization
                                                                           2        2
                        of these methods. Thus, Ψ(x) is minimized in Rn. These methods use the concept of
                        generalized Jacobian [10] defined by the set
                                                            ′         n×n                          
                                     ∂G(x) = conv      lim G (x ) ∈ R      :  lim x →x, x ∈D           ,         (3)
                                                      k→∞       k            k→∞ k           k     G
                        for a Lipschitz continuous function G: Rn → Rn, in x, where D            denotes the set of
                                                                                              G
                        all points where is G is differentiable and hull{A} is the convex envelope of A. This
                        set is nonempty, convex, and compact [11]. Usually, the set (3) is difficult to compute,
                        for this reason, we use the overestimation ∂G(x)T ⊆ ∂G1(x) × ··· × ∂Gn(x) given in
                        [11], where the right side, for short ∂ G(x)T [18], called C-sub differential of G at x,
                                                               C
                        is the set of matrices Rn×n, whose i-th column is the generalized gradient of the i-th
                        component of the function G.
                        Another strategy to solve (2) is to smooth the Jacobian proposed in [9] and called Jaco-
                        bian smoothing in [18]. The general idea of methods using this strategy is to approximate
                        Φ by a smooth function Φµ: Rn → Rn, where µ > 0 is the smoothing parameter, and
                        then solving a sequence of smooth nonlinear equation systems,
                                                               φ (x ,F (x)) 
                                                                   µ  1   1
                                                                       .        
                                                    Φ (x) =            .         = 0,                          (4)
                                                     µ                  .
                                                                 φ (x ,F (x))
                                                                   µ  n   n
                        with µ going to zero and φµ a smoothing function of φ used in (2). The system (4) is
                        solved at each iteration by solving the mixed Newton equation) Φ′ (x )s       = −Φ(x ).
                                                                                             µ   k  k          k
                                                                                               [Revista Integración
                                   Aglobal Jacobian smoothing algorithm for nonlinear complementarity problems              193
                           In [18], the authors present a new algorithm with good numerical performance based
                           on the Jacobian smoothing strategy to solve the NCP, by reformulating it as a system
                           of nonlinear equations using the Fischer-Burmeister complementary function defined by
                                       √ 2      2
                           φ(a,b) =      a +b −a−b. Motivated by the results obtained with this function, and
                           since it is a particular case of the following family of complementary functions [17]
                                                              q         2
                                                 φ (a,b) =      (a−b) +λab−a−b,               λ∈(0,4),                       (5)
                                                   λ
                           correspondingto λ = 2, in this paper we use this strategy with the family (5) to propose a
                           new algorithm that solves complementarity problems by reformulating it as a nonlinear,
                           nondifferentiable system of equations. This algorithm can be seen as a generalization
                           of the one proposed in [18] to any member of family φ , with λ in (0, 4). Under
                                                                                               λ
                           certain hypotheses, we demonstrate that the proposed algorithm converges local and, q-
                           superlinear or q-quadratically to a solution of the complementarity problem. In addition,
                           we analyze the numerical performance of the proposed algorithm.
                           The organization of this paper is as follows. In Section 2, we present the Jacobian
                           smoothing strategy applied to a function Φλ, we described the Jacobian matrix of its
                           smoothing and find an upper bound of the parameter µ which will be very important in
                           the algorithmic proposal. In Section 3, we present some preliminary results that we use
                           to develop the convergence theory of the algorithm proposed. In Section 4, we present
                           a new Jacobian smoothing algorithm to solve nonlinear complementarity problems that
                           generalize the one presented in [18] to all members of family (5). Moreover, we prove
                           that our algorithm is well defined. In Section 5, we develop its global convergence theory.
                           In Section 6, under some hypotheses, we prove that the algorithm converges local and
                           q-superlinear or q-quadratically to the solution of the complementarity problem. In
                           Section 8, we analyze the numerical performance of the proposed algorithm. Finally, In
                           Section 9, we present our concluding remarks.
                           2.    Smoothing Jacobian strategy for Φ (x) = 0
                                                                                    λ
                           We consider the reformulation (2) of the NCP as a nonsmooth nonlinear system of
                           equations. If φ = φ , the family (5), we obtain the system Φ (x) = 0. The basic
                                                    λ                                                  λ
                           iteration of a generalized Newton method to solve this system has the form,
                                                                   H s = −Φ (xk),                                            (6)
                                                                     k k         λ
                           where H ∈ ∂Φ (xk) or H ∈ ∂ Φ (xk). Here, we use H ∈ ∂ Φ (xk). In order to
                                     k        λ             k     C λ                            k     C λ
                           define a smoothing Jacobian method for Φλ(x) = 0, we follow the basic idea given in
                           [18] and we consider smoothing φ          as proposed in [4]: for all λ ∈ (0,4) and µ > 0,
                                                                  λ
                                                   p          2
                                     φ (a,b) =        (a−b) +λab+(4−λ)µ−a−b = G (a,b) − a − b.                               (7)
                                       λµ                                                          λµ
                           As expected, the distance between φ              and its smoothing function, φ           , is upper
                                                                         λ                                       λµ
                           bounded by a constant that depends on the parameters λ and µ. This is a particu-
                           lar case of the following proposition that will be useful in the convergence theory.
                           Proposition 2.1. Function φλµ satisfies the inequality
                                                                                 √        √       √
                                                   |φ    (a,b) −φ      (a,b)| ≤    4−λ| µ − µ |,
                                                     λµ            λµ                         1       2
                                                        1             2
                           Vol. 39, No. 2, 2021]
                          194                Wilmer Sánchez, Rosana Pérez & Héctor J. Martínez
                                              2                                                      √        √
                          for all (a,b) ∈ R      and µ ,µ ≥ 0. In particular, |φ           −φ | ≤       4−λ µ, for all
                                                       1   2                           λµ      λ
                          (a,b) ∈ R2, λ ∈ (0,4) and µ ≥ 0.
                          Proof. Let (a,b) ∈ R2, µ      and µ nonnegatives, such that µ ̸= µ .
                                                      1        2                              1     2
                                                                                                                 
                                                                                           (µ −µ )(4−λ)          
                            |φ   (a,b) −φ      (a,b)| = |G      (a,b) −G      (a,b)| =        1    2              ·
                              λµ            λµ              λµ            λµ
                                1             2                1             2          G    (a,b) +G      (a,b)
                                                                                           λµ            λµ
                                                                                             1             2
                                                       p
                          Observe that G      (a,b) ≥    µ(4−λ). Then
                                           λµ
                                                                  |(µ1 −µ2)(4−λ)|          √       √ √
                                   |φ    (a,b) −φ      (a,b)| ≤                √        ≤| µ − µ | 4−λ.
                                     λµ            λµ             √      √                     1       2
                                        1             2          (  µ + µ ) 4−λ
                                                                     1       2
                                                                                        √       √                        ✓
                                                                                                                         ✓✓
                          In particular, if µ = µ and µ = 0 then |φ           −φ |≤ 4−λ µ.                               □
                                              1             2              λµ      λ
                          From (7), we define the function Φ         : Rn → Rn by,
                                                                 λµ
                                                                     φ (x ,F (x)) 
                                                                         λµ   1   1
                                                                              .         
                                                        Φλµ(x) =              .         ·                             (8)
                                                                               .
                                                                        φ (x ,F (x))
                                                                         λµ   n   n
                          The next proposition gives an upper bound for the distance between Φλ and its approx-
                          imation Φλµ.
                          Proposition 2.2. The function Φλµ satisfies the following inequalities
                                                             √       √
                             i) ∥Φλµ1(x)−Φλµ2(x)∥ ≤ κ| µ1 −            µ2|.
                                                         √
                            ii) ∥Φλµ(x)−Φλ(x)∥ ≤ κ µ.
                                        n                                     p
                          for all x ∈ R , and µ,µ1,µ2 ≥ 0, where κ =             n(4−λ).
                          Proof. Using the Euclidean norm and Proposition 2.1,
                                                           v
                                                           un
                                                              X
                                                           u                                           2
                             ∥Φ     (x)−Φ      (x)∥    = t [φ (x,F(x))−φ (x,F(x))]
                                λµ          λµ                      λµ    i   i         λµ    i  i
                                  1           2                        1                  2
                                                              i=1
                                                           r h √          √ √           i2   p            √       √
                                                       ≤      n ( µ1− µ2) 4−λ = n(4−λ)| µ1− µ2|.
                                                                                                                         ✓
                                                                                                                         ✓✓
                          The second part of the proposition is obtained by choosing µ1 = µ and µ2 = 0.                  □
                          Now, the basic iteration of a smoothing Jacobian method for solving Φλ(x) = 0 is as
                          follows
                                                              ′   k                   k
                                                            Φ (x )s       = −Φ (x ),                                    (9)
                                                              λµ      k           λ
                                                                                      k
                                                                  xk+1    = sk + x ,
                                                                                                     [Revista Integración
The words contained in this file might help you see if this file matches what you are looking for:

...H revistaintegracion escuela de matematicas universidad industrial santander vol n pag aglobal jacobian smoothing algorithm for nonlinear complementarity problems wilmer sancheza rosana perezb hector j martinezc a b del cauca departamento popayan colombia c valle cali abstract in this paper we use the strategy to propose new solving based on its reformu lation as nonsmooth system of equations can be seen generalization one proposed develop global convergence theory and under certain assumptions demonstrate that converges locally q superlinearly or quadratically solu tion problem some numerical experiments show good performance keywords function generalized newton methods method conver gence superlinear quadratic msc m un algoritmo con jacobiano suavizado para problemas complementariedad no lineal resumen en este articulo usamos la estrategia proponer nuevo resolver basado su reformulacion como sistema ecuaciones li neales puede verse una generalizacion propuesto desarrollamos teoria co...

no reviews yet
Please Login to review.