# Complexity Analysis of Primal-Dual Interior-Point  Methods for Linear Optimization Based on a New Parametric Kernel Function with a Trigonometric Barrier Term

Authors: X. Z. Cai; G. Q. Wang; M. El Ghami; Y. J. Yue
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We introduce a new parametric kernel function, which is a combination of the classic kernel
function and a trigonometric barrier term, and present various properties of this new kernel function. A
class of large- and small-update primal-dual interior-point methods for linear optimization based on this
parametric kernel function is proposed. By utilizing the feature of the parametric kernel function, we derive
the iteration bounds for large-update methods,O
(
n
2
/
3
log
⁡
(
n
/
ε
)
), and small-update methods, O
(
n
log
⁡
(
n
/
ε
)
). These results match the currently best known iteration bounds for large- and small-update methods based on the trigonometric kernel functions.


---

## Body

## 1. Introduction

In this paper, we consider the linear optimization (LO) problem in standard form(
P
)
min
⁡
{
c
T
x
:
A
x
=
b
,
x
≥
0
}
,
where A
∈
R
m
×
n with rank(
A
)
=
m, b
∈
R
m, and c
∈
R
n. The dual problem of (
P
) is given by
(
D
)
max
⁡
{
b
T
y
:
A
T
y
+
s
=
c
,
s
≥
0
}
.For years, LO has been one of the most active research areas in mathematical programming. There are many solution approaches for LO. Among them, the interior-point methods (IPMs) gain much more attention. Several efficient IPMs for LO and a large amount of results have been proposed. For an overview of the relevant results, see a recent book on this subject [1] and the references cited therein.In the literature two types of primal-dual IPMs are distinguished: large-update methods and small-update methods, according to the value of the barrier-update parameterθ. However, there is still a gap between the practical behavior of these algorithms and these theoretical performance results. The so-called large-update IPMs have superior practical performance but with relatively weak theoretical results. While the so-called small-update IPMs enjoy the best known worst-case iteration bounds but their performance in computational practice is poor.Recently, this gap was reduced by Peng et al. [2] who introduced the so-called self-regular kernel functions and designed primal-dual IPMs based on self-regular proximities for LO. They improved the iteration bound for large-update methods from O
(
n
log
⁡
(
n
/
ε
)
) to O
(
n
log
⁡
n
log
⁡
(
n
/
ε
)
), which almost closes the gap between the iteration bounds for large- and small-update methods. Later, Bai, et al. [3] presented a large class of eligible kernel functions, which is fairly general and includes the classical logarithmic function and the self-regular functions, as well as many non-self-regular functions as special cases. The best known iteration bounds for LO obtained are as good as the ones in [2] for appropriate choices of the eligible kernel functions. Some well-known eligible kernel functions and the corresponding iteration bounds for large- and small-update methods are collected in Table 1. For some other related kernel-function based IPMs we refer to the recent books on this subject [4, 5].Table 1
Complexity results for the eligible kernel functions.
i
The eligible kernel functionsψ
i
(
t
)
Large-update methods
Small-update methods
Reference
1
t
2
-
1
2
-
log
⁡
t
O
(
n
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
For example [1]
2
1
2
(
t
-
1
t
)
2
O
(
n
2
/
3
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[3]
3
t
2
-
1
2
+
t
1
-
q
-
1
q
-
1
,
q
>
1
O
(
q
n
(
q
+
1
)
/
2
q
log
⁡
n
ε
)
O
(
q
2
n
log
⁡
n
ε
)
[3]
4
t
2
-
1
2
+
t
1
-
q
-
1
q
(
q
-
1
)
-
q
-
1
q
(
t
-
1
)
,
q
>
1
O
(
q
n
(
q
+
1
)
/
2
q
log
⁡
n
ε
)
O
(
q
2
n
log
⁡
n
ε
)
[2]
5
t
2
-
1
2
+
e
1
/
t
-
e
e
O
(
n
(
log
⁡
n
)
2
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[3]
6
t
2
-
1
2
-
∫
1
t
‍
e
1
/
ξ
-
1
d
ξ
O
(
n
(
log
⁡
n
)
2
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[3]
7
t
2
-
1
2
+
e
q
(
1
/
t
-
1
)
-
q
q
,
q
≥
1
O
(
q
n
log
⁡
n
ε
)
O
(
q
q
n
log
⁡
n
ε
)
[9]
8
t
2
-
1
2
-
∫
1
t
‍
e
q
(
1
/
ξ
-
1
)
d
ξ
,
q
≥
1
O
(
q
n
log
⁡
n
ε
)
O
(
q
q
n
log
⁡
n
ε
)
[3]
9
t
2
-
1
2
+
6
π
tan
⁡
(
π
(
1
-
t
)
2
+
4
t
)
O
(
n
3
/
4
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[6]
10
t
2
-
1
2
-
log
⁡
(
t
)
+
1
8
tan
2
(
π
(
1
-
t
)
2
+
4
t
)
O
(
n
2
/
3
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[7]
11
t
2
-
1
2
-
∫
1
t
‍
e
3
(
tan
⁡
(
π
2
+
2
ξ
)
-
1
)
d
ξ
O
(
n
(
log
⁡
n
)
2
log
⁡
n
ε
)
O
(
n
log
⁡
n
ε
)
[8]
12
t
-
1
+
t
1
-
q
-
1
q
-
1
,
q
>
1
O
(
q
n
log
⁡
n
ε
)
O
(
q
2
n
log
⁡
n
ε
)
[3]
13
{
t
p
+
1
-
1
p
+
1
+
t
1
-
q
-
1
q
-
1
,
t
>
0
,
p
∈
[
0,1
]
,
q
>
1
t
p
+
1
-
1
p
+
1
-
log
⁡
t
,
t
>
0
,
p
∈
[
0,1
]
,
q
=
1
O
(
q
n
(
p
+
q
)
/
(
q
(
1
+
p
)
)
log
⁡
n
ε
)
O
(
q
2
n
log
⁡
n
ε
)
[10]Particularly, El Ghami et al. [6] first introduced a trigonometric kernel function for primal-dual IPMs in LO. They established the worst case iteration bounds for large- and small-update methods, namely, O
(
n
3
/
4
log
⁡
(
n
/
ε
)
) and O
(
n
log
⁡
(
n
/
ε
)
), respectively. Peyghami et al. [7] considered a new kernel function with a trigonometric barrier term. Based on this kernel function, they proved that large-update method for solving LO has the worst case iteration bound, namely, O
(
n
2
/
3
log
⁡
(
n
/
ε
)
), which improves the so far obtained iteration bound for large-update methods based on the trigonometric kernel function proposed in [6]. Recently, Peyghami and Hafshejani [8] established the better iteration bound O
(
n
(
log
⁡
(
n
)
)
2
log
⁡
(
n
/
ε
)
) for large-update methods based on a new kernel function consisting of a trigonometric function in its barrier term.Motivated by their work, the purpose of this paper is to deal with the so-called primal-dual IPMs for LO based on a new kind of parametric kernel function as follows:(1)
ψ
(
t
)
=
t
2
-
1
2
-
log
⁡
t
+
λ
tan
2
(
h
(
t
)
)
,
where 0
<
λ
≤
8
/
25
π (the bound of the λ is due to the proof of Lemma 3) and h
(
t
)
=
π
(
1
-
t
)
/
(
3
t
+
2
). We develop some new properties of the parametric kernel function, as well as the corresponding barrier function. Compared to the existing ones, the proposed function has a parameter λ. This implies that our kernel function includes a class of kernel functions. Furthermore, we present a class of primal-dual IPMs for LO based on this new parametric kernel function. The obtained iteration bound for large-update methods, namely, O
(
n
2
/
3
log
⁡
(
n
/
ε
)
), which improves the classical iteration complexity with a factor n
1
/
3, and for small-update methods, we derive the iteration bound, namely, O
(
n
log
⁡
(
n
/
ε
)
), which matches the currently best known iteration bound for small-update methods.The paper is organized as follows. In Section2, we present the framework of kernel-based IPMs for LO. In Section 3, we introduce the new parametric kernel function with a trigonometric barrier term and develop some useful properties of the new kernel function, as well as the corresponding barrier function. The analysis and complexity of the algorithms for large- and small-update methods are presented in Section 4. Finally, Section 5 contains some conclusions and remarks.Some notations used throughout the paper are as follows.R
n, R
+
n, and R
+
+
n denote the set of vectors with n components, the set of nonnegative vectors, and the set of positive vectors, respectively. ∥
x
∥ denotes the 2-norm of the vector x. e denotes the identity vector. For any x
∈
R
n, x
min
⁡ (or x
max
⁡) denotes the smallest (or largest) value of the components of x. Finally, if g
(
x
)
≥
0 is a real valued function of a real nonnegative variable, the notation g
(
x
)
=
O
(
x
) means that g
(
x
)
≤
c
-
x for some positive constant c
- and g
(
x
)
=
Θ
(
x
) means that c
1
x
≤
g
(
x
)
≤
c
2
x for two positive constants c
1 and c
2.


## 2. Framework of Kernel-Based IPMs for LO

In this section, we briefly recall the framework of kernel-based IPMs for LO, which includes the central path, the new search directions, and the generic primal-dual interior-point algorithm for LO.


### 2.1. Central Path for LO

Throughout the paper, we assume that both(
P
) and (
D
) satisfy the interior-point condition (IPC); that is, there exists (
x
0
,
y
0
,
s
0
) such that
(2)
A
x
0
=
b
,
x
0
>
0
,
A
T
y
0
+
s
0
=
c
,
s
0
>
0
.The Karush-Kuhn-Tucker (KKT) conditions for(
P
) and (
D
) are given by
(3)
A
x
=
b
,
x
≥
0
,
A
T
y
+
s
=
c
,
s
≥
0
,
x
s
=
0
,
where x
s denotes the component-wise product of the vectors of x and s. The standard approach is to replace the third equation in (3), the so-called complementarity condition for (
P
) and (
D
), by the parameterized equation x
s
=
μ
e, with μ
>
0. This yields the following system:
(4)
A
x
=
b
,
x
≥
0
,
A
T
y
+
s
=
c
,
s
≥
0
,
x
s
=
μ
e
.Sincerank
⁡
(
A
)
=
m and the IPC holds, the parameterized system (4) has a unique solution for each μ
>
0. This solution is denoted as (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) and we call x
(
μ
) the μ-center of (
P
) and (
y
(
μ
)
,
s
(
μ
)
) the μ-center of (
D
). The set of μ-centers (with μ running through all positive real numbers) gives a homotopy path, which is calledthe central path of (
P
) and (
D
). If μ
→
0, then the limit of the central path exists and since the limit points satisfy the complementarity condition (3), the limit yields optimal solutions for (
P
) and (
D
) (see, e.g., [1]).


### 2.2. New Search Directions

IPMs follow the central path approximately and approach the optimal set of LO by lettingμ go to zero. Applying Newton’s method to the system (4), we have
(5)
A
Δ
x
=
0
,
A
T
Δ
y
+
Δ
s
=
0
,
s
Δ
x
+
x
Δ
s
=
μ
e
-
x
s
.This system has a unique solution [2, 3]. Defining the vector
(6)
v
:
=
x
s
μ
.Note that the triple(
x
,
y
,
s
) coincides with the μ-center (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) if and only if v
=
e. For further use we introduce the scaled search directions d
x and d
s according to
(7)
d
x
:
=
v
Δ
x
x
,
d
s
:
=
v
Δ
s
s
.By using (6) and (7), after some elementary reductions, we have
(8)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
v
-
1
-
v
,
where A
¯
:
=
(
1
/
μ
)
A
V
-
1
X with V
:
=
diag
⁡
(
v
)
,
X
:
=
diag
⁡
(
x
).It is obvious that the right-hand sidev
-
1
-
v in the third equation of the system (8) equals minus the derivative of the classic barrier function as follows:
(9)
Ψ
c
(
v
)
:
=
∑
i
=
1
n
‍
ψ
c
(
v
i
)
,
v
∈
R
+
+
n
,
where
(10)
ψ
c
(
t
)
=
t
2
-
1
2
-
log
⁡
t
is the kernel function of the classic barrier function. Thus, the system (8) can be rewritten as the following system:
(11)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
-
∇
Ψ
c
(
v
)
.Corresponding to the parametric kernel function (1), we define the barrier function Ψ
(
v
)
:
R
+
+
n
→
R
+ as follows:
(12)
Ψ
(
v
)
:
=
∑
i
=
1
n
‍
ψ
(
v
i
)
.Due to the properties of the parametric kernel functionψ
(
t
), see, for example, Section 3, we can conclude that Ψ
(
v
) is a strictly convex function and attains minimal value at v
=
e and Ψ
(
e
)
=
0; that is,
(13)
∇
Ψ
(
v
)
=
0
⟺
Ψ
(
v
)
=
0
⟺
v
=
e
.Hence, the value ofΨ
(
v
) can be considered as a measure of the distance between the given iterate and the μ-center of the algorithms.The approach in this paper differs only in one detail: we replace the right-hand side of the third equation in (8) by -
∇
Ψ
(
v
). This yields the following system:
(14)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
-
∇
Ψ
(
v
)
.The scaled search directionsd
x and d
s are orthogonal vectors due to the fact that d
x belongs to the null space and d
s to the row space of the matrix A
¯. From (13), one may easily verify that the right-hand side in the system (14) vanishes if and only if v
=
e. Thus we conclude that Δ
x, Δ
y, and Δ
s all vanish if and only if v
=
e, that is, if and only if x
=
x
(
μ
), y
=
y
(
μ
), and s
=
s
(
μ
). Otherwise, we will use (
Δ
x
,
Δ
y
,
Δ
s
) as the new search direction.For the analysis of the interior-point algorithm, we define the norm-based proximity measureδ
(
v
) as follows:
(15)
δ
(
v
)
:
=
1
2
∥
∇
Ψ
(
v
)
∥
.One can easily verify that(16)
d
x
=
d
s
=
0
⟺
∇
Ψ
(
v
)
=
0
⟺
δ
(
v
)
=
0
⟺
Ψ
(
v
)
=
0
⟺
v
=
e
.


### 2.3. Generic Primal-Dual Algorithm for LO

In general each kernel function gives rise to a primal-dual interior-point algorithm. Without loss of generality we assume that(
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) is known for some positive μ. For example, due to the above assumption we may assume this for μ
=
1, with x
(
1
)
=
s
(
1
)
=
e. Then, we decrease μ to μ
:
=
(
1
-
θ
)
μ for some θ
∈
(
0,1
). We solve the scaled Newton system (14) and through (7) to get the new search direction (
Δ
x
,
Δ
y
,
Δ
s
). The new triple (
x
+
,
y
+
,
s
+
) is given by
(17)
x
+
:
=
x
+
α
Δ
x
,
y
+
:
=
y
+
α
Δ
y
,
s
+
:
=
s
+
α
Δ
s
,
where α denotes the default step size, α
∈
(
0,1
], which has to be chosen appropriately. If necessary, we repeat the procedure until we find iterates that are in the neighborhood of (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
). Then μ is again reduced by the factor 1
-
θ and we apply Newton’s method targeting the new μ-centers, and so on. This process is repeated until μ is small enough, say until n
μ
<
ε; at this stage we have found an ε-solution of (
P
) and (
D
). The generic form of this algorithm is shown in Algorithm 1.Algorithm 1:
Generic primal-dual interior-point algorithm for LO.
Input:
A threshold parameterτ
>
0;
an accuracy parameterε
>
0;
a fixed barrier update parameterθ
,
0
<
θ
<
1;
begin
x
:
=
e
;
s
:
=
e
;
μ
:
=
1;
while  n
μ
≥
ε  do
begin
μ
:
=
(
1
-
θ
)
μ;
while  Ψ
(
v
)
>
τ  do
begin
calculate the search direction(
Δ
x
,
Δ
y
,
Δ
s
);
determine the default step sizeα;
update(
x
,
y
,
s
)
:
=
(
x
,
y
,
s
)
+
α
(
Δ
x
,
Δ
y
,
Δ
s
).
end
end
end


## 2.1. Central Path for LO

Throughout the paper, we assume that both(
P
) and (
D
) satisfy the interior-point condition (IPC); that is, there exists (
x
0
,
y
0
,
s
0
) such that
(2)
A
x
0
=
b
,
x
0
>
0
,
A
T
y
0
+
s
0
=
c
,
s
0
>
0
.The Karush-Kuhn-Tucker (KKT) conditions for(
P
) and (
D
) are given by
(3)
A
x
=
b
,
x
≥
0
,
A
T
y
+
s
=
c
,
s
≥
0
,
x
s
=
0
,
where x
s denotes the component-wise product of the vectors of x and s. The standard approach is to replace the third equation in (3), the so-called complementarity condition for (
P
) and (
D
), by the parameterized equation x
s
=
μ
e, with μ
>
0. This yields the following system:
(4)
A
x
=
b
,
x
≥
0
,
A
T
y
+
s
=
c
,
s
≥
0
,
x
s
=
μ
e
.Sincerank
⁡
(
A
)
=
m and the IPC holds, the parameterized system (4) has a unique solution for each μ
>
0. This solution is denoted as (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) and we call x
(
μ
) the μ-center of (
P
) and (
y
(
μ
)
,
s
(
μ
)
) the μ-center of (
D
). The set of μ-centers (with μ running through all positive real numbers) gives a homotopy path, which is calledthe central path of (
P
) and (
D
). If μ
→
0, then the limit of the central path exists and since the limit points satisfy the complementarity condition (3), the limit yields optimal solutions for (
P
) and (
D
) (see, e.g., [1]).


## 2.2. New Search Directions

IPMs follow the central path approximately and approach the optimal set of LO by lettingμ go to zero. Applying Newton’s method to the system (4), we have
(5)
A
Δ
x
=
0
,
A
T
Δ
y
+
Δ
s
=
0
,
s
Δ
x
+
x
Δ
s
=
μ
e
-
x
s
.This system has a unique solution [2, 3]. Defining the vector
(6)
v
:
=
x
s
μ
.Note that the triple(
x
,
y
,
s
) coincides with the μ-center (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) if and only if v
=
e. For further use we introduce the scaled search directions d
x and d
s according to
(7)
d
x
:
=
v
Δ
x
x
,
d
s
:
=
v
Δ
s
s
.By using (6) and (7), after some elementary reductions, we have
(8)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
v
-
1
-
v
,
where A
¯
:
=
(
1
/
μ
)
A
V
-
1
X with V
:
=
diag
⁡
(
v
)
,
X
:
=
diag
⁡
(
x
).It is obvious that the right-hand sidev
-
1
-
v in the third equation of the system (8) equals minus the derivative of the classic barrier function as follows:
(9)
Ψ
c
(
v
)
:
=
∑
i
=
1
n
‍
ψ
c
(
v
i
)
,
v
∈
R
+
+
n
,
where
(10)
ψ
c
(
t
)
=
t
2
-
1
2
-
log
⁡
t
is the kernel function of the classic barrier function. Thus, the system (8) can be rewritten as the following system:
(11)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
-
∇
Ψ
c
(
v
)
.Corresponding to the parametric kernel function (1), we define the barrier function Ψ
(
v
)
:
R
+
+
n
→
R
+ as follows:
(12)
Ψ
(
v
)
:
=
∑
i
=
1
n
‍
ψ
(
v
i
)
.Due to the properties of the parametric kernel functionψ
(
t
), see, for example, Section 3, we can conclude that Ψ
(
v
) is a strictly convex function and attains minimal value at v
=
e and Ψ
(
e
)
=
0; that is,
(13)
∇
Ψ
(
v
)
=
0
⟺
Ψ
(
v
)
=
0
⟺
v
=
e
.Hence, the value ofΨ
(
v
) can be considered as a measure of the distance between the given iterate and the μ-center of the algorithms.The approach in this paper differs only in one detail: we replace the right-hand side of the third equation in (8) by -
∇
Ψ
(
v
). This yields the following system:
(14)
A
¯
d
x
=
0
,
A
¯
T
Δ
y
+
d
s
=
0
,
d
x
+
d
s
=
-
∇
Ψ
(
v
)
.The scaled search directionsd
x and d
s are orthogonal vectors due to the fact that d
x belongs to the null space and d
s to the row space of the matrix A
¯. From (13), one may easily verify that the right-hand side in the system (14) vanishes if and only if v
=
e. Thus we conclude that Δ
x, Δ
y, and Δ
s all vanish if and only if v
=
e, that is, if and only if x
=
x
(
μ
), y
=
y
(
μ
), and s
=
s
(
μ
). Otherwise, we will use (
Δ
x
,
Δ
y
,
Δ
s
) as the new search direction.For the analysis of the interior-point algorithm, we define the norm-based proximity measureδ
(
v
) as follows:
(15)
δ
(
v
)
:
=
1
2
∥
∇
Ψ
(
v
)
∥
.One can easily verify that(16)
d
x
=
d
s
=
0
⟺
∇
Ψ
(
v
)
=
0
⟺
δ
(
v
)
=
0
⟺
Ψ
(
v
)
=
0
⟺
v
=
e
.


## 2.3. Generic Primal-Dual Algorithm for LO

In general each kernel function gives rise to a primal-dual interior-point algorithm. Without loss of generality we assume that(
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
) is known for some positive μ. For example, due to the above assumption we may assume this for μ
=
1, with x
(
1
)
=
s
(
1
)
=
e. Then, we decrease μ to μ
:
=
(
1
-
θ
)
μ for some θ
∈
(
0,1
). We solve the scaled Newton system (14) and through (7) to get the new search direction (
Δ
x
,
Δ
y
,
Δ
s
). The new triple (
x
+
,
y
+
,
s
+
) is given by
(17)
x
+
:
=
x
+
α
Δ
x
,
y
+
:
=
y
+
α
Δ
y
,
s
+
:
=
s
+
α
Δ
s
,
where α denotes the default step size, α
∈
(
0,1
], which has to be chosen appropriately. If necessary, we repeat the procedure until we find iterates that are in the neighborhood of (
x
(
μ
)
,
y
(
μ
)
,
s
(
μ
)
). Then μ is again reduced by the factor 1
-
θ and we apply Newton’s method targeting the new μ-centers, and so on. This process is repeated until μ is small enough, say until n
μ
<
ε; at this stage we have found an ε-solution of (
P
) and (
D
). The generic form of this algorithm is shown in Algorithm 1.Algorithm 1:
Generic primal-dual interior-point algorithm for LO.
Input:
A threshold parameterτ
>
0;
an accuracy parameterε
>
0;
a fixed barrier update parameterθ
,
0
<
θ
<
1;
begin
x
:
=
e
;
s
:
=
e
;
μ
:
=
1;
while  n
μ
≥
ε  do
begin
μ
:
=
(
1
-
θ
)
μ;
while  Ψ
(
v
)
>
τ  do
begin
calculate the search direction(
Δ
x
,
Δ
y
,
Δ
s
);
determine the default step sizeα;
update(
x
,
y
,
s
)
:
=
(
x
,
y
,
s
)
+
α
(
Δ
x
,
Δ
y
,
Δ
s
).
end
end
end


## 3. New Parametric Kernel Function and Its Properties

In this section, we introduce the new parametric kernel function with a trigonometric barrier term and develop some useful properties of the new kernel function as well as the corresponding barrier function that are needed in the analysis of the algorithms.For ease of reference, we give the first three derivatives ofψ
(
t
) given by (1) with respect to t as follows:
(18)
ψ
′
(
t
)
=
t
-
1
t
+
2
λ
h
′
(
t
)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
,
(19)
ψ
′′
(
t
)
=
1
+
1
t
2
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
g
1
(
t
)
,
(20)
ψ
′′′
(
t
)
=
-
2
t
3
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
g
2
(
t
)
,
where
(21)
g
1
(
t
)
:
=
h
′′
(
t
)
tan
(
h
(
t
)
)
+
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
,
g
2
(
t
)
:
=
3
h
′
(
t
)
h
′′
(
t
)
(
3
tan
2
(
h
(
t
)
)
+
1
)
ddddddd
+
4
h
′
(
t
)
3
tan
(
h
(
t
)
)
(
3
tan
2
(
h
(
t
)
)
+
2
)
ddddddd
+
h
′′′
(
t
)
tan
(
h
(
t
)
)
,
h
′
(
t
)
=
-
5
π
(
3
t
+
2
)
2
,
h
′′
(
t
)
=
30
π
(
3
t
+
2
)
3
,
h
′′′
(
t
)
=
-
270
π
(
3
t
+
2
)
4
.One can easily verify that(22)
ψ
(
1
)
=
ψ
′
(
1
)
=
0
.This implies that the kernel functionψ
(
t
) is completely defined by its second derivative as follows:
(23)
ψ
(
t
)
=
∫
1
t
‍
∫
1
ξ
‍
ψ
′′
(
ζ
)
d
ζ
d
ξ
.In what follows, we develop some technical lemmas on the parametric kernel function.Lemma 1.
Let0
<
t
≤
2
/
3. Then
(24)
tan
(
h
(
t
)
)
-
1
3
π
t
>
0
.Proof.
Defineg
(
t
)
:
=
tan
(
h
(
t
)
)
-
1
/
3
π
t. For 0
<
t
≤
2
/
3, we have
(25)
cos
⁡
(
h
(
t
)
)
=
sin
(
π
2
-
h
(
t
)
)
<
π
2
-
h
(
t
)
.
It follows that(26)
g
′
(
t
)
=
1
cos
⁡
2
(
h
(
t
)
)
h
′
(
t
)
+
1
3
π
t
2
=
1
3
π
t
2
cos
⁡
2
(
h
(
t
)
)
(
3
π
t
2
h
′
(
t
)
+
cos
⁡
2
(
h
(
t
)
)
)
<
1
3
π
t
2
cos
⁡
2
(
h
(
t
)
)
(
3
π
t
2
h
′
(
t
)
+
(
π
2
-
h
(
t
)
)
2
)
=
-
35
π
12
(
3
t
+
2
)
2
cos
⁡
2
(
h
(
t
)
)
<
0
.
Thusg
(
t
) is monotone decreasing in (
0
,
2
/
3
], and since g
(
2
/
3
)
=
tan
(
π
/
12
)
-
1
/
2
π
≈
0.1088
>
0, this implies the lemma.Lemma 2.
Leta be a constant, and
(27)
w
(
t
,
λ
)
=
L
n
(
λ
)
t
n
+
L
n
-
1
(
λ
)
t
n
-
1
+
⋯
+
L
1
(
λ
)
t
+
L
0
(
λ
)
,
1111111111111111111111111111111111111111111
t
∈
R
.
Here L
i
(
λ
) are the functions of parameter λ
∈
R for i
=
0,1
,
…
,
n. If L
n
(
λ
)
>
0, w
(
a
,
λ
)
>
0 and (
∂
i
w
(
t
,
λ
)
/
∂
t
i
)
|
t
=
a
>
0 for i
=
1
,
…
,
n
-
1, then we have w
(
t
,
λ
)
>
0 for all t
>
a.Proof.
It is obvious that(
∂
n
w
(
t
,
λ
)
/
∂
t
n
)
=
n
!
L
n
(
λ
)
>
0, for all t
∈
R. This implies that (
∂
n
-
1
w
(
t
,
λ
)
/
∂
t
n
-
1
) is monotone increasing. Since (
∂
n
-
1
w
(
t
,
λ
)
/
∂
t
n
-
1
)
|
t
=
a
>
0, we have w
(
n
-
1
)
(
t
,
λ
)
>
0 for all t
>
a. And so on, we can conclude that w
(
t
,
λ
)
>
0 for all t
>
a. This completes the proof of the lemma.Lemma 3.
Lett
>
0. Then
(28)
ψ
′′
(
t
)
>
1
,
(29)
t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0
,
(30)
t
ψ
′′
(
t
)
-
ψ
′
(
t
)
>
0
,
(31)
ψ
′′′
(
t
)
<
0
.Proof.
Firstly, we consider two cases to prove (28).
Case  1.Assume that 0
<
t
<
1. Then we have tan
(
h
(
t
)
)
>
0. Since h
′′
(
t
)
>
0, from (19) one can see that ψ
′′
(
t
)
>
1 for all t
∈
(
0,1
), when λ
>
0.
Case  2. Assume that t
≥
1. Define
(32)
ξ
(
t
)
:
=
1
t
2
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
ddddd
×
(
h
′′
(
t
)
tan
(
h
(
t
)
)
+
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
)
.
We need to prove that when0
<
λ
≤
8
/
25
π, ξ
(
t
)
>
0 holds. Using the fact that tan
(
h
(
t
)
)
∈
(
-
3
,
0
] for all t
≥
1, we have
(33)
ξ
(
t
)
=
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
1
2
λ
t
2
(
ta
n
2
(
h
(
t
)
)
+
1
)
+
h
′′
(
t
)
tan
(
h
(
t
)
)
d
d
d
d
+
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
1
2
λ
t
2
(
ta
n
2
(
h
(
t
)
)
+
1
)
)
≥
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
1
8
λ
t
2
-
30
3
π
(
3
t
+
2
)
3
+
25
π
2
(
3
t
+
2
)
4
)
=
ta
n
2
(
h
(
t
)
)
+
1
4
t
2
(
3
t
+
2
)
4
u
1
(
t
,
λ
)
,
where
(34)
u
1
(
t
,
λ
)
:
=
(
3
t
+
2
)
4
-
λ
π
(
240
3
t
2
(
3
t
+
2
)
-
200
π
t
2
)
.
From Lemma2, by solving (
∂
i
u
1
(
t
,
λ
)
/
∂
t
i
)
|
t
=
1
>
0 for i
=
0,1
,
2,3, we can conclude that
(35)
λ
<
135
π
(
264
3
-
20
π
)
≈
0.342
π
,
which implies that ψ
′′
(
t
)
>
1 for all t
≥
1, when 0
<
λ
≤
8
/
25
π.
Secondly, we consider three cases to prove that when0
<
λ
≤
8
/
25
π, (29) holds. We have(36)
t
ψ
′′
(
t
)
+
ψ
′
(
t
)
=
2
t
+
2
k
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
(
t
h
′′
(
t
)
+
h
′
(
t
)
)
tan
(
h
(
t
)
)
d
d
d
+
t
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
)
.
Case  1. Assume that t
≥
1. Since λ
>
0, we have ψ
′
(
t
)
>
0 and ψ
′′
(
t
)
>
0; therefore t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0 holds for this case.
Case  2. Assume that 2
/
3
<
t
<
1. t
h
′′
(
t
)
+
h
′
(
t
)
=
5
π
(
9
t
2
-
4
)
/
(
3
t
+
2
)
4
>
0;  therefore t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0 also holds for this case.
Case  3. Assume that 0
<
t
≤
2
/
3. Using Lemma 1, we have
(37)
(
t
h
′′
(
t
)
+
h
′
(
t
)
)
tan
(
h
(
t
)
)
+
t
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
≥
5
π
(
9
t
2
-
4
)
(
3
t
+
2
)
4
tan
(
h
(
t
)
)
+
t
h
′
(
t
)
2
(
1
π
t
tan
(
h
(
t
)
)
+
1
)
=
tan
(
h
(
t
)
)
45
π
t
2
+
5
π
(
3
t
+
2
)
4
+
t
h
′
(
t
)
2
>
0
.
This implies that t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0 for all 0
<
t
≤
2
/
3.
From three cases above we conclude that when0
<
λ
≤
8
/
25
π, we have t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0 for all t
≥
0.
Thirdly, we consider two cases to prove that when0
<
λ
≤
8
/
25
π, (30) holds.
Case  1. Assume that 0
<
t
<
1. We have ψ
′
(
t
)
<
0 and ψ
′′
(
t
)
>
0; therefore t
ψ
′′
(
t
)
-
ψ
′
(
t
)
>
0 holds for this case.
Case  2. Assume that t
≥
1. Then using the fact that t
h
′′
(
t
)
-
h
′
(
t
)
>
0 and tan
(
h
(
t
)
)
∈
(
-
3
,
0
], we have
(38)
t
ψ
′′
(
t
)
-
ψ
′
(
t
)
=
2
t
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
(
t
h
′′
(
t
)
-
h
′
(
t
)
)
tan
(
h
(
t
)
)
d
d
d
+
t
h
′
(
t
)
2
(
3
tan
2
(
h
(
t
)
)
+
1
)
)
≥
2
t
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
-
3
t
h
′′
(
t
)
+
3
h
′
(
t
)
+
t
h
′
(
t
)
2
)
=
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
1
λ
t
(
ta
n
2
(
h
(
t
)
)
+
1
)
-
3
t
h
′′
(
t
)
dddddd
+
3
h
′
(
t
)
+
t
h
′
(
t
)
2
1
λ
t
(
ta
n
2
(
h
(
t
)
)
+
1
)
)
≥
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
1
4
λ
t
-
3
t
h
′′
(
t
)
+
3
h
′
(
t
)
+
t
h
′
(
t
)
2
)
=
(
ta
n
2
(
h
(
t
)
)
+
1
)
2
t
(
3
t
+
2
)
4
u
2
(
t
,
λ
)
,
where
(39)
u
2
(
t
,
λ
)
:

