Open Access
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

© Wuhan University 2023

Licence Creative CommonsThis 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], interior-point 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 semi-definite programming (SDP), linear complementarity problem (LCP), and second-order cone programming (SOCP). As a result, corresponding optimization software packages have been developed and widely adopted[2,3]. Among the existing IPMs, primal-dual IPM is recognized as one of the most efficient methods.

Initially, the classical Newton direction determined by the logarithmic kernel function was used in primal-dual IPM. However, Peng et al [4] introduced the concept of self-regular kernel function in 2001 and used it to determine the search direction, which greatly improved the theoretical iteration complexity of the primal-dual IPM. This marked an important breakthrough in IPM research. Furthermore, Bai et al[5] proposed a primal-dual IPM for linear programming based on a class of eligible kernel functions (not necessarily self-regular) and achieved excellent iteration complexity results. Currently, IPM based on kernel function is a very active research areas in mathematical programming[6-8]. Roos[2] proposed a primal-dual full-Newton step feasible IPM for LP in 1997, which avoids step size calculation and linear search and is known as the simplest primal-dual 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 full-Newton step IPM for LP and symmetric optimization (SO) based on algebraic equivalence transformation. Zhang et al proposed the full-Newton step IPM based on the positive-asymptotic kernel function to solve LCP, and obtained the best iteration result of the small-update algorithm.

Recently, Zhang and Geng et al[13,14] proposed the full-Newton step feasible (infeasible) IPM for LP and SDP respectively using the kernel function with linear growth terms. Their algorithms obtained the best-known 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 predictor-corrector IPM for the sufficient wLCP. More recently, Asadi et al[17] proposed a full-Newton 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 full-Newton 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 full-Newton step primal-dual 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 full-Newton 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 non-negative 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 full-Newton 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 full-Newton step primal-dual interior-point 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 Full-Newton Step Primal-Dual Interior-Point Algorithm

In this paper, we consider the following special wLCP, which is to find vectors such that

(1)

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)

(2)

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

(3)

Define

(4)

then (3) is equivalent to the following scale system

(5)

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

(6)

Note that the right of the third equation in system (5) is the negative gradient of the barrier function

(7)

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

(8)

where corresponds to the kernel function as . Thus, the third equations in (8) is , so the system (8) becomes

(9)

Defines proximity measure as follows

(10)

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 norm-based 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

(11)

that is strictly feasible, namely and satisfies

If iteration point satisfies condition , then the algorithm iteration terminates.

A full-Newton step primal-dual IPM for the special wLCP is given as Algorithm 1.

Algorithm 1: A full-Newton step primal-dual 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

(12)

In the same way, we also deduce that

(13)

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

(14)

Since the right-hand side is monotonically increasing with respect to , then, for with , one has

(15)

To guarantee , the inequality (15) implies that it suffices to have

(16)

where .

From (16), we obtain

At this stage, we choose , then (16) holds. This completes the proof.

3 Iterative Complexity Boundary

Let

(17)

where .

Due to , we obtain . Note that . Lemma 3 and Lemma 8 show the new iteration point obtained after full-Newton 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 well-suited for efficiently solving large-scale the special wLCP problems.

Table 1

The numerical results of the special wLCP for different sizes with t=1

5 Conclusion

In this paper, a full-Newton 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

  1. Karmarkar N K. A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4: 373-395. [CrossRef] [MathSciNet] [Google Scholar]
  2. Roos C, Terlaky T, J-Ph Vial. Theory and Algorithms for Linear Optimization: An Interior Approach[M]. Chichester: John Wiley, Sons, 1997. [Google Scholar]
  3. Yang Y G. Arc-Search Techniques for Interior-Point Methods[M]. Boca Raton: CRC Press, 2020. [CrossRef] [Google Scholar]
  4. Peng J M, Roos C. Terlaky T. Self-regular functions and new search directions for linear and semi-definite optimization[J]. Math Program, 2002, 93(1): 129-171. [CrossRef] [MathSciNet] [Google Scholar]
  5. Bai Y Q, Ghami M EL, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithm in linear optimization[J]. SIAM J Optim, 2004, 15(1):101-128. [CrossRef] [MathSciNet] [Google Scholar]
  6. Lesaja G, Wang G Q, Zhu D T. Interior-point methods for Cartesian Formula -linear complementarity problems over symmetric cones based on the eligible kernel functions[J]. Optim Method Softw, 2012, 27: 827-843. [CrossRef] [MathSciNet] [Google Scholar]
  7. Cai X Z, Li L, El Ghami M, et al. A new parametric kernel function yielding the best known iteration bounds of interior-point methods for the Cartesian Formula -LCP over symmetric cones[J]. Pac J Optim, 2017, 13(4): 547-570. [MathSciNet] [Google Scholar]
  8. Li L, Tao J Y, El Ghami M, et al. A new parametric kernel function with a trigonometric barrier term for Formula -linear complementarity problems[J]. Pac J Optim, 2017, 13(2): 255-278. [MathSciNet] [Google Scholar]
  9. Wang G Q, Yu C J, Teo K L. A full-Newton step feasible interior-point algorithm for Formula -linear complementarity problems[J]. J Glob Optim, 2014, 59(1): 81-99. [CrossRef] [Google Scholar]
  10. Darvay Z. New interior point algorithms in linear programming[J]. Adv Model Optim, 2003, 5(1): 51-92. [Google Scholar]
  11. Darvay Z, Rigo P R. New interior-point algorithm for symmetric optimization based on a positive-asymptotic barrier function[J]. Numer Func Anal Opt, 2018, 39(15): 1705-1726. [CrossRef] [MathSciNet] [Google Scholar]
  12. Zhang M W, Huang K, Li M M, et al. A new full-Newton step interior-point method for Formula -LCP based on a positive-asymptotic kernel function[J]. J Appl Math Comput, 2020, 64: 313-330. [CrossRef] [MathSciNet] [Google Scholar]
  13. Geng J, Zhang M W, Pang J J. A full-Newton 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): 501-509. [Google Scholar]
  14. Zhang M W, Geng J, Wu S. A new infeasible interior point algorithm with full-Newton steps based for linear programming based on kernel function [J]. J Nonlinear Funct Anal, 2021: Article ID 31. [Google Scholar]
  15. Potra F A. Weighted complementarity problems: A new paradigm for computing equilibria[J]. SIAM J Optim, 2012, 22(4): 1634-1654. [CrossRef] [MathSciNet] [Google Scholar]
  16. Potra F A. Sufficient weighted complementarity problems[J]. Comp Appl Math, 2016, 64: 467-488. [Google Scholar]
  17. Asadi A, Darvay Z, Lesaja G, et al. A full-Newton step interior-point method for monotone weighted linear complementarity problems[J]. J Optim Theory Appl, 2020, 186: 864-878. [CrossRef] [MathSciNet] [Google Scholar]
  18. Chi X N, Zhang R J, Liu S Y. A new full-Newton step feasible interior-point algorithm for linear weighted complementarity problem[J]. Appl Math, 2021, 34(2): 304-311. [Google Scholar]

All Tables

Table 1

The numerical results of the special wLCP for different sizes with t=1

Current usage metrics show cumulative count of Article Views (full-text 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 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.