# A New Noninterior Continuation Method for Solving a System of Equalities and Inequalities

Authors: Jianguang Zhu; Binbin Hao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

By using slack variables and minimum function, we first reformulate the system of equalities and inequalities as a system of nonsmooth equations, and, using smoothing technique, we construct the smooth operator. A new noninterior continuation method is proposed to solve the system of smooth equations. It shows that any accumulation point of the iteration sequence generated by our algorithm is a solution of the system of equalities and inequalities. Some numerical experiments show the
feasibility and efficiency of the algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the following system of equalities and inequalities:(1)
f
I
(
x
)
≤
0
,
f
E
(
x
)
=
0
,
where I
=
{
1
,
…
,
m
} and E
=
{
m
+
1
,
…
,
n
}. Define f
(
x
)
=
[
f
1
(
x
)
,
…
,
f
n
(
x
)
] with f
i
:
ℜ
n
→
ℜ, for any i
∈
{
1
,
…
,
n
}. Throughout this paper, we assume that f is continuously differentiable.Problems taking the form (1) have been studied extensively due to its various applications in data analysis, set separation problems, computer aided design problems, and image reconstructions.Recently, a class of popular numerical methods, namely, the so-called noninterior continuation methods, has been studied extensively for complementarity, variational inequality, and mathematical programming problems; see, for example, [1–7]. However, as we observe, there are few noninterior continuation methods available for the system of equalities and inequalities given by (1).In this paper, we first reformulate (1) as a system of nonsmooth equations by using slack variables and minimum function, and, using smoothing technique, we construct the smooth equations. Then, a noninterior continuation method for (1) by modifying and extending the method of Huang [1] is proposed. Under suitable assumptions, we show that the proposed algorithm is globally linearly convergent. We also report some preliminary numerical results, which demonstrate that the algorithm is effective for solving (1).The organization of this paper is as follows. In Section2, we reformulate (1) as a system of smooth equations. In Section 3, we propose a noninterior continuation method for solving (1). Global convergence is analyzed in Section 4. Some preliminary computational results are reported in Section 5.We introduce some notations. All vectors are column vectors, the superscriptT denotes transpose, ℜ
+
n (resp., ℜ
+
+
n) denotes the nonnegative (resp., positive) orthant in ℜ
n. I denotes n
×
n identity matrix. For x
∈
ℜ
n, ∥
x
∥ denotes the 2-norm of x. For a continuously differentiable function F
:
ℜ
n
→
ℜ
m, we denote the Jacobian of F at x
∈
ℜ
n by F
′
(
x
).


## 2. Equivalent Smoothing Reformulation of (1)