=
(
3
t
+
2
)
4
-
λ
π
(
120
3
t
2
(
3
t
+
2
)
d
d
d
d
d
d
d
+
20
3
t
(
3
t
+
2
)
2
-
100
π
t
2
)
.
From Lemma2, by solving (
∂
i
u
2
(
t
,
λ
)
/
∂
t
i
)
|
t
=
1
>
0 for i
=
0,1
,
2,3, we can conclude that
(40)
λ
<
75
π
(
133
3
-
10
π
)
≈
0.377
π
,
which implies that t
ψ
′′
(
t
)
-
ψ
′
(
t
)
>
0 for all t
≥
1, when 0
<
λ
≤
8
/
25
π.
Finally, we consider three cases to prove that (31) holds while 0
<
λ
≤
8
/
25
π. We have
(41)
ψ
′′′
(
t
)
=
-
2
t
3
+
2
λ
(
tan
2
(
h
(
t
)
)
+
1
)
g
2
(
t
)
=
-
2
(
tan
2
(
h
(
t
)
)
+
1
)
×
(
1
t
3
(
ta
n
2
(
h
(
t
)
)
+
1
)
-
λ
g
2
(
t
)
)
.
Define(42)
ζ
(
t
)
:
=
1
t
3
(
ta
n
2
(
h
(
t
)
)
+
1
)
-
λ
g
2
(
t
)
.
Case  1. Assume that 0
<
t
≤
1. In this situation, we have tan
(
h
(
t
)
)
>
0, h
′
(
t
)
<
0, h
′′′
(
t
)
<
0, and h
′
(
t
)
h
′′
(
t
)
<
0, from which we know that g
2
(
t
)
<
0. Therefore ψ
′′′
(
t
)
<
0 holds for this case.
Case  2. Assume that 1
<
t
≤
6. Due to the fact that -
1
≤
tan
(
h
(
t
)
)
<
0, 1
/
(
1
+
ta
n
2
(
h
(
t
)
)
)
≥
1
/
2, and tan
(
h
(
t
)
)
(
3
tan
2
(
h
(
t
)
)
+
2
)
≥
-
5 for all 1
<
t
≤
6, we have
(43)
ζ
(
t
)
≥
1
2
t
3
+
λ
(
-
3
h
′
(
t
)
h
′′
(
t
)
+
20
h
′
(
t
)
3
+
h
′′′
(
t
)
)
=
1
2
t
3
+
λ
(
450
π
2
(
3
t
+
2
)
5
-
2500
π
3
(
3
t
+
2
)
6
+
270
π
(
3
t
+
2
)
4
)
=
1
2
t
3
(
3
t
+
2
)
6
u
3
(
t
,
λ
)
,
where
(44)
u
3
(
t
,
λ
)
:

