Issue 
Wuhan Univ. J. Nat. Sci.
Volume 29, Number 1, February 2024



Page(s)  29  37  
DOI  https://doi.org/10.1051/wujns/2024291029  
Published online  15 March 2024 
Mathematics
CLC number: O221
A FullNewton Step Feasible InteriorPoint Algorithm for the Special Weighted Linear Complementarity Problems Based on a Kernel Function
^{1}
Mathematics Department, Anhui Institute of Information Technology, Wuhu 241000, Anhui, China
^{2}
College of Science, China Three Gorges University, Yichang 443002, Hubei, China
^{†} Corresponding author. Email: zmwang@ctgu.edu.cn
Received:
28
June
2023
In this paper, a new fullNewton step primaldual interiorpoint algorithm for solving the special weighted linear complementarity problem is designed and analyzed. The algorithm employs a kernel function with a linear growth term to derive the search direction, and by introducing new technical results and selecting suitable parameters, we prove that the iteration bound of the algorithm is as good as bestknown polynomial complexity of interiorpoint methods. Furthermore, numerical results illustrate the efficiency of the proposed method.
Key words: interiorpoint algorithm / weighted linear complementarity problem / fullNewton step / kernel function / iteration complexity
Cite this article: GENG Jie, ZHANG Mingwang, ZHU Dechun. A FullNewton Step Feasible InteriorPoint Algorithm for the Special Weighted Linear Complementarity Problems Based on a Kernel Function[J]. Wuhan Univ J of Nat Sci, 2024, 29(1): 2937.
Biography: GENG Jie, male, Associate professor, research direction: optimization theory and algorithm. Email: jiegeng@iflytek.com
Fundation item: Supported by University Science Research Project of Anhui Province (2023AH052921) and Outstanding Youth Talent Project of Anhui Province (gxyq2021254)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
Since Karmarkar's seminal work in linear programming (LP)^{[1]}, interiorpoint methods (IPMs) have emerged as a major research area and are widely regarded as highly effective methods. IPMs have been successfully extended to solve various optimization problems, such as semidefinite programming (SDP), linear complementarity problem (LCP), and secondorder cone programming (SOCP). As a result, corresponding optimization software packages have been developed and widely adopted^{[2,3]}. Among the existing IPMs, primaldual IPM is recognized as one of the most efficient methods.
Initially, the classical Newton direction determined by the logarithmic kernel function was used in primaldual IPM. However, Peng et al ^{[4]} introduced the concept of selfregular kernel function in 2001 and used it to determine the search direction, which greatly improved the theoretical iteration complexity of the primaldual IPM. This marked an important breakthrough in IPM research. Furthermore, Bai et al^{[5]} proposed a primaldual IPM for linear programming based on a class of eligible kernel functions (not necessarily selfregular) and achieved excellent iteration complexity results. Currently, IPM based on kernel function is a very active research areas in mathematical programming^{[68]}. Roos^{[2]} proposed a primaldual fullNewton step feasible IPM for LP in 1997, which avoids step size calculation and linear search and is known as the simplest primaldual IPM. This algorithm has also been extended to other optimization models. For example, Wang et al^{[9]} generalized Roos' method to solve LCP and Darvay et al^{[10,11]} designed the fullNewton step IPM for LP and symmetric optimization (SO) based on algebraic equivalence transformation. Zhang et al proposed the fullNewton step IPM based on the positiveasymptotic kernel function to solve LCP, and obtained the best iteration result of the smallupdate algorithm.
Recently, Zhang and Geng et al^{[13,14]} proposed the fullNewton step feasible (infeasible) IPM for LP and SDP respectively using the kernel function with linear growth terms. Their algorithms obtained the bestknown iterative complexity results and demonstrated good performance in corresponding calculation.
The weighted linear complementarity problem (wLCP), which is a generalization of the LCP, was first proposed by Potra in 2012^{[15]}. Since then, two IPMs have been proposed and analyzed for the monotonic wLCP. The wLCP has found wide applications in various fields such as science, finance, management, and engineering. Subsequently, Potra^{[16]} proposed a predictorcorrector IPM for the sufficient wLCP. More recently, Asadi et al^{[17]} proposed a fullNewton step feasible IPM for the monotonic wLCP and proved that the algorithm achieves the best known iterative complexity. Furthermore, Chi et al^{[18]} proposed a fullNewton step feasible IPM for the special wLCP based on specific continuous differentiable functions and used the Darvay algebraic equivalence transformation method to determine the search direction. Their approach yielded excellent theoretical complexity and demonstrated good practical calculation results.
A new fullNewton step primaldual IPM is proposed for the special wLCP based on the search direction determined by the kernel function with linear growth term^{[13,14]}. The algorithm eliminates the calculation of the step size by using fullNewton steps. By utilizing the simple algebraic expression of the kernel function with linear growth term, an appropriate proximity measure is defined, and new technical results are established to overcome the difficulty of convergence analysis caused by the nonnegative weight vector. Under weaker conditions, the polynomial complexity of the algorithm is proved, and its complexity order is shown to be the same as the best existing complexity order among similar methods. Numerical examples demonstrate the effectiveness of the proposed algorithm. To the authors' knowledge, this algorithm is the first fullNewton IPM based on kernel functions with linear growth terms for solving wLCP.
The remainder of this paper is organized as follows. In Section 1, we introduce the fullNewton step primaldual interiorpoint algorithm. The convergence analysis and the iteration bound of the algorithm are shown in Section 2. In Section 3, we get the upper bound of the number of iterations of the algorithm. In Section 4, we present some numerical examples and results. Finally, some conclusions are given in Section 5.
1 FullNewton Step PrimalDual InteriorPoint Algorithm
In this paper, we consider the following special wLCP, which is to find vectors such that
where is a given matrix with full row rank, , are given vectors, and is a given weight vector. When , the system (1) reduces to the KKT condition for LP. Therefore, solving for special wLCP (1) becomes a more challenging problem than solving LP.
Denote the strictly feasible set of problem (1) as
where
Choose an initial point .
Let and consider the perturbed version of problem (1)
Throughout this paper, we assume that the special wLCP (1) satisfies the interior point condition (IPC), i.e.,, which implies the existence of a solution for the problem (1). Since is a matrix supposed full row rank and the IPC holds, the parameter system (2) has a unique solution for each . It is denoted as and we call it the center of the special wLCP (1). The collection gives a homotopy path, which is called the central path of the special wLCP (1). Furthermore, if , then , so the optimal solution to the special wLCP (1) is obtained.
To determine the search direction of the algorithm, we use the Newton method for solving the system (2), where the search direction satisfies the following system
Define
then (3) is equivalent to the following scale system
where .
Definition 1 A twice differentiable function is called a kernel function, if it satisfies the following conditions
; ; .
The barrier function is determined by the kernel function as below
Note that the right of the third equation in system (5) is the negative gradient of the barrier function
Obviously, for the barrier function , its corresponding kernel function is the classical logarithmic kernel function .
The approach in this paper differs only one detail: we replace with a new barrier function , and the system (5) can be rewritten as
where corresponds to the kernel function as . Thus, the third equations in (8) is , so the system (8) becomes
Defines proximity measure as follows
Note 1 The kernel function differs from the usual kernel function in that its growth term is linear in . It was first introduced in Ref. [14] and was used to determine the iteration direction of the algorithm for LP.
Note 2 It is easy to verify that . Therefore, can be used as a measure of iterate to center of (2).
Note 3 In the existing literature, proximity measures are generally defined as . However, in this paper we define a new normbased proximity
This effectively simplifies the convergence analysis of the algorithm.
Now we outline the method. Select the appropriate parameter and any initial point , let , for . It is obvious that at the start of algorithm. Solve the system (9) and use (4) to obtain the search direction , where . The new iteration point is given by
that is strictly feasible, namely and satisfies
If iteration point satisfies condition , then the algorithm iteration terminates.
A fullNewton step primaldual IPM for the special wLCP is given as Algorithm 1.
Algorithm 1: A fullNewton step primaldual IPM for wLCP 