In this section, we give the equivalent smoothing reformulation of (1) and discuss some associated properties of the reformulation. Firstly, we introduce the NCP function and the smoothing function. A function ϕ
:
ℜ
2
→
ℜ is called an NCP function, if it possesses the following property:
(2)
ϕ
(
a
,
b
)
=
0
⟺
a
≥
0
,
b
≥
0
,
a
b
=
0
.
One well-known NCP function is the minimum function [9], which is defined as follows:
(3)
ϕ
min
⁡
(
a
,
b
)
=
a
+
b
-
|
a
-
b
|
.
Accordingly, the smoothing function associated with ϕ
min
⁡ is [4]
(4)
ϕ
min
⁡
(
a
,
b
,
μ
)
=
a
+
b
-
(
a
-
b
)
2
+
2
μ
2
.For (1), we introduce a slack variable s
∈
ℜ
m. Then, (1) is equivalent to the following system of equations:
(5)
f
E
(
x
)
=
0
,
f
I
(
x
)
+
s
=
0
,
s
≥
0
.
Based on the minimum function, we reformulate (5) into the following equivalent system of nonlinear equation:
(6)
Φ
(
w
)
∶
=
(
f
E
(
x
)
f
I
(
x
)
+
s
Φ
min
⁡
(
0
,
s
)
)
=
0
,
where Φ
min
⁡
(
0
,
s
)
=
(
ϕ
min
⁡
(
0
,
s
1
)
,
…
,
ϕ
min
⁡
(
0
,
s
m
)
)
T, w
=
(
x
,
s
)
∈
ℜ
n
×
m.Since the function in (6) is nonsmooth, the noninterior continuation method cannot be directly applied to solve (6). In order to make (6) solvable by the noninterior continuation method, we will use the smoothing technique and construct the smooth approximation of Φ as Φ
μ. Consider
(7)
Φ
μ
(
w
)
∶
=
(
f
E
(
x
)
+
μ
x
E
f
I
(
x
)
+
s
+
μ
x
I
Φ
min
⁡
(
0
,
s
,
μ
)
+
μ
s
)
,
where x
I
=
(
x
1
,
x
2
,
…
,
x
m
)
T, x
E
=
(
x
m
+
1
,
x
m
+
2
,
…
,
x
n
)
T, s
∈
ℜ
m, x
=
(
x
I
,
x
E
)
∈
ℜ
n, and Φ
min
⁡
(
0
,
s
,
μ
) = (
ϕ
min
⁡
(
0
,
s
1
,
μ
)
,
…
,
ϕ
min
⁡
(
0
,
s
m
,
μ
)
)
T. Thereby, it is obvious that, if Φ
μ
(
w
)
=
0 and μ
=
0, then x solves (1). It is not difficult to see that, for any w
∈
ℜ
n
×
ℜ
m, the function Φ
μ
(
w
) is continuously differentiable. Let Φ
μ
′
(
w
) denote the Jacobian of the function Φ
μ
(
w
); then, for any w
∈
ℜ
n
×
ℜ
m,
(8)
Φ
μ
′
(
w
)
∶
=
(
f
E
′
(
x
)
+
μ
V
0
(
n
-
m
)
×
m
f
I
′
(
x
)
+
μ
U
I
m
0
m
×
n
Φ
min
⁡
′
(
0
,
s
,
μ
)
+
μ
I
m
)
,
where U
∶
=
[
I
m
0
m
×
(
n
-
m
)
] and V
∶
=
[
0
(
n
-
m
)
×
m
I
n
-
m
]. Here, we use 0
l to denote the l-dimensional zero vector and 0
l
×
q to denote the l
×
q zero matrix for any positive integers l and q. Thus, we can solve approximately the smooth system Φ
μ
(
w
)
=
0 by using Newton’s method at each iteration and then obtain a solution of Φ
0
(
w
)
=
0 by reducing the parameter μ to zero so that a solution of (1) can be found.


## 3. Algorithm