=
(
3
t
+
2
)
6
-
λ
π
×
(
5000
π
2
t
3
+
540
t
3
(
3
t
+
2
)
2
d
d
d
d
-
900
π
t
3
(
3
t
+
2
)
)
.
From Lemma2, by solving (
∂
i
u
3
(
t
,
λ
)
/
∂
t
i
)
|
t
=
1
>
0 for i
=
0,1
,
…
,
5, we can conclude that
(45)
λ
<
125
π
(
40
π
2
+
108
-
36
π
)
≈
0.321
π
,
which implies that ψ
′′′
(
t
)
<
0 for all 0
<
t
≤
6, when 0
<
λ
≤
8
/
25
π.
Case  3. Assume that t
>
6. Due to the fact that -
3
<
tan
(
h
(
t
)
)
<
-
1, 1
/
(
1
+
ta
n
2
(
h
(
t
)
)
)
>
1
/
4, and tan
(
h
(
t
)
)
(
3
tan
2
(
h
(
t
)
+
2
)
)
>
-
44
3 for all t
>
6, we have
(46)
ζ
(
t
)
≥
1
4
t
3
-
λ
(
-
44
3
h
′
(
t
)
3
-
3
h
′′′
(
t
)
12
h
′
(
t
)
h
′′
(
t
)
d
d
d
d
d
d
d
d
-
44
3
h
′
(
t
)
3
-
3
h
′′′
(
t
)
)
=
1
4
t
3
-
λ
π
(
5500
3
π
2
(
3
t
+
2
)
6
dddddddd
+
270
3
(
3
t
+
2
)
4
-
1800
π
(
3
t
+
2
)
5
)
=
1
4
t
3
(
3
t
+
2
)
6
u
4
(
t
,
λ
)
,
where
(47)
u
4
(
t
,
λ
)
:
=
(
3
t
+
2
)
6
-
λ
π
d
d
d
d
d
d
d
d
×
(
22000
3
π
2
t
3
+
1080
3
t
3
(
3
t
+
2
)
2
d
d
d
d
d
d
d
d
d
d
d
d
-
7200
π
t
3
(
3
t
+
2
)
)
.
From Lemma2, by solving (
∂
i
u
4
(
t
,
λ
)
/
∂
t
i
)
|
t
=
6
>
0 for i
=
0,1
,
…
,
5, we can conclude that
(48)
λ
<
4000
π
(
297
3
π
2
+
5832
3
-
1944
π
)
≈
0.441
π
,
this implies that when 0
<
λ
≤
8
/
25
π, we have ψ
′′′
(
t
)
<
0 for all t
≥
6.
From the above discussions, the proof of the lemma is completed.The property described below is exponential convexity, which has been proven to be very useful in the analysis of primal-dual interior-point algorithms based on the eligible kernel functions [2, 3].Lemma 4.
Lett
1
,
t
2
≥
0. Then
(49)
ψ
(
t
1
t
2
)
≤
1
2
(
ψ
(
t
1
)
+
ψ
(
t
2
)
)
.Proof.
The result of the lemma follows immediately from Lemma  1 in [2], which states that the above inequality holds if and only if t
ψ
′′
(
t
)
+
ψ
′
(
t
)
>
0 for all t
>
0. Hence, from (29) in Lemma 3, the proof of the lemma is completed.From (28) of Lemma 3 (i.e., ψ
′′
(
t
)
>
1), we say that ψ
(
t
) is strongly convex. The following lemma provides an important consequence of this property. These results can be directly obtained from the corresponding results in [3].Lemma 5.
Lett
>
0. Then
(50)
1
2
(
t
-
1
)
2
≤
ψ
(
t
)
≤
1
2
ψ
′
(
t
)
2
.As the consequences of Lemma5, one has the following two corollaries.Corollary 6.
LetΨ
(
v
)
≥
1. Then
(51)
δ
(
v
)
≥
Ψ
(
v
)
2
.Corollary 7.
LetΨ
(
v
)
≥
1. Then
(52)
∥
v
∥
≤
n
+
2
Ψ
(
v
)
≤
n
+
2
δ
(
v
)
.Lemma 8.
Letβ
≥
1. Then
(53)
ψ
(
β
t
)
≤
ψ
(
t
)
+
1
2
(
β
2
-
1
)
t
2
.Proof.
Let(54)
w
(
t
)
:
=
-
log
⁡
(
t
)
+
λ
tan
2
(
h
(
t
)
)
,
0
<
λ
≤
8
25
π
.
Then(55)
ψ
(
t
)
=
1
2
(
t
2
-
1
)
+
w
(
t
)
,
ψ
(
β
t
)
-
ψ
(
t
)
=
1
2
(
β
2
-
1
)
t
2
+
w
(
β
t
)
-
w
(
t
)
.
Asβ
≥
1, to prove the lemma, it is sufficient to show that the function w
(
t
) is a decreasing function. For this purpose, we have
(56)
w
′
(
t
)
=
-
1
t
+
2
λ
h
′
(
t
)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
=
-
1
t
-
10
λ
π
(
3
t
+
2
)
2
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
.
If0
<
t
≤
1, then tan
(
h
(
t
)
)
≥
0, so w
′
(
t
)
<
0.
Ift
>
1, then -
3
<
tan
(
h
(
t
)
)
<
0. Using 0
<
λ
≤
8
/
25
π, we have
(57)
w
′
(
t
)
<
-
1
t
+
λ
40
3
π
(
3
t
+
2
)
2
≤
-
1
t
+
64
3
5
(
3
t
+
2
)
2
=
-
5
(
3
t
+
2
)
2
+
64
3
t
5
t
(
3
t
+
2
)
2
<
-
9
(
5
t
-
1
)
(
t
-
1
)
-
11
5
t
(
3
t
+
2
)
2
<
0
.
This implies the result of the lemma.Theorem 9.
Let0
<
θ
<
1 and v
+
=
v
/
1
-
θ. Then
(58)
Ψ
(
v
+
)
≤
Ψ
(
v
)
+
θ
2
(
1
-
θ
)
(
2
Ψ
(
v
)
+
2
2
n
Ψ
(
v
)
+
n
)
.Proof.
It follows from Lemma8 with β
=
1
/
1
-
θ that
(59)
Ψ
(
β
v
)
≤
Ψ
(
v
)
+
1
2
∑
i
=
1
n
‍
(
β
2
-
1
)
v
i
2
=
Ψ
(
v
)
+
θ
∥
v
∥
2
2
(
1
-
θ
)
.
Thus, we have, by Corollary7,
(60)
Ψ
(
v
+
)
≤
Ψ
(
v
)
+
θ
2
(
1
-
θ
)
(
2
Ψ
(
v
)
+
2
2
n
Ψ
(
v
)
+
n
)
.
The proof of the theorem is completed.