Input
Accuracy parameter ; update parameter let where with ; Set ; begin ; whiledo begin obtain the search direction by solving the system (9) and using (4); let ; according to (17) below, get ; set ;; end end 
2 Analysis of the Algorithm
We start with some technical lemmas that play a key role in subsequent complexity analysis.
Lemma 1 Let , and are orthogonal. Then
A basic property of the proximal measure is easily obtained by (10).
Lemma 2 Let . Then .
From the system (9), we may get . Since, according to (9), Lemma 1 and Lemma 2, we derive that
In the same way, we also deduce that
Lemma 3 Let . Then iteration points is strictly feasible, i.e., .
Proof Consider the step size and define
According to (4) and the system of equations (9), it follows that
Due to the fact that , and it follows from (12) that
Because are both linear function of and , this implies that for each . Correspondingly, we can get . Hence, is strictly feasible. This completes the proof.
Lemma 4 Let . Then
Proof By following the proof of Lemma 3 and (13), we get
This completes the proof.
Lemma 5 Let . Then the following inequality holds: .
Proof According to the proof of Lemma 3 and (13), we have
This completes the proof of the lemma.
The following lemma gives the local quadratic convergence of proximity measure.
Lemma 6 Let with . Then .
Proof By the definition of , we have
from Lemma 5, we derive
This completes the proof.
Lemma 7 Let and . Then
where
Proof From the definition of, we can get , which implies
It follows from Lemma 4 and Lemma 5 that
And note that , we obtain
This completes the proof of the lemma.
Lemma 8 Let . If , then .
Proof By Lemma 7, we have
Since the righthand side is monotonically increasing with respect to , then, for with , one has
To guarantee , the inequality (15) implies that it suffices to have
where .
From (16), we obtain
At this stage, we choose , then (16) holds. This completes the proof.
3 Iterative Complexity Boundary
Let
where .
Due to , we obtain . Note that . Lemma 3 and Lemma 8 show the new iteration point obtained after fullNewton step is strictly feasible, and
Next, we will discuss the iteration complexity of the algorithm. We first examine the value of the "dual gap".
Lemma 9 Assume that the parameters are defined as in (17). If , then
Proof From Lemma 5, we obtain
Therefore, if , then
This completes the proof.
Based on the previous discussion, the iteration bound is given by the following theorem:
Theorem 1 Assume that the parameters are defined as in (17). If the special wLCP (1) is strictly feasible, then Algorithm 1 finds an approximate solution of the special wLCP (1) after at most
iterations.
Proof From and Lemma 9, we obtain
According to (17), we get
Using the same method as Theorem 5.1 in Ref. [17], it is easy to get the upper bound of the number of iterations of the algorithm as
This completes the proof.
4 Numerical Examples
This section presents several numerical experiments to show the effectiveness of the algorithm. The numerical results are obtained by using MATLAB 2014b on an Intel Core i5 (3.10 GHz) with 4 GB RAM.
Throughout all experiments, we set the precision parameter . Six kinds of the special wLCPs with different sizes are randomly generated. In detail, we generate a random six matrices with full rows rank, a random weighted vectors . We take the initial point , and are defined as in (17). The CPU time in second (Time), the number of iterations (Iter) are shown in Table 1 as follows.
• For the special wLCP of the same scale, the number of iterations and the runtime are positively correlated with the upper bound of ;
• When the upper bound of is fixed, we observe a positive correlation between the number of iterations and the runtime with the scale of the special wLCP, specifically with the problem size parameters and ;
• As the size parameters and increase, the number of iterations does not significantly increase, suggesting that the algorithm is wellsuited for efficiently solving largescale the special wLCP problems.
The numerical results of the special wLCP for different sizes with t=1
5 Conclusion
In this paper, a fullNewton step IPM for wLCP based on a kernel function is proposed. Applying this function to the central path, new search directions for wLCP are obtained. The analysis of wLCP is more complicated than LCP because of the nonzero weight vector. We prove the feasibility and convergence of Algorithm 1. Numerical results indicate the efficiency of our algorithm.
References
 Karmarkar N K. A new polynomialtime algorithm for linear programming[J]. Combinatorica, 1984, 4: 373395. [CrossRef] [MathSciNet] [Google Scholar]
 Roos C, Terlaky T, JPh Vial. Theory and Algorithms for Linear Optimization: An Interior Approach[M]. Chichester: John Wiley, Sons, 1997. [Google Scholar]
 Yang Y G. ArcSearch Techniques for InteriorPoint Methods[M]. Boca Raton: CRC Press, 2020. [CrossRef] [Google Scholar]
 Peng J M, Roos C. Terlaky T. Selfregular functions and new search directions for linear and semidefinite optimization[J]. Math Program, 2002, 93(1): 129171. [CrossRef] [MathSciNet] [Google Scholar]
 Bai Y Q, Ghami M EL, Roos C. A comparative study of kernel functions for primaldual interiorpoint algorithm in linear optimization[J]. SIAM J Optim, 2004, 15(1):101128. [CrossRef] [MathSciNet] [Google Scholar]
 Lesaja G, Wang G Q, Zhu D T. Interiorpoint methods for Cartesian linear complementarity problems over symmetric cones based on the eligible kernel functions[J]. Optim Method Softw, 2012, 27: 827843. [CrossRef] [MathSciNet] [Google Scholar]
 Cai X Z, Li L, El Ghami M, et al. A new parametric kernel function yielding the best known iteration bounds of interiorpoint methods for the Cartesian LCP over symmetric cones[J]. Pac J Optim, 2017, 13(4): 547570. [MathSciNet] [Google Scholar]
 Li L, Tao J Y, El Ghami M, et al. A new parametric kernel function with a trigonometric barrier term for linear complementarity problems[J]. Pac J Optim, 2017, 13(2): 255278. [MathSciNet] [Google Scholar]
 Wang G Q, Yu C J, Teo K L. A fullNewton step feasible interiorpoint algorithm for linear complementarity problems[J]. J Glob Optim, 2014, 59(1): 8199. [CrossRef] [Google Scholar]
 Darvay Z. New interior point algorithms in linear programming[J]. Adv Model Optim, 2003, 5(1): 5192. [Google Scholar]
 Darvay Z, Rigo P R. New interiorpoint algorithm for symmetric optimization based on a positiveasymptotic barrier function[J]. Numer Func Anal Opt, 2018, 39(15): 17051726. [CrossRef] [MathSciNet] [Google Scholar]
 Zhang M W, Huang K, Li M M, et al. A new fullNewton step interiorpoint method for LCP based on a positiveasymptotic kernel function[J]. J Appl Math Comput, 2020, 64: 313330. [CrossRef] [MathSciNet] [Google Scholar]
 Geng J, Zhang M W, Pang J J. A fullNewton step feasible IPM for semidefinite optimization based on a kernel function with linear growth term[J]. Wuhan University Journal of Natural Sciences, 2020, 25 (6): 501509. [Google Scholar]
 Zhang M W, Geng J, Wu S. A new infeasible interior point algorithm with fullNewton steps based for linear programming based on kernel function [J]. J Nonlinear Funct Anal, 2021: Article ID 31. [Google Scholar]
 Potra F A. Weighted complementarity problems: A new paradigm for computing equilibria[J]. SIAM J Optim, 2012, 22(4): 16341654. [CrossRef] [MathSciNet] [Google Scholar]
 Potra F A. Sufficient weighted complementarity problems[J]. Comp Appl Math, 2016, 64: 467488. [Google Scholar]
 Asadi A, Darvay Z, Lesaja G, et al. A fullNewton step interiorpoint method for monotone weighted linear complementarity problems[J]. J Optim Theory Appl, 2020, 186: 864878. [CrossRef] [MathSciNet] [Google Scholar]
 Chi X N, Zhang R J, Liu S Y. A new fullNewton step feasible interiorpoint algorithm for linear weighted complementarity problem[J]. Appl Math, 2021, 34(2): 304311. [Google Scholar]
All Tables
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.