In this section, we propose a noninterior continuation algorithm. Some basic properties are given. In particular, we show that the algorithm is well defined.Algorithm 1 (a noninterior continuation algorithm).
Consider the following.Step  0. Choose δ
,
γ
,
σ
∈
(
0,1
). Take any (
x
0
,
s
0
)
∈
ℜ
2
n and μ
0
∈
(
0
,
∞
); choose β
≥
n such that ∥
Φ
μ
0
(
x
0
,
s
0
)
∥
≤
β
μ
0. Set k
∶
=
0.
Step  1. If μ
k
=
0, then stop..
Step  2. If Φ
μ
k
(
x
k
,
s
k
)
=
0, then set (
x
k
+
1
,
s
k
+
1
)
∶
=
(
x
k
,
s
k
) and θ
k
∶
=
1, and go to Step  4; otherwise, compute (
Δ
x
k
,
Δ
s
k
)
∈
ℜ
2
n by
(9)
Φ
μ
k
′
(
x
k
,
s
k
)
(
Δ
x
k
,
Δ
s
k
)
=
-
Φ
μ
k
(
x
k
,
s
k
)
.
Step  3. Let θ
k be maximum of the values 1
,
δ
,
δ
2
,
… such that
(10)
∥
Φ
μ
k
(
x
k
+
θ
Δ
x
k
,
s
k
+
θ
Δ
s
k
)
∥
≤
[
1
-
σ
θ
k
]
∥
Φ
μ
k
(
x
k
,
s
k
)
∥
.
Set(
x
k
+
1
,
s
k
+
1
)
∶
=
(
x
k
+
θ
Δ
x
k
,
s
k
+
θ
Δ
s
k
).Step  4. Set the following:(11)
μ
¯
k
∶
=
(
1
-
1
1
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
σ
θ
k
)
μ
k
.Letη
k be the minimum of the values 1
,
γ
,
γ
2
,
… such that
(12)
∥
Φ
η
k
μ
¯
k
(
x
k
+
1
,
s
k
+
1
)
∥
≤
β
η
k
μ
¯
k
,and setμ
k
+
1
∶
=
η
k
μ
¯
k. Set k
∶
=
k
+
1 and go to Step  1.Remark 2.
Algorithm1 is a modified version of Huang’s algorithm in [1]. It is easy to see that, if Φ
μ
k
(
w
k
)
=
0, for any k, then Algorithm 1 does not solve the Newton equation (9) and does not perform the line search (10) in the (
k
+
1
)th iteration. Thus, Algorithm 1 only needs to solve at most a linear system of equations at each iteration. Algorithm 1 can be started easily. In fact, we can choose any (
μ
0
,
x
0
,
s
0
)
∈
ℜ
+
+
×
ℜ
n
×
ℜ
m as the starting point of our algorithm and then set
(13)
β
∶
=
max
⁡
{
n
,
∥
Φ
μ
0
(
x
0
,
s
0
)
∥
μ
0
}
.Definef
′
(
x
)
∶
=
[
f
E
′
(
x
)
T
,
f
I
′
(
x
)
T
]
T. We will use the following assumption.Assumption 3.
f
′
(
x
)
+
μ
I
n is invertible for any x
∈
ℜ
n and μ
∈
ℜ
+
+.The next result plays an important role in establishing the well-definedness and the local quadratic convergence of Algorithm1.Lemma 4.
(i)ϕ
min
⁡
(
·
,
·
,
·
) is continuously differentiable at any (
μ
,
a
,
b
)
∈
ℜ
3
∖
(
0,0
,
0
).
(ii) For anyμ
1
,
μ
2
>
0 and (
a
,
b
)
∈
ℜ
×
ℜ, we have
(14)
|
ϕ
min
⁡
(
a
,
b
,
μ
1
)
-
ϕ
min
⁡
(
a
,
b
,
μ
2
)
|
≤
2
|
μ
1
-
μ
2
|
.Theorem 5.
Suppose thatf is a continuously differentiable function and Assumption 3 is satisfied. Then Algorithm 1 is well defined.Proof.
For any square matrixA, we use det
⁡
(
A
) to denote the determinant of A. It is easy to see from (8) that det
⁡
(
Φ
μ
′
(
w
)
)
=
det
⁡
(
f
′
(
x
)
+
μ
I
n
)
·
det
⁡
(
Φ
min
⁡
′
(
0
,
s
,
μ
)
+
μ
I
m
), for any μ
>
0 and w
∈
ℜ
n
×
ℜ
m. Furthermore, it is easy to see that Φ
min
⁡
′
(
0
,
s
,
μ
) is positive semidefinite. Thus, by Assumption 3, we obtain that Φ
μ
′
(
w
) is nonsingular, for any μ
>
0 and w
∈
ℜ
n
×
ℜ
m. Hence, Step  2 is well defined.
Now we prove that Step  3 is well defined. For anyα
∈
(
0,1
], define
(15)
r
(
α
)
=
Φ
μ
k
(
w
k
+
α
Δ
w
k
)
-
Φ
μ
k
(
w
k
)
-
α
Φ
μ
k
′
(
w
k
)
Δ
w
k
.
From μ
k
>
0 and Lemma 4(i), we know that Φ
min
⁡
(
w
) is continuously differentiable at w
k. Thus, by (15), we have
(16)
∥
r
(
α
)
∥
=
o
(
α
)
.
Then by (9), (15) and (16),
(17)
∥
Φ
μ
k
(
w
k
+
α
Δ
w
k
)
∥
≤
∥
Φ
μ
k
(
w
k
)
+
α
Φ
μ
k
′
(
w
k
)
Δ
w
k
∥
+
∥
r
(
α
)
∥
=
(
1
-
α
)
∥
Φ
μ
k
(
w
k
)
∥
+
o
(
α
)
=
(
1
-
σ
α
)
∥
Φ
μ
k
(
w
k
)
∥
-
(
1
-
σ
)
α
∥
Φ
μ
k
(
w
k
)
∥
+
o
(
α
)
.
Since σ
∈
(
0,1
), then (
1
-
σ
)
α
∥
Φ
μ
k
(
w
k
)
∥
>
0. For α sufficient small, we can get ∥
Φ
μ
k
(
w
k
+
α
Δ
w
k
)
∥
≤
(
1
-
σ
α
)
∥
Φ
μ
k
(
w
k
)
∥, this shows that Step  3 is well defined.
Next we show that Step  4 is well defined. IfΦ
μ
k
(
w
k
)
≠
0, it follows from Lemma 4(ii) and (7) that
(18)
∥
Φ
μ
1
(
w
)
-
Φ
μ
2
(
w
)
∥
=
∥
(
(
μ
1
-
μ
2
)
x
Φ
min
⁡
(
0
,
s
,
μ
1
)
-
Φ
min
⁡
(
0
,
s
,
μ
2
)
+
(
μ
1
-
μ
2
)
s
)
∥
≤
|
μ
1
-
μ
2
|
∥
x
∥
+
|
μ
1
-
μ
2
|
∥
s
∥
+
∥
Φ
min
⁡
(
0
,
s
,
μ
1
)
-
Φ
min
⁡
(
0
,
s
,
μ
2
)
∥
≤
|
μ
1
-
μ
2
|
(
∥
x
∥
+
∥
s
∥
)
+
2
n
|
μ
1
-
μ
2
|
=
|
μ
1
-
μ
2
|
(
∥
x
∥
+
∥
s
∥
+
2
n
)
≤
2
n
|
μ
1
-
μ
2
|
(
∥
x
∥
+
∥
s
∥
+
1
)
.
Then, by β
≥
n, (10)–(12), and (18), we have
(19)
∥
Φ
μ
¯
k
(
w
k
+
1
)
∥
≤
∥
Φ
μ
k
(
w
k
+
1
)
∥
+
∥
Φ
μ
k
(
w
k
+
1
)
-
Φ
μ
¯
k
(
w
k
+
1
)
∥
≤
(
1
-
σ
θ
k
)
∥
Φ
μ
k
(
w
k
)
∥
+
2
n
|
μ
k
-
μ
k
¯
|
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
≤
(
1
-
σ
θ
k
)
β
μ
k
+
2
n
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
1
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
σ
θ
k
μ
k
≤
(
1
-
σ
θ
k
)
β
μ
k
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
1
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
β
σ
θ
k
μ
k
=
(
1
-
[
1
-
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
1
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
]
σ
θ
k
)
β
μ
k
=
(
1
-
1
1
+
2
(
∥
x
k
+
1
∥
+
∥
s
k
+
1
∥
+
1
)
σ
θ
k
)
β
μ
k
=
β
μ
¯
k
.
If Φ
μ
k
(
w
k
)
=
0, similarly we also obtain that (19) holds. Thus, from (19), we know that there exists a minimal η
k
∈
(
0,1
] such that (12) holds; that is, Step  4 is well defined.
Therefore, Algorithm1 is well defined.