## 4. Analysis and Complexity of the Algorithms

In this section, we first choose a default step size. Then, we derive an upper bound for the decrease of the barrier function during an inner iteration. Finally, the iteration bounds for large- and small-update methods are established.


### 4.1. Computation of the Default Step Size

In each inner iteration, we first compute the search direction(
d
x
,
Δ
y
,
d
s
) from the system (14). Then through (7), we obtain the search direction (
Δ
x
,
Δ
y
,
Δ
s
). Note that during an inner iteration the parameter μ is fixed. Hence, after the step the new v-vector is given by
(61)
v
+
=
x
+
s
+
μ
.It follows from (17) that
(62)
x
+
=
x
(
e
+
α
Δ
x
x
)
=
x
v
(
v
+
α
d
x
)
,
(63)
s
+
=
s
(
e
+
α
Δ
s
s
)
=
s
v
(
v
+
α
d
s
)
.Also usingx
s
=
μ
v
2, we obtain
(64)
v
+
=
(
v
+
α
d
x
)
(
v
+
α
d
s
)
.We consider the decrease inΨ as a function of α and define
(65)
f
(
α
)
:
=
Ψ
(
v
+
)
-
Ψ
(
v
)
.However, working withf
(
α
) may not be easy because in general f
(
α
) is not convex. Thus, we are searching for the convex function f
1
(
α
) that is an upper bound of f
(
α
) and whose derivatives are easier to calculate than those of f
(
α
).Lemma4 implies that
(66)
Ψ
(
v
+
)
=
Ψ
(
(
v
+
α
d
x
)
(
v
+
α
d
s
)
)
≤
1
2
(
Ψ
(
v
+
α
d
x
)
+
Ψ
(
v
+
α
d
s
)
)
.Let(67)
f
1
(
α
)
:
=
1
2
(
Ψ
(
v
+
α
d
x
)
+
Ψ
(
v
+
α
d
s
)
)
-
Ψ
(
v
)
.This makes clear thatf
1
(
α
) is an upper bound of f
(
α
). Furthermore, we can easily verify that f
(
0
)
=
f
1
(
0
)
=
0.Taking the derivative with respect toα, we have
(68)
f
1
′
(
α
)
=
1
2
∑
i
=
1
n
‍
(
ψ
′
(
v
i
+
α
(
d
x
)
i
)
(
d
x
)
i
+
ψ
′
(
v
i
+
α
(
d
s
)
i
)
(
d
s
)
i
)
.This gives, also using the third expression of system (14),
(69)
f
1
′
(
0
)
=
1
2
∇
Ψ
(
v
)
T
(
d
x
+
d
s
)
=
-
1
2
∇
Ψ
(
v
)
T
∇
Ψ
(
v
)
=
-
2
δ
(
v
)
2
.Differentiating once again, we get(70)
f
1
′′
(
α
)
=
1
2
∑
i
=
1
n
(
ψ
′′
(
v
i
+
α
(
d
x
)
i
)
(
d
x
)
i
2
ddddd
+
ψ
′′
(
v
i
+
α
(
d
s
)
i
)
(
d
s
)
i
2
)
.Below we use the shorthand notation:δ
:
=
δ
(
v
). The following lemma provides an upper bound of f
1
′′
(
α
), which can be found in Lemma  4.1 in [3].Lemma 10.
One hasf
1
′′
(
α
)
≤
2
δ
2
ψ
′′
(
v
min
⁡
-
2
α
δ
).Following the strategy considered in [3], we briefly recall how to choose the default step size. Suppose that the step size α satisfies
(71)
-
ψ
′
(
v
min
⁡
-
2
α
δ
)
+
ψ
′
(
v
min
⁡
)
≤
2
δ
.Thenf
1
(
α
)
≤
0. The largest possible value of the step size of α satisfying (71) is given by
(72)
α
-
:
=
1
2
δ
(
ρ
(
δ
)
-
ρ
(
2
δ
)
)
,
where ρ
(
s
)
:
[
0
,
∞
)
→
(
0,1
] is the inverse function of -
(
1
/
2
)
ψ
′
(
t
) for t
∈
(
0,1
]. Furthermore, we can conclude that
(73)
1
ψ
′′
(
ρ
(
2
δ
)
)
≤
α
-
≤
1
ψ
′′
(
ρ
(
δ
)
)
.Sinceρ
(
s
) is the inverse function of -
(
1
/
2
)
ψ
′
(
t
), one has
(74)
-
(
t
-
1
t
+
2
λ
h
′
(
t
)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
)
=
2
s
.This implies(75)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
=
-
1
2
λ
h
′
(
t
)
(
2
s
+
t
-
1
t
)
=
(
3
t
+
2
)
2
10
λ
π
(
2
s
+
t
-
1
t
)
≤
5
s
λ
π
,
for t
∈
(
0,1
]. Hence, putting t
=
ρ
(
2
δ
), we get 4
δ
=
-
ψ
′
(
t
). Thus one has
(76)
tan
3
(
h
(
t
)
)
≤
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
≤
10
δ
λ
π
⟹
tan
(
h
(
t
)
)
≤
(
10
λ
π
)
1
/
3
δ
1
/
3
.From Lemma1, it yields
(77)
tan
(
h
(
t
)
)
-
1
3
π
t
>
0
,
∀
0
<
t
≤
2
3
,
which implies that
(78)
1
+
tan
(
h
(
t
)
)
>
1
3
π
t
,
∀
0
<
t
≤
1
.It also means that(79)
1
t
<
3
π
(
1
+
tan
(
h
(
t
)
)
)
,
∀
0
<
t
≤
1
.Sinceh
′′
(
t
)
=
30
π
/
(
3
t
+
2
)
3
≤
15
π
/
4 and h
′
(
t
)
2
=
25
π
2
/
(
3
t
+
2
)
4
≤
25
π
2
/
16 for all 0
<
t
≤
1, one has
(80)
α
-
=
1
ψ
′′
(
t
)
=
1
×
(
1
+
1
t
2
+
2
λ
(
ta
n
2
(
h
(
t
)
)
+
1
)
d
d
d
d
×
(
h
′′
(
t
)
tan
(
h
(
t
)
)
+
h
′
(
t
)
2
(
3
ta
n
2
(
h
(
t
)
)
+
1
)
)
1
+
1
t
2
+
2
λ

)
-
1
=
1
×
(
1

+

1
t
2
+
2
λ
(
h
′′
(
t
)
tan
(
h
(
t
)
)
(
ta
n
2
(
h
(
t
)
)

+

1
)
ddddddd
dddddddd
d

+

h
′
(
t
)
2
(
3
ta
n
2
(
h
(
t
)
)
(
ta
n
2
(
h
(
t
)
)

+

1
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d

+

(
ta
n
2
(
h
(
t
)
)

+

1
)
)
)
1
+
1
t
2
+
2
λ

)
-
1
≥
1
×
(
1
+
9
π
2
(
1
+
(
10
δ
λ
π
)
1
/
3
)
2
dddddd
+
2
λ
(
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
h
′′
(
t
)
10
δ
λ
π
+
h
′
(
t
)
2
d
d
d
d
d
d
d
d
d
d
×
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
≥
1
×
(
1
+
9
π
2
(
1
+
(
10
δ
λ
π
)
1
/
3
)
2
dddddd
+
2
λ
(
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
15
π
4
10
δ
λ
π

+

25
π
2
16
(
1

+

(
10
λ
π
)
2
/
3
δ
2
/
3
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d

+

3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
.Therefore, using Corollary6 (i.e., 2
δ
≥
Ψ
(
v
)
≥
1), one has
(81)
α
-
≥
1
×
(
(
2
δ
)
4
/
3
+
9
π
2
(
(
2
δ
)
2
/
3
+
(
10
δ
λ
π
)
1
/
3
(
2
δ
)
1
/
3
)
2
ddddddd
+
2
λ
(
75
δ
2
λ
(
2
δ
)
1
/
3
+
25
π
2
16
d
d
d
d
d
d
d
d
d
d
d
d
×
(
(
2
δ
)
4
/
3
+
(
10
λ
π
)
2
/
3
δ
2
/
3
(
2
δ
)
2
/
3
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
.Define(82)
C
:
=
2
4
/
3
+
9
π
2
(
2
2
/
3
+
(
20
λ
π
)
1
/
3
)
2
ddd
+
75
2
3
+
25
λ
π
2
8
(
2
4
/
3
+
(
20
λ
π
)
2
/
3
+
3
(
10
λ
π
)
4
/
3
)
.Then, we have(83)
α
-
≥
1
C
δ
4
/
3
.In the sequel, we use(84)
α
~
:
=
1
C
δ
4
/
3
as the default step size, which essentially depends only on the norm δ and on the constant C.


### 4.2. Decrease of the Barrier Function during an Inner Iteration

In what follows, we will show that the barrier functionΨ
(
v
) in each inner iteration with the default step size α
~, as defined by (84), is decreasing. For this, we need the following technical result.Lemma 11 (Lemma 12 in [2]).
Leth
(
t
) be a twice differentiable convex function with h
(
0
)
=
0, h
′
(
0
)
<
0 and let h
(
t
) attain its (global) minimum at t
*
>
0. If h
′′
(
t
) is increasing for t
∈
[
0
,
t
*
], then
(85)
h
(
t
)
≤
t
h
′
(
0
)
2
,
0
≤
t
≤
t
*
.As a consequence of Lemma11 and the fact that f
(
α
)
≤
f
1
(
α
), which is a twice differentiable convex function with f
1
(
0
)
=
0 and f
1
′
(
0
)
=
-
2
δ
2
<
0, we can easily prove the following lemma.Lemma 12.
Let the step sizeα be such that α
≤
α
~. Then f
(
α
)
≤
-
α
δ
2.The following theorem shows that the default step size (84) yields a sufficient decrease of the barrier function during each inner iteration.Lemma 13.
Letα
~ be the default step size as given by (84). Then
(86)
f
(
α
~
)
≤
-
(
2
3
C
)
-
1
Ψ
(
v
)
1
/
3
.Proof.
From Lemma12, (84), and Corollary 6, we have
(87)
f
(
α
~
)
≤
-
α
~
δ
2
≤
-
C
-
1
δ
2
/
3
≤
-
(
2
3
C
)
-
1
Ψ
(
v
)
1
/
3
.
This completes the proof of the theorem.


### 4.3. Iteration Bounds for Large- and Small-Update Methods

From Theorem9, after updating the parameter μ to (
1
-
θ
)
μ with 0
<
θ
<
1, we have
(88)
Ψ
(
v
+
)
≤
Ψ
(
v
)
+
θ
2
(
1
-
θ
)
(
2
Ψ
(
v
)
+
2
2
n
Ψ
(
v
)
+
n
)
.At the start of an outer iteration and just before updating the parameterμ, we have Ψ
(
v
)
≤
τ. Due to (88), the value of Ψ
(
v
) exceeds the threshold τ after updating μ. Therefore, we need to count how many inner iterations are required to return to the situation where Ψ
(
v
)
≤
τ. We denote the value of Ψ
(
v
) after the μ-update as Ψ
0 and the subsequent values in the same outer iteration are denoted as Ψ
k, k
=
1,2
,
…
,
K, where K denotes the total number of inner iterations in the outer iteration. Hence, we have
(89)
Ψ
0
≤
τ
+
θ
2
(
1
-
θ
)
(
2
τ
+
2
2
n
τ
+
n
)
.According to a decrease off
(
α
~
) in Lemma 13, we have
(90)
Ψ
k
+
1
≤
Ψ
k
-
β
(
Ψ
k
)
1
-
γ
,
k
=
0,1
,
…
,
K
-
1
,
where β
=
(
2
3
C
)
-
1 and γ
=
2
/
3.Lemma 14 (Lemma 14 in [2]).
Lett
0
,
t
1
,
…
,
t
K be a sequence of positive numbers such that
(91)
t
k
+
1
≤
t
k
-
β
t
k
1
-
γ
,
k
=
0,1
,
…
,
K
-
1
,
where β
>
0 and 0
<
γ
≤
1. Then K
≤
⌈
t
0
γ
/
β
γ
⌉.The following lemma provides an estimate for the number of inner iterations between two successive barrier parameter updates, in terms ofΨ
0 and the constant C.Lemma 15.
One has(92)
K
≤
3
2
3
C
2
(
Ψ
0
)
2
/
3
.Proof.
Using (90) and also applying Lemma 14, the result of the lemma follows.The number of outer iterations is bounded above by(
1
/
θ
)
log
⁡
(
n
/
ε
) (cf., [1, Π.17, page 116]). By multiplying the number of outer iterations and the number of inner iterations, we get an upper bound for the total number of iterations, namely,
(93)
3
2
3
C
2
θ
(
τ
+
θ
2
(
1
-
θ
)
(
2
τ
+
2
2
n
τ
+
n
)
)
2
/
3
log
⁡
n
ε
.Then, the iteration bound for large-update methods is established in the following theorem.Theorem 16.
For large-update methods, one takes forθ a constant (independent on n), namely, θ
=
Θ
(
1
) and τ
=
O
(
n
). The iteration bound then becomes
(94)
O
(
n
2
/
3
log
⁡
n
ε
)
,
which improves the classical iteration bound with a factor n
1
/
3. Similar to the analysis in [10], the iteration complexity for the small-update methods is straight and we leave it for the interested readers.Theorem 17.
For small-update methods, one takesθ
=
Θ
(
1
/
n
) and τ
=
O
(
1
). The iteration bound then becomes
(95)
O
(
n
log
⁡
n
ε
)
,
which matches the currently best known iteration bound for small-update methods.


## 4.1. Computation of the Default Step Size

In each inner iteration, we first compute the search direction(
d
x
,
Δ
y
,
d
s
) from the system (14). Then through (7), we obtain the search direction (
Δ
x
,
Δ
y
,
Δ
s
). Note that during an inner iteration the parameter μ is fixed. Hence, after the step the new v-vector is given by
(61)
v
+
=
x
+
s
+
μ
.It follows from (17) that
(62)
x
+
=
x
(
e
+
α
Δ
x
x
)
=
x
v
(
v
+
α
d
x
)
,
(63)
s
+
=
s
(
e
+
α
Δ
s
s
)
=
s
v
(
v
+
α
d
s
)
.Also usingx
s
=
μ
v
2, we obtain
(64)
v
+
=
(
v
+
α
d
x
)
(
v
+
α
d
s
)
.We consider the decrease inΨ as a function of α and define
(65)
f
(
α
)
:
=
Ψ
(
v
+
)
-
Ψ
(
v
)
.However, working withf
(
α
) may not be easy because in general f
(
α
) is not convex. Thus, we are searching for the convex function f
1
(
α
) that is an upper bound of f
(
α
) and whose derivatives are easier to calculate than those of f
(
α
).Lemma4 implies that
(66)
Ψ
(
v
+
)
=
Ψ
(
(
v
+
α
d
x
)
(
v
+
α
d
s
)
)
≤
1
2
(
Ψ
(
v
+
α
d
x
)
+
Ψ
(
v
+
α
d
s
)
)
.Let(67)
f
1
(
α
)
:
=
1
2
(
Ψ
(
v
+
α
d
x
)
+
Ψ
(
v
+
α
d
s
)
)
-
Ψ
(
v
)
.This makes clear thatf
1
(
α
) is an upper bound of f
(
α
). Furthermore, we can easily verify that f
(
0
)
=
f
1
(
0
)
=
0.Taking the derivative with respect toα, we have
(68)
f
1
′
(
α
)
=
1
2
∑
i
=
1
n
‍
(
ψ
′
(
v
i
+
α
(
d
x
)
i
)
(
d
x
)
i
+
ψ
′
(
v
i
+
α
(
d
s
)
i
)
(
d
s
)
i
)
.This gives, also using the third expression of system (14),
(69)
f
1
′
(
0
)
=
1
2
∇
Ψ
(
v
)
T
(
d
x
+
d
s
)
=
-
1
2
∇
Ψ
(
v
)
T
∇
Ψ
(
v
)
=
-
2
δ
(
v
)
2
.Differentiating once again, we get(70)
f
1
′′
(
α
)
=
1
2
∑
i
=
1
n
(
ψ
′′
(
v
i
+
α
(
d
x
)
i
)
(
d
x
)
i
2
ddddd
+
ψ
′′
(
v
i
+
α
(
d
s
)
i
)
(
d
s
)
i
2
)
.Below we use the shorthand notation:δ
:
=
δ
(
v
). The following lemma provides an upper bound of f
1
′′
(
α
), which can be found in Lemma  4.1 in [3].Lemma 10.
One hasf
1
′′
(
α
)
≤
2
δ
2
ψ
′′
(
v
min
⁡
-
2
α
δ
).Following the strategy considered in [3], we briefly recall how to choose the default step size. Suppose that the step size α satisfies
(71)
-
ψ
′
(
v
min
⁡
-
2
α
δ
)
+
ψ
′
(
v
min
⁡
)
≤
2
δ
.Thenf
1
(
α
)
≤
0. The largest possible value of the step size of α satisfying (71) is given by
(72)
α
-
:
=
1
2
δ
(
ρ
(
δ
)
-
ρ
(
2
δ
)
)
,
where ρ
(
s
)
:
[
0
,
∞
)
→
(
0,1
] is the inverse function of -
(
1
/
2
)
ψ
′
(
t
) for t
∈
(
0,1
]. Furthermore, we can conclude that
(73)
1
ψ
′′
(
ρ
(
2
δ
)
)
≤
α
-
≤
1
ψ
′′
(
ρ
(
δ
)
)
.Sinceρ
(
s
) is the inverse function of -
(
1
/
2
)
ψ
′
(
t
), one has
(74)
-
(
t
-
1
t
+
2
λ
h
′
(
t
)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
)
=
2
s
.This implies(75)
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
=
-
1
2
λ
h
′
(
t
)
(
2
s
+
t
-
1
t
)
=
(
3
t
+
2
)
2
10
λ
π
(
2
s
+
t
-
1
t
)
≤
5
s
λ
π
,
for t
∈
(
0,1
]. Hence, putting t
=
ρ
(
2
δ
), we get 4
δ
=
-
ψ
′
(
t
). Thus one has
(76)
tan
3
(
h
(
t
)
)
≤
tan
(
h
(
t
)
)
(
tan
2
(
h
(
t
)
)
+
1
)
≤
10
δ
λ
π
⟹
tan
(
h
(
t
)
)
≤
(
10
λ
π
)
1
/
3
δ
1
/
3
.From Lemma1, it yields
(77)
tan
(
h
(
t
)
)
-
1
3
π
t
>
0
,
∀
0
<
t
≤
2
3
,
which implies that
(78)
1
+
tan
(
h
(
t
)
)
>
1
3
π
t
,
∀
0
<
t
≤
1
.It also means that(79)
1
t
<
3
π
(
1
+
tan
(
h
(
t
)
)
)
,
∀
0
<
t
≤
1
.Sinceh
′′
(
t
)
=
30
π
/
(
3
t
+
2
)
3
≤
15
π
/
4 and h
′
(
t
)
2
=
25
π
2
/
(
3
t
+
2
)
4
≤
25
π
2
/
16 for all 0
<
t
≤
1, one has
(80)
α
-
=
1
ψ
′′
(
t
)
=
1
×
(
1
+
1
t
2
+
2
λ
(
ta
n
2
(
h
(
t
)
)
+
1
)
d
d
d
d
×
(
h
′′
(
t
)
tan
(
h
(
t
)
)
+
h
′
(
t
)
2
(
3
ta
n
2
(
h
(
t
)
)
+
1
)
)
1
+
1
t
2
+
2
λ

)
-
1
=
1
×
(
1

+

1
t
2
+
2
λ
(
h
′′
(
t
)
tan
(
h
(
t
)
)
(
ta
n
2
(
h
(
t
)
)

+

1
)
ddddddd
dddddddd
d

+

h
′
(
t
)
2
(
3
ta
n
2
(
h
(
t
)
)
(
ta
n
2
(
h
(
t
)
)

+

1
)
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d

+

(
ta
n
2
(
h
(
t
)
)

+

1
)
)
)
1
+
1
t
2
+
2
λ

)
-
1
≥
1
×
(
1
+
9
π
2
(
1
+
(
10
δ
λ
π
)
1
/
3
)
2
dddddd
+
2
λ
(
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
h
′′
(
t
)
10
δ
λ
π
+
h
′
(
t
)
2
d
d
d
d
d
d
d
d
d
d
×
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
≥
1
×
(
1
+
9
π
2
(
1
+
(
10
δ
λ
π
)
1
/
3
)
2
dddddd
+
2
λ
(
(
1
+
(
10
λ
π
)
2
/
3
δ
2
/
3
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
15
π
4
10
δ
λ
π

+

25
π
2
16
(
1

+

(
10
λ
π
)
2
/
3
δ
2
/
3
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d

+

3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
.Therefore, using Corollary6 (i.e., 2
δ
≥
Ψ
(
v
)
≥
1), one has
(81)
α
-
≥
1
×
(
(
2
δ
)
4
/
3
+
9
π
2
(
(
2
δ
)
2
/
3
+
(
10
δ
λ
π
)
1
/
3
(
2
δ
)
1
/
3
)
2
ddddddd
+
2
λ
(
75
δ
2
λ
(
2
δ
)
1
/
3
+
25
π
2
16
d
d
d
d
d
d
d
d
d
d
d
d
×
(
(
2
δ
)
4
/
3
+
(
10
λ
π
)
2
/
3
δ
2
/
3
(
2
δ
)
2
/
3
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
+
3
(
10
λ
π
)
4
/
3
δ
4
/
3
)
)
)
-
1
.Define(82)
C
:
=
2
4
/
3
+
9
π
2
(
2
2
/
3
+
(
20
λ
π
)
1
/
3
)
2
ddd
+
75
2
3
+
25
λ
π
2
8
(
2
4
/
3
+
(
20
λ
π
)
2
/
3
+
3
(
10
λ
π
)
4
/
3
)
.Then, we have(83)
α
-
≥
1
C
δ
4
/
3
.In the sequel, we use(84)
α
~
:
=
1
C
δ
4
/
3
as the default step size, which essentially depends only on the norm δ and on the constant C.


## 4.2. Decrease of the Barrier Function during an Inner Iteration

In what follows, we will show that the barrier functionΨ
(
v
) in each inner iteration with the default step size α
~, as defined by (84), is decreasing. For this, we need the following technical result.Lemma 11 (Lemma 12 in [2]).
Leth
(
t
) be a twice differentiable convex function with h
(
0
)
=
0, h
′
(
0
)
<
0 and let h
(
t
) attain its (global) minimum at t
*
>
0. If h
′′
(
t
) is increasing for t
∈
[
0
,
t
*
], then
(85)
h
(
t
)
≤
t
h
′
(
0
)
2
,
0
≤
t
≤
t
*
.As a consequence of Lemma11 and the fact that f
(
α
)
≤
f
1
(
α
), which is a twice differentiable convex function with f
1
(
0
)
=
0 and f
1
′
(
0
)
=
-
2
δ
2
<
0, we can easily prove the following lemma.Lemma 12.
Let the step sizeα be such that α
≤
α
~. Then f
(
α
)
≤
-
α
δ
2.The following theorem shows that the default step size (84) yields a sufficient decrease of the barrier function during each inner iteration.Lemma 13.
Letα
~ be the default step size as given by (84). Then
(86)
f
(
α
~
)
≤
-
(
2
3
C
)
-
1
Ψ
(
v
)
1
/
3
.Proof.
From Lemma12, (84), and Corollary 6, we have
(87)
f
(
α
~
)
≤
-
α
~
δ
2
≤
-
C
-
1
δ
2
/
3
≤
-
(
2
3
C
)
-
1
Ψ
(
v
)
1
/
3
.
This completes the proof of the theorem.


## 4.3. Iteration Bounds for Large- and Small-Update Methods

From Theorem9, after updating the parameter μ to (
1
-
θ
)
μ with 0
<
θ
<
1, we have
(88)
Ψ
(
v
+
)
≤
Ψ
(
v
)
+
θ
2
(
1
-
θ
)
(
2
Ψ
(
v
)
+
2
2
n
Ψ
(
v
)
+
n
)
.At the start of an outer iteration and just before updating the parameterμ, we have Ψ
(
v
)
≤
τ. Due to (88), the value of Ψ
(
v
) exceeds the threshold τ after updating μ. Therefore, we need to count how many inner iterations are required to return to the situation where Ψ
(
v
)
≤
τ. We denote the value of Ψ
(
v
) after the μ-update as Ψ
0 and the subsequent values in the same outer iteration are denoted as Ψ
k, k
=
1,2
,
…
,
K, where K denotes the total number of inner iterations in the outer iteration. Hence, we have
(89)
Ψ
0
≤
τ
+
θ
2
(
1
-
θ
)
(
2
τ
+
2
2
n
τ
+
n
)
.According to a decrease off
(
α
~
) in Lemma 13, we have
(90)
Ψ
k
+
1
≤
Ψ
k
-
β
(
Ψ
k
)
1
-
γ
,
k
=
0,1
,
…
,
K
-
1
,
where β
=
(
2
3
C
)
-
1 and γ
=
2
/
3.Lemma 14 (Lemma 14 in [2]).
Lett
0
,
t
1
,
…
,
t
K be a sequence of positive numbers such that
(91)
t
k
+
1
≤
t
k
-
β
t
k
1
-
γ
,
k
=
0,1
,
…
,
K
-
1
,
where β
>
0 and 0
<
γ
≤
1. Then K
≤
⌈
t
0
γ
/
β
γ
⌉.The following lemma provides an estimate for the number of inner iterations between two successive barrier parameter updates, in terms ofΨ
0 and the constant C.Lemma 15.
One has(92)
K
≤
3
2
3
C
2
(
Ψ
0
)
2
/
3
.Proof.
Using (90) and also applying Lemma 14, the result of the lemma follows.The number of outer iterations is bounded above by(
1
/
θ
)
log
⁡
(
n
/
ε
) (cf., [1, Π.17, page 116]). By multiplying the number of outer iterations and the number of inner iterations, we get an upper bound for the total number of iterations, namely,
(93)
3
2
3
C
2
θ
(
τ
+
θ
2
(
1
-
θ
)
(
2
τ
+
2
2
n
τ
+
n
)
)
2
/
3
log
⁡
n
ε
.Then, the iteration bound for large-update methods is established in the following theorem.Theorem 16.
For large-update methods, one takes forθ a constant (independent on n), namely, θ
=
Θ
(
1
) and τ
=
O
(
n
). The iteration bound then becomes
(94)
O
(
n
2
/
3
log
⁡
n
ε
)
,
which improves the classical iteration bound with a factor n
1
/
3. Similar to the analysis in [10], the iteration complexity for the small-update methods is straight and we leave it for the interested readers.Theorem 17.
For small-update methods, one takesθ
=
Θ
(
1
/
n
) and τ
=
O
(
1
). The iteration bound then becomes
(95)
O
(
n
log
⁡
n
ε
)
,
which matches the currently best known iteration bound for small-update methods.


## 5. Conclusions and Remarks

In this paper, we have proposed a class of primal-dual IPMs for LO based on a new parametric kernel function, which is a combination of the classic kernel function and a trigonometric barrier term. The worst case iteration bounds for large- and small-update methods are established, namely,O
(
n
2
/
3
log
⁡
(
n
/
ε
)
) and O
(
n
log
⁡
(
n
/
ε
)
), respectively. For both versions of the kernel-based IPMs, the obtained iteration bounds match the currently best known iteration bound for such methods based on the trigonometric kernel functions.The paper improved the complexity results for large-update methods obtained by El Ghami et al. [6] and generalized the results presented recently by Peyghami et al. [7]. Furthermore, the analysis deviates significantly from the analysis presented in previous papers [6, 7].Some interesting topics for further research remain. The extension to second-order cone optimization (SOCO), semidefinite optimization (SDO), and symmetric cone optimization (SCO) deserves to be investigated. Furthermore, the numerical results may help us compare the behavior of the proposed algorithms with other existing IPMs.



---

*Source: 710158-2014-06-15.xml*