## 4. Convergence of Algorithm1

In this section, we analyze the global convergence properties of Algorithm1. We show that any accumulation point of the iteration sequence {
w
k
} is a solution of the system Φ
(
w
)
=
0.Theorem 6.
Suppose thatf is a continuously differentiable function and (
w
*
,
μ
*
)
∶
=
(
x
*
,
s
*
,
μ
*
) is an accumulation point of the iteration sequence {
(
w
k
,
μ
k
)
} generated by Algorithm 1. If Assumption 3 is satisfied, then lim
⁡
k
→
∞
μ
k
=
0, and hence w
* is a solution of Φ
(
w
)
=
0.Proof.
Since the sequence{
μ
k
} is monotonically decreasing and bounded from below by zero, then μ
k
→
μ
*
≥
0. If μ
*
=
0, we obtain the desired result. Suppose μ
*
>
0. Without loss of generality, we assume that lim
⁡
k
→
∞
(
w
k
,
μ
k
)
=
(
w
*
,
μ
*
). If there exists an infinite subset K
1
=
{
k
1
,
…
,
k
i
,
k
i
+
1
,
…
} such that Φ
μ
k
(
w
k
)
=
0, k
∈
K
1, then, by Step  2 of Algorithm 1, we have θ
k
i
≡
1, for any i
≥
1. It follows from Step  4 that
(20)
μ
k
i
+
1
≤
μ
k
i
+
1
=
η
k
i
μ
¯
k
i
≤
(
1
-
σ
1
+
2
(
∥
x
k
i
+
1
∥
+
∥
s
k
i
+
1
∥
+
1
)
)
μ
k
i
.
Let i
→
+
∞; we have that
(21)
0
<
μ
*
≤
(
1
-
σ
1
+
2
(
∥
x
*
∥
+
∥
s
*
∥
+
1
)
)
μ
*
,
which is a contradiction. Therefore, without loss of generality, we may assume that Φ
μ
k
(
w
k
)
≠
0 holds, for any k
≥
0. From the assumption, f is continuously differentiable and (7); it is not difficult to see that Φ
μ
(
w
) is continuously differentiable in both w and μ for any μ
>
0. Since μ
k
→
μ
*
>
0, by assumption, then we have
(22)
lim
⁡
k
→
∞
Φ
μ
k
(
w
k
)
=
Φ
μ
*
(
w
*
)
,
lim
⁡
k
→
∞
Φ
μ
k
′
(
w
k
)
=
Φ
μ
*
′
(
w
*
)
.
The steplength θ
¯
k
∶
=
θ
k
/
δ does not satisfy (10); that is,
(23)
∥
Φ
μ
k
(
w
k
+
θ
¯
k
Δ
w
k
)
∥
-
∥
Φ
μ
k
(
w
k
)
∥
θ
¯
k
>
-
σ
∥
Φ
μ
k
(
w
k
)
∥
.
By taking k
→
∞ in the above inequality, we have
(24)
Φ
μ
*
(
w
*
)
T
Φ
μ
*
(
w
*
)
Δ
w
*
≥
-
σ
∥
Φ
μ
*
(
w
*
)
∥
2
.
It follows from (9) that
(25)
Φ
μ
*
(
w
*
)
T
Φ
μ
*
(
w
*
)
Δ
w
*
=
-
∥
Φ
μ
*
(
w
*
)
∥
2
.
By substituting (25) into (24), we obtain that ∥
Φ
μ
*
(
w
*
)
∥
≤
σ
∥
Φ
μ
*
(
w
*
)
∥, which contradicts σ
<
1. This proves μ
*
=
0.
Next, we prove thatw
* is a solution of Φ
(
w
)
=
0. In view of the Algorithm 1, we have
(26)
∥
Φ
μ
k
(
w
k
)
∥
≤
β
μ
k
.
Then, by taking the limit on both sides of (26) based on the continuity of Φ
μ
(
w
), we have ∥
Φ
0
(
w
*
)
∥
=
∥
Φ
μ
*
(
w
*
)
∥
≤
β
μ
*. Hence, ∥
Φ
0
(
w
*
)
∥
=
0.


## 5. Numerical Experiments

In this section, we implement Algorithm1 for solving the system of equalities and inequalities in MATLAB in order to see the behavior of our noninterior continuation algorithm. All the program codes were written in MATLAB and run in MATLAB 7.5 environment. All numerical experiments were done at a PC with CPU of 1.6 GHz and RAM of 512 MB.In numerical implementation, we adopt the similar strategy to [10]; the function Φ
μ
(
w
) defined by (7) is replaced by
(27)
Φ
μ
(
w
)
∶
=
(
f
E
(
x
)
+
c
μ
x
E
f
I
(
x
)
+
s
+
c
μ
x
I
Φ
min
⁡
(
0
,
s
,
μ
)
+
c
μ
s
)
,
where c is a given constant. It is easy to see that such a change does not destroy any theoretical results obtained in this paper. In order to obtain an interior solution of (1), we solve the following system of equalities and inequalities:
(28)
f
I
(
x
)
+
ɛ
e
≤
0
,
f
E
(
x
)
=
0
,
where ɛ is a sufficiently small number and e is a vector of all ones. The parameters used in Algorithm 1 were as follows: σ
=
0.4, ɛ
=
0.00001, δ
=
γ
=
0.5, μ
0
=
{
1
,
Φ
0
(
w
0
)
}, and β
=
max
⁡
{
n
,
∥
Φ
μ
0
(
w
0
)
∥
/
μ
0
}; the parameter c and the starting point are chosen according to the ones listed in Tables 1, 2, 3, and 4. Set s
0
∶
=
-
f
I
(
x
0
) and w
0
=
(
x
0
,
s
0
). We used μ
≤
1
0
-
6 as the stopping criterion.Table 1
Numerical results for Example 1′.
ST
c
=
10
2
c
=
10
3
IT
SOL
IT
SOL
(
0,0
,
0
)
T
8
(
0.8771,0.6720,0.5725
)
T
6
(
0.8697,0.6680,0.5741
)
T
(
-
1
,
-
1
,
-
1
)
T
6
(
0.8771,0.6721,0.5726
)
T
5
(
0.8664,0.6665,0.5730
)
T
(
1,1
,
1
)
T
8
(
0.8771,0.6720,0.5725
)
T
6
(
0.8697,0.6680,0.5741
)
T
(
1,0
,
1
)
T
8
(
0.8766,0.6718,0.5726
)
T
9
(
0.8702,0.6687,0.5737
)
TTable 2
Numerical results for Example 2′.
ST
c
=
10
2
c
=
1
0
3
IT
SOL
IT
SOL
(
0,0
,
0
)
T
12
(
-
0.8362
,
-
0.8605,1.9566
)
T
10
(
-
0.8396
,
-
0.8600,1.9558
)
T
(
-
1
,
-
1
,
-
1
)
T
12
(
-
0.8362
,
-
0.8606,1.9565
)
T
11
(
-
0.8394
,
-
0.8600,1.9558
)
T
(
1,1
,
1
)
T
10
(
-
0.8364
,
-
0.8605,1.9565
)
T
9
(
-
0.8446
,
-
0.8592,1.9548
)
T
(
0,1
,
0
)
T
11
(
-
0.8363
,
-
0.8605,1.9565
)
T
13
(
-
0.8376
,
-
0.8603,1.9562
)
TTable 3
Numerical results for Example 3′.
ST
c
=
10
2
c
=
10
3
IT
SOL
IT
SOL
(
-
1
,
-
1
,
-
1
)
T
5
(
-
0.0952,0.0952,0.4471
)
T
4
(
-
0.0946,0.0944,0.4474
)
T
(
0,0
,
0
)
T
13
(
-
0.0953,0.0953,0.4471
)
T
10
(
-
0.0948,0.0946,0.4472
)
T
(
1,1
,
1
)
T
5
(
-
0.0953,0.0952,0.4471
)
T
4
(
-
0.0947,0.0946,0.4476
)
T
(
0,1
,
0
)
T
5
(
-
0.0952,0.0952,0.4471
)
T
5
(
-
0.0950,0.0949,0.4472
)
TTable 4
Numerical results for Example 4′.
ST
c
=
10
2
c
=
10
3
IT
SOL
IT
SOL
(
0,0
,
0
)
T
18
(
0.5769,0.4787,99.9981
)
T
22
(
0.7944,0.3344,100.0022
)
T
(
0,0
,
-
1
)
T
18
(
0.3516,0.7573,100.0028
)
T
14
(
1.2045,0.0456,100.0051
)
T
(
1,0
,
1
)
T
19
(
0.8154,0.4056,99.9981
)
T
9
(
1.2619
,
-
1.2051,99.9994
)
T
(
0,0
,
1
)
T
17
(
0.6092,0.4122,99.9992
)
T
13
(
1.0040
,
-
1.0030,100.0533
)
TWe consider the following four examples.Example 1.
Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(29)
f
1
(
x
)
∶
=
(
x
1
-
0.5
)
2
+
(
x
2
-
1
)
2
-
0.25
≤
0
,
f
2
(
x
)
∶
=
-
(
x
1
-
0.5
)
2
-
(
x
1
-
1.1
)
2
+
x
2
2
-
0.26
≤
0
,
f
3
(
x
)
∶
=
x
2
+
x
3
2
-
1
≤
0
.Example 2.
Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(30)
f
1
(
x
)
∶
=
x
1
+
x
2
e
0.8
x
3
+
e
1.6
≤
0
,
f
2
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
3
2
-
5.2675
=
0
,
f
3
(
x
)
∶
=
x
1
+
x
2
+
x
3
-
0.2605
=
0
.Example 3.
Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(31)
f
1
(
x
)
∶
=
0.8
-
e
x
1
+
x
2
+
x
3
2
≤
0
,
f
2
(
x
)
∶
=
1.21
e
x
1
+
e
x
2
-
2.2
=
0
,
f
3
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
2
-
0.1135
=
0
.Example 4.
Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(32)
f
1
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
3
2
-
10000
≤
0
,
f
2
(
x
)
∶
=
x
1
-
0.7
sin
x
1
-
0.2
cos
⁡
x
2
=
0
,
f
3
(
x
)
∶
=
x
2
-
0.7
cos
⁡
x
1
+
0.2
sin
x
2
=
0
.The first example only contains inequalities; the other examples contain equalities and inequalities. Instead of these three examples, we use Algorithm1 to solve the following problems.Example
1
′
. Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(33)
f
1
(
x
)
∶
=
(
x
1
-
0.5
)
2
+
(
x
2
-
1
)
2
-
0.25
+
ɛ
≤
0
,
f
2
(
x
)
∶
=
-
(
x
1
-
0.5
)
2
-
(
x
1
-
1.1
)
2
+
x
2
2
-
0.26
+
ɛ
≤
0
,
f
3
(
x
)
∶
=
x
2
+
x
3
2
-
1
+
ɛ
≤
0
.Example
2
′
. Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(34)
f
1
(
x
)
∶
=
x
1
+
x
2
e
0.8
x
3
+
e
1.6
+
ɛ
≤
0
,
f
2
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
3
2
-
5.2675
=
0
,
f
3
(
x
)
∶
=
x
1
+
x
2
+
x
3
-
0.2605
=
0
.Example
3
′
. Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(35)
f
1
(
x
)
∶
=
0.8
-
e
x
1
+
x
2
+
x
3
2
+
ɛ
≤
0
,
f
2
(
x
)
∶
=
1.21
e
x
1
+
e
x
2
-
2.2
=
0
,
f
3
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
2
-
0.1135
=
0
.Example
4
′
. Consider (1), where f
∶
=
(
f
1
,
f
2
,
f
3
)
T with x
∈
ℜ
3 and
(36)
f
1
(
x
)
∶
=
x
1
2
+
x
2
2
+
x
3
2
-
10000
+
ɛ
≤
0
,
f
2
(
x
)
∶
=
x
1
-
0.7
sin
x
1
-
0.2
cos
⁡
x
2
=
0
,
f
3
(
x
)
∶
=
x
2
-
0.7
cos
⁡
x
1
+
0.2
sin
x
2
=
0
.The numerical results are listed in Tables1, 2, 3, 4, and 5, where Exam denotes the tested examples, ST denotes the starting point x
0, C denotes the value of the parameter c given in (27), CPU denotes the CPU time for solving the underlying problem in second, IT denotes the total number of iterations, − represents iteration number in more than 1000, and SOL denotes the solution obtained by Algorithm 1.Table 5
Numerical results for Examples 1′–4′.
Example
ST
Our algorithm
Algorithm in [8]
IT
CPU
IT
CPU
Example 1′
(
0,0
,
0
)
T
8
0.007767
6
0.006365
(
-
1
,
-
1
,
-
1
)
T
6
0.006270
8
0.007373
(
1,1
,
1
)
T
8
0.006578
7
0.006137
Example 2′
(
0,0
,
0
)
T
12
0.016807
49
0.068499
(
-
1
,
-
1
,
-
1
)
T
12
0.017554
45
0.065420
(
1,1
,
1
)
T
10
0.026884
54
0.187465
Example 3′
(
0,0
,
0
)
T
13
0.011897
5
0.004939
(
-
1
,
-
1
,
-
1
)
T
5
0.007156
18
0.023658
(
1,1
,
1
)
T
5
0.006765
11
0.010136
Example 4′
(
0,0
,
0
)
T
18
0.030636
—
—
(
0,0
,
1
)
T
17
0.036194
—
—
(
1,0
,
1
)
T
19
0.043265
—
—From Tables1, 2, 3, and 4, it is easy to see that all problems that we tested can be solved efficiently. In Table 5, we compare our proposed algorithm with the algorithm in [8]. The numerical results illustrate that our algorithm is more effective.



---

*Source: 592540-2014-04-24.xml*