# A Noninterior Path following Algorithm for Solving a Class of Multiobjective Programming Problems

Authors: Menglong Su; Zhengbang Zha; Zhonghai Xu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Multiobjective programming problems have been widely applied to various engineering areas which include optimal design of an automotive engine, economics, and military strategies. In this paper, we propose a noninterior path following algorithm to solve a class of multiobjective programming problems. Under suitable conditions, a smooth path will be proven to exist. This can give a constructive proof of the existence of solutions and lead to an implementable globally convergent algorithm. Several numerical examples are given to illustrate the results of this paper.


---

## Body

## 1. Introduction

In this paper, the following conventions will be used. Ifx
,
y
∈
R
n, thenx
≦
y if and only if x
i
≤
y
i
,
i
=
1
,
…
,
n;
x
<
y if and only if x
i
<
y
i
,
i
=
1
,
…
,
n;
x
≤
y if and only if x
i
≤
y
i
,
i
=
1
,
…
,
n, with strict inequality holding for at least one i;
x
=
y if and only if x
i
=
y
i
,
i
=
1
,
…
,
n.Multiobjective programming problems have been widely applied to various engineering areas which include optimal design of an automotive engine, economics, and military strategies. Consider the following multiobjective program (MOP):(1)
min
⁡
x
∈
R
n
f
(
x
)
s
.
t
.
g
(
x
)
≦
0
,
h
(
x
)
=
0
,
where f
:
R
n
→
R
p,  g
:
R
n
→
R
m, and h
:
R
n
→
R
l are assumed to be three times continuously differentiable. In this paper, the nonnegative and positive orthants of R
m are denoted as R
+
m and R
+
+
m, respectively.In the literature, solutions for a multiobjective programming problem are referred to variously as efficient, Paretooptimal, and nondominated solutions. In this paper we will refer to a solution of a multiobjective programming problem as an efficient solution. It is well-known that ifx is an efficient solution of MOP problems, under some constraint qualifications (the Kuhn and Tucker constraint qualification [1] or the Abadie constraint qualification [2]), then the following Karush-Kuhn-Tucker (KKT) condition at x for MOP problems holds [3, 4]:
(2)
∇
f
(
x
)
λ
+
∇
g
(
x
)
u
+
∇
h
(
x
)
v
=
0
,
h
(
x
)
=
0
,
U
g
(
x
)
=
0
,
g
(
x
)
≦
0
,
u
≧
0
,
where ∇
f
(
x
)
=
(
∇
f
1
(
x
)
,
…
,
∇
f
p
(
x
)
)
∈
R
n
×
p, ∇
g
(
x
)
=
(
∇
g
1
(
x
)
,
…
,
∇
g
m
(
x
)
)
∈
R
n
×
m, ∇
h
(
x
)
=
(
∇
h
1
(
x
)
,
…
,
∇
h
l
(
x
)
)
∈
R
n
×
l,  λ
∈
R
+
p
∖
{
0
}, u
∈
R
m, v
∈
R
l, and U
=
diag
⁡
(
u
)
∈
R
m
×
m. We say that x is a KKT point of MOP problems if it satisfies the KKT condition.To solve linear programming, in 1984, Karmarkar [5] proposed a projective scaling algorithm, which is the first efficient polynomial-time algorithm in practice and hence competitive with the widely used simplex algorithm, which has no polynomiality although it is also efficient for linear programming. It was noted that Karmarkar’s projective scaling algorithm is equivalent to a projected Newton barrier algorithm [6]. Based on Karmarkar’s projective scaling algorithm, ones developed various central path following algorithms (or, in other terms, interior point methods and homotopy methods, see [7–12], etc.), which replaced projective scaling transformation of Karmarkar’s algorithm with affine scaling transformation. This modification can relax the particular assumptions on the simplex structure by Karmarkar’s algorithm. Later, the central path following algorithms were extended to solve convex nonlinear programming problems (see [13–16], etc.). It should be pointed out that all these central path following algorithms are globally convergent, but their global convergence results were obtained under the assumptions that the logarithmic barrier function is strictly convex and the solution set is nonempty and bounded.Since Kellogg et al. [17] and Smale [18] proposed the notable homotopy method, this method has become a powerful solution tool with global convergence in finding solutions for various nonlinear problems, for example, zeros or fixed points of maps; see [19–24] and so forth. Furthermore, in [25], for convex nonlinear programming problems, by using the ideas of homotopy methods, Lin et al. proposed a new interior point method, which is called the combined homotopy interior point (CHIP) method, for solving convex programming problems. In that paper, the authors removed the convexity condition of the logarithmic barrier function and the nonemptiness of the solution set. In [26], by taking a piecewise technique, under the commonly used conditions in the literature, Yu et al. obtained the polynomiality of the CHIP method. Their results show that the efficiency of the CHIP method is also very well. The advantages mentioned above attract more and more researchers’ attention and the CHIP method has been applied to various areas such as fixed point problems [27, 28], variational inequalities [29, 30], and bilevel programming problems [31]. Furthermore, in 2008, for a class of nonconvex MOP problems, Song and Yao developed a new CHIP method [32]. In that paper, the authors constructed a new combined homotopy and thus obtained the existence of an interior path from a known interior point to a KKT point of (1).It is well-known that the choice of initial points plays an important role in the computational efficiency of the predictor-corrector algorithms (for a good introduction and a complete survey about the predictor-corrector algorithms, one can refer to the books [33, 34], etc.) resulting from the CHIP algorithm. Here it should be pointed out that, for parametric programming (see [35–42], etc., for related works), the predictor-corrector algorithms also had successful applications (see [35, 43], etc.). But in [32], initial points are generally confined in the interior of the feasible set, which is not easily localized for many cases; hence it is essential to enlarge the scope of choice of initial points. To this end, in this paper, we apply proper perturbations to the constraint functions and hence develop a noninterior path following algorithm. With the new approach, we are capable of choosing initial points more easily. This can improve the computational efficiency of the predictor-corrector algorithms greatly compared to before.Another purpose of this paper is to solve MOP problems in a broader class of nonconvex sets than those in [32]. To complete this work, we introduce C
2 mappings ξ
i
(
x
,
u
i
)
∈
R
n
(
i
=
1
,
…
,
m
) and η
j
(
x
,
v
j
)
∈
R
n
(
j
=
1
,
…
,
l
), which can make us extend the results in [32] to more general nonconvex sets.In this paper, under the commonly used conditions in the literature, a bounded smooth homotopy path from a given initial point to a KKT point of (1) can be proven to exist. This forms the theoretical base of the noninterior path following algorithm. Numerically tracing the smooth path can lead to an implementable globally convergent algorithm for MOP problems. An explicit advantage of the noninterior path following algorithm is that the induced predictor-corrector algorithm has global convergence, compared with some locally convergent algorithms, for example, the notable Newton’s algorithms [33, 34]. Although the usual continuation methods (see [44–46], etc.) are globally convergent, they require that the partial derivative of the mapping H in (9) with respect to w is nonsingular. This requirement is often not easily satisfied in practice (see [33, 34], etc.). However, by the parameterized Sard theorem, the noninterior path following algorithm only requires that the mapping H in (9) is of full row rank. This is another advantage of the algorithm presented in this paper. In addition, compared with the results in [32], we can solve MOP problems on more general nonconvex sets, and we also enlarge the scope of choice of initial points to the exterior of the feasible set.This paper is organized as follows. In Section2, we apply proper perturbations to the constrained functions, based on which, we construct a new combined homotopy and hence develop a noninterior path following algorithm. In Section 3, we use the predictor-corrector algorithm resulting from the noninterior path following algorithm to compute some experimental examples to illustrate the results of this paper. Finally, we make some conclusions in Section 4.


## 2. Theoretical Analysis of the Noninterior Path following Algorithm

In this section, letΩ
=
{
x
∈
R
n
:
g
(
x
)
≦
0
,
h
(
x
)
=
0
}, Ω
0
=
{
x
∈
R
n
:
g
(
x
)
<
0
,
h
(
x
)
=
0
}, Λ
+
=
{
λ
∈
R
+
p
:
∑
q
=
1
p
λ
q
=
1
}, Λ
+
+
=
{
λ
∈
R
+
+
p
:
∑
q
=
1
p
λ
q
=
1
}
,
B
(
x
)
=
{
i
∈
{
1
,
…
,
m
}
:
g
i
(
x
)
=
0
}, and U
(
0
)
=
diag
⁡
(
u
(
0
)
)
∈
R
m
×
m. In addition, ∥
·
∥ stands for the Euclidean norm.In [32], Song and Yao developed a new CHIP method to solve the KKT point of (1) in a class of nonconvex sets; the main result of that paper is formulated as follows.Theorem 1.
Suppose that(
A
1
)
Ω
0 is nonempty and Ω is bounded;
(
A
2
)
for anyx
∈
Ω the matrix {
∇
g
i
(
x
)
,
∇
h
(
x
)
:
i
∈
B
(
x
)
} is of full column rank;
(
A
3
)
(the normal cone condition ofΩ) for any x
∈
Ω the normal cone of Ω at x only meets Ω at x; that is, for any x
∈
Ω, one has
(3)
{
x
+
∑
i
∈
B
(
x
)
‍
u
i
∇
g
i
(
x
)
+
∇
h
(
x
)
v
:
u
i
≧
0
f
o
r
i
∈
B
(
x
)
}
⋂
Ω
=
{
x
}
.Then for almost all (
x
(
0
)
,
u
(
0
)
,
v
(
0
)
,
λ
(
0
)
)
∈
Ω
0
×
R
+
+
m
×
{
0
}
×
Λ
+
+, there is a regular solution curve of the homotopy
(4)
(



(
1
-
μ
)
(
∇
f
(
x
)
λ
+
∇
g
(
x
)
u
)
+
∇
h
(
x
)
v
+
μ
(
x
-
x
(
0
)
)
h
(
x
)
U
g
(
x
)
-
μ
U
(
0
)
g
(
x
(
0
)
)
(
1
-
μ
)
(
1
-
∑
q
=
1
p
λ
q
)
e
p
-
μ
(
λ
-
λ
(
0
)
)



)
=
0
,
where e
p
=
(
1
,
…
,
1
)
T
∈
R
p,  μ
∈
(
0,1
]. When μ
→
0, the limit set T
⊂
Ω
×
R
+
m
×
R
l
×
Λ
+
×
{
0
} is nonempty and the x-component of any point in T is a KKT point of (1).However, in [32], initial points are confined in the interior of Ω. This point may reduce the computational efficiency of predictor-corrector algorithms greatly. To enlarge the scope of choice of initial points, in this paper, we apply proper perturbations to the constrained functions g
(
x
), h
(
x
) and introduce the parameters
(5)
γ
i
=
{
2
g
i
(
x
(
0
)
)
,
g
i
(
x
(
0
)
)
>
0
,
1
,
g
i
(
x
(
0
)
)
=
0
,
0
,
g
i
(
x
(
0
)
)
<
0
,
i
=
1
,
…
,
m
,
θ
j
=
{
1
,
h
j
(
x
(
0
)
)
≠
0
,
0
,
h
j
(
x
(
0
)
)
=
0
,
j
=
1
,
…
,
l
.
Then let e
m
=
(
1
,
…
,
1
)
T
∈
R
m, γ
=
(
γ
1
,
…
,
γ
m
)
T
∈
R
m, θ
=
(
θ
1
,
…
,
θ
l
)
T
∈
R
l, Ω
(
μ
)
=
{
x
∈
R
n
:
g
(
x
) − μ
γ
(
g
(
x
(
0
)
)
+
e
m
)
≦
0
,
h
(
x
)
-
μ
θ
h
(
x
(
0
)
)
=
0
}, Ω
0
(
μ
)
=
{
x
∈
R
n
:
g
(
x
)
-
μ
γ
(
g
(
x
(
0
)
)
+
e
m
)
<
0
,
h
(
x
)
-
μ
θ
h
(
x
(
0
)
)
=
0
}, I
(
x
,
μ
)
=
{
i
∈
{
1
,
…
,
m
}
:
g
i
(
x
)
-
μ
γ
i
(
g
i
(
x
(
0
)
)
+
1
)
=
0
}.At the same time, to solve MOP problems in more general nonconvex sets, we assume that there exist continuous mappingsξ
(
x
,
u
)
=
(
ξ
1
(
x
,
u
1
)
,
…
,
ξ
m
(
x
,
u
m
)
)
∈
R
n
×
m and η
(
x
,
v
)
=
(
η
1
(
x
,
v
1
)
,
…, η
l
(
x
,
v
l
)
)
∈
R
n
×
l such that the following assumptions hold.(
C
1
)
Ω
0
(
μ
) is nonempty and Ω
(
μ
) is bounded.
(
C
2
)
ξ
i
(
x
,
0
)
=
0
,
i
=
1
,
…
,
m, η
j
(
x
,
0
)
=
0
,
j
=
1
,
…
,
l; besides, for any x
∈
Ω
(
μ
), if ∥
(
y
,
z
,
u
,
v
)
∥
→
∞, then
(6)
∥
∑
i
∈
I
(
x
,
μ
)
‍
(
y
i
∇
g
i
(
x
)
+
ξ
i
(
x
,
u
i
)
)
+
∇
h
(
x
)
z
+
∑
j
=
1
l
‍
η
j
(
x
,
v
j
)
∥
⟶
∞
.
(
C
3
)
For anyx
∈
Ω
(
μ
), if
(7)
∑
i
∈
I
(
x
,
μ
)
‍
(
y
i
∇
g
i
(
x
)
+
ξ
i
(
x
,
u
i
)
)
+
∇
h
(
x
)
z
+
∑
j
=
1
l
‍
η
j
(
x
,
v
j
)
=
0
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
y
i
≧
0
,
u
i
≧
0
,
theny
i
=
0,  u
i
=
0,  ∀
i
∈
I
(
x
,
μ
),  z
=
0,  v
j
=
0
,
j
=
1
,
…
,
l.
(
C
4
)
Whenμ
=
0,1, for any x
∈
Ω
(
μ
), we have
(8)
{
x
+
∑
i
∈
I
(
x
,
μ
)
‍
ξ
i
(
x
,
u
i
)
+
∑
j
=
1
l
‍
η
j
(
x
,
v
j
)
:
u
i
≧
0
for
i
∈
I
(
x
,
μ
)
∑
j
=
1
l
‍
}
⋂
Ω
(
μ
)
=
{
x
}
.Next, we construct a new combined homotopy as follows:(9)
H
(
w
,
μ
)
=
(
(
1
-
μ
)
(
∇
f
(
x
)
λ
+
(
1
-
μ
)
∇
g
(
x
)
u
)
+
(
1
-
μ
)
∇
h
(
x
)
v
+
∑
i
=
1
m
ξ
i
(
x
,
μ
(
1
-
μ
)
u
i
)
+
∑
j
=
1
l
η
j
(
x
,
μ
v
j
)
+
μ
(
x
-
x
(
0
)
)
+
μ
(
1
-
μ
)
α
h
(
x
)
-
μ
θ
h
(
x
(
0
)
)
U
(
g
(
x
)
-
μ
γ
(
g
(
x
(
0
)
)
+
e
m
)
)
+
μ
β
(
1
-
μ
)
(
1
-
∑
q
=
1
p
λ
q
)
e
p
-
μ
(
λ
-
λ
(
0
)
)
)
=
0
,
where w
=
(
x
,
u
,
v
,
λ
)
∈
R
n
+
m
+
l
×
Λ
+, α
∈
R
n, and β
∈
R
+
+
m.Remark 2.
(1) In [32], the initial point x
(
0
) is a strictly feasible point and has to satisfy the following constraints: g
(
x
(
0
)
)
<
0 and h
(
x
(
0
)
)
=
0. However, it is not easy to choose such an initial point in practice when the constraint functions g
(
x
) and h
(
x
) are complex. For example, when the feasible set is Ω
=
{
(
x
1
,
x
2
,
x
3
,
x
4
)
∈
R
4
:
x
1
2
+
x
2
2
+
x
3
2
+
x
4
2
+
x
1
-
x
2
+
x
3
-
x
4
-
8
≦
0
,
x
1
2
+
2
x
2
2
+
x
3
2
+
2
x
4
2
-
x
1 − x
4
-
10
≦
0,2
x
1
2
+
x
2
2
+
x
3
2
+
2
x
1
-
x
2
-
x
4
-
5
≦
0
,
x
1
-
5
≦
0
,
x
2
-
5
≦
0
} (see [25, Example 4.1]), it is difficult to choose the initial point x
(
0
) satisfying all the constraints for this example. This difficulty may reduce the computational efficiency of the algorithm in [32]. In this paper, we can choose the initial point x
(
0
) arbitrarily in R
n, by selecting proper parameters γ and θ according to the signs of g
(
x
(
0
)
) and h
(
x
(
0
)
). Since the initial point for the example mentioned above can be chosen arbitrarily in R
n, this modification can improve the computational efficiency of algorithms greatly compared to before. In addition, compared with some locally convergent methods, for example, the notable Newton’s methods, the method proposed in this paper is a globally convergent method, whose initial points can be chosen more easily.
(2) In [32], the authors required that the feasible set must satisfy the so-called normal cone condition, which is a generalization of the convexity condition (Figure 1). If the feasible set is a convex set, then it satisfies the normal cone condition. On the other hand, if the feasible set satisfies the normal cone condition, then the outer normal cone of the feasible set at a boundary point x can not meet the interior of the feasible set but meets the feasible set only at x. In this paper, we extend the results in [32] to more general nonconvex sets. If the feasible set satisfies the normal cone condition, let ξ
i
(
x
,
u
i
)
=
∇
g
i
(
x
)
u
i,  i
=
1
,
…
,
m,  η
j
(
x
,
v
j
)
=
∇
h
j
(
x
)
v
j,  j
=
1
,
…
,
l; then it necessarily satisfies assumptions (
C
1
)
–
(
C
4
). Conversely, the conclusion does not hold. This point can be illustrated by Examples 1–4 in Section 3.Figure 1
The nonconvex set satisfying the normal cone condition.For a givenx
(
0
), the zero-point set of H
(
w
,
μ
) is denoted by
(10)
H
-
1
(
0
)
=
{
(
w
,
μ
)
∈
R
n
+
m
+
l
×
Λ
+
×
(
0,1
]
:
H
(
w
,
μ
)
=
0
}
.Lemma 3.
LetH be defined as in (9) and let assumptions (
C
1
)
–
(
C
4
) hold. Then the equation H
(
w
,
1
)
=
0 has a unique solution.Proof.
Whenμ
=
1, the homotopy equation (9) becomes
(11)
∑
j
=
1
l
‍
η
j
(
x
,
v
j
)
+
x
-
x
(
0
)
=
0
,
h
(
x
)
-
θ
h
(
x
(
0
)
)
=
0
,
U
(
g
(
x
)
-
γ
(
g
(
x
(
0
)
)
+
e
m
)
)
+
β
=
0
,
λ
-
λ
(
0
)
=
0
.
From the second and third equations in (11), we get that x
∈
Ω
0
(
1
). Then assumption (
C
4
), together with the first equation in (11), yields that x
=
x
(
0
). By assumption (
C
2
), we get v
=
0. So it follows from the third equation in (11) that u
=
-
[
diag
⁡
(
g
(
x
(
0
)
)
-
γ
(
g
(
x
(
0
)
)
+
e
m
)
)
]
-
1
β. At last, from the fourth equation in (11), we obtain λ
=
λ
(
0
). Therefore (11) has a unique solution w
=
w
(
0
)
=
(
x
(
0
)
,
-
[
diag
⁡
(
g
(
x
(
0
)
)
-
γ
(
g
(
x
(
0
)
)
+
e
m
)
)
]
-
1
β
,
0
,
λ
(
0
)
).In the following, we recall some basic definitions and results from differential topology, which will be used in our main result of this paper.The inverse image theorem (see [47]) tells us that if 0 is a regular value of the map H, then H
-
1
(
0
) consists of some smooth curves. The regularity of H can be obtained by the following lemma.Lemma 4 (transversality theorem, see [21]).
LetQ, N, and P be smooth manifolds with dimensions q
,
m, and p
~, respectively. Let W
⊂
P be a submanifold of codimension p (i.e., p
~
=
p
+ dimension of W). Consider a smooth map Φ
:
Q
×
N
→
P. If Φ is transversal to W, then, for almost all a
∈
Q, Φ
a
(
·
)
=
Φ
(
a
,
·
)
:
N
→
P is transversal to W. Recall that a smooth map h
:
N
→
P is transversal to W if
(12)
{
R
a
n
g
e
(
D
h
(
x
)
)
}
+
{
T
y
W
}
=
T
y
P
,
h
h
h
h
h
h
h
h
i
w
h
e
n
e
v
e
r
y
=
h
(
x
)
∈
W
,
where D
h is the Jacobi matrix of h and T
y
W and T
y
P denote the tangent spaces of W and P at y, respectively.In this paper,W
=
{
0
}, so the transversality theorem is corresponding to the parameterized Sard theorem on smooth manifolds.Lemma 5 (parameterized Sard theorem).
LetV
⊂
R
n, U
⊂
R
m be open sets and let Φ
:
V
×
U
→
R
k be a C
r map, where r
>
max
⁡
⁡
{
0
,
m
-
k
}. If 0
∈
R
k is a regular value of Φ, then, for almost all a
∈
V, 0 is a regular value of Φ
a
≡
Φ
(
a
,
·
).With the preparation of the previous lemmas, we can prove the following main theorem on the existence and boundedness of a smooth path from a given pointx
(
0
) in R
n to a KKT point of (1). This implies the global convergence of the noninterior path following algorithm.Theorem 6.
LetH be defined as in (9) and let assumptions (
C
1
)
–
(
C
4
) hold. Then, for almost all w
(
0
)
∈
R
n
×
R
+
+
m
×
{
0
}
×
Λ
+
+, there exists a C
1 curve (
w
(
s
)
,
μ
(
s
)
) of dimension 1 such that
(13)
H
(
w
(
s
)
,
w
(
0
)
,
μ
(
s
)
)
=
0
,
(
w
(
0
)
,
μ
(
0
)
)
=
(
w
(
0
)
,
1
)
.
When μ
(
s
)
→
0, w
(
s
) tends to a point w
*
=
(
x
*
,
u
*
,
v
*
,
λ
*
). The x-component of w
* is a KKT point of (1).Proof .
Whenx
(
0
), λ
(
0
), and α are considered as variables, we denote H
(
w
,
μ
) by H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
). Let the Jacobian matrix of H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
) be denoted by D
H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
), for any μ
∈
(
0,1
],(14)
∂
H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
)
∂
(
x
(
0
)
,
α
,
u
,
λ
(
0
)
)
=
(
-
μ
I
μ
(
1
-
μ
)
I
(
1
-
μ
)
2
∇
g
(
x
)
+
μ
(
1
-
μ
)
∇
u
ξ
(
x
,
μ
(
1
-
μ
)
u
)
0
-
μ
θ
∇
h
(
x
(
0
)
)
T
0
0
0
-
μ
γ
U
∇
g
(
x
(
0
)
)
T
0
diag
⁡
(
g
(
x
)
-
γ
(
g
(
x
(
0
)
)
+
e
m
)
)
0
0
0
0
μ
I
)
,where ∇
u
ξ
(
x
,
μ
(
1
-
μ
)
u
)
=
(
∇
u
1
ξ
1
(
x
,
μ
(
1
-
μ
)
u
1
)
,
…
,
∇
u
m
ξ
m
(
x
,
μ
(
1
-
μ
)
u
m
)
). Since ∇
h
(
x
)
T is a matrix of full row rank, ∂
H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
)
/
∂
(
x
(
0
)
,
α
,
u
,
λ
(
0
)
) is of full row rank. Therefore D
H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
) is also of full row rank, and 0 is a regular value of H
¯
(
w
,
x
(
0
)
,
α
,
λ
(
0
)
,
μ
). By Lemma 5, for almost all (
x
(
0
)
,
α
,
λ
(
0
)
)
∈
Ω
0
(
1
)
×
R
n
×
Λ
+
+, 0 is a regular value of map H
:
R
n
×
R
+
m
×
R
l × R
p
×
(
0,1
]
→
R
n
+
m
+
l
+
p. By the inverse image theorem, H
-
1
(
0
) consists of some smooth curves. Since H
(
w
(
0
)
,
1
)
=
0, then a C
1 curve (
w
(
s
)
,
μ
(
s
)
) of dimension 1, denoted by Γ
w
(
0
), is starting from (
w
(
0
)
,
1
).
In the following, we furthermore assume that∇
h
(
x
)
T
∇
v
η
(
x
,
v
) is nonsingular. By the classification theorem of one-dimensional smooth manifolds, Γ
w
(
0
) is diffeomorphic either to a unit circle or to a unit interval. For any w
(
0
)
∈
Ω
0
(
1
)
×
R
+
+
m
×
{
0
}
×
Λ
+
+, it is easy to show that ∂
H
(
w
(
0
)
,
1
)
/
∂
w is nonsingular; thus Γ
w
(
0
) cannot be diffeomorphic to a unit circle. That is, Γ
w
(
0
) is diffeomorphic to a unit interval.
Let(
w
*
,
μ
*
) be a limit point of Γ
w
(
0
); then the following cases may occur: (a)
(
w
*
,
μ
*
)
=
(
x
*
,
u
*
,
v
*
,
λ
*
,
μ
*
)
∈
Ω
×
R
+
m
×
R
l
×
Λ
+
×
{
0
},
(b)
(
w
*
,
μ
*
)
=
(
x
*
,
u
*
,
v
*
,
λ
*
,
μ
*
)
∈
Ω
0
(
1
)
×
R
+
+
m
×
R
l
×
Λ
+
+
×
{
1
},
(c)
(
w
*
,
μ
*
)
=
(
x
*
,
u
*
,
v
*
,
λ
*
,
μ
*
)
∈
∂
(
Ω
(
μ
*
)
×
R
+
m
×
R
l
)
×
Λ
+
×
(
0,1
].
By Lemma3, the equation H
(
w
,
w
(
0
)
,
1
)
=
0 has a unique solution (
w
(
0
)
,
1
) in Ω
0
(
1
)
×
R
+
+
m
×
R
l
×
Λ
+
+
×
{
1
}, so case (b) is impossible.
It follows from Theorem 3.2 in [32] that the projection of the smooth curve Γ
w
(
0
) onto the λ-plane is bounded.
LetI
(
x
*
)
=
{
i
∈
{
1
,
…
,
m
}
:
lim
⁡
k
→
∞
u
i
(
k
)
=
∞
} and J
(
x
*
)
=
{
j
∈
{
1
,
…
,
l
}
:
lim
⁡
j
→
∞
v
j
(
k
)
=
∞
}. If J
(
x
*
)
≠
∅, from the first equation in (9), we have
(15)
(
1
-
μ
k
)
(

∇
f
(
x
(
k
)
)
λ
(
k
)
+
∑
i
∉
I
(
x
*
)
‍
(
(
1
-
μ
k
)
∇
g
i
(
x
(
k
)
)
u
i
(
k
)
+
ξ
i
hhhhhhhhhhhhhhhhhhhhhhhh
×
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)

)
)
∑
i
∉
I
(
x
*
)
‍


)
+
μ
k
(
x
(
k
)
-
x
(
0
)
)
+
(
1
-
μ
k
)
μ
k
α
+
(
1
-
μ
k
)
∇
h
(
x
(
k
)
)
v
(
k
)
+
∑
j
=
1
l
‍
η
j
(
x
(
k
)
,
μ
k
v
j
(
k
)
)
+
∑
i
∈
I
(
x
*
)
‍
(
(
1
-
μ
k
)
∇
g
i
(
x
(
k
)
)
u
i
(
k
)
hhhhhhhhhi
+
ξ
i
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)
)
=
0
.By assumptions(
C
2
) and (
C
3
), the fourth, fifth, and sixth parts in the left-hand side of (15) tend to infinity as k
→
∞, but the other three parts are bounded; this is impossible. Therefore the projection of the smooth curve Γ
w
(
0
) onto the v-plane is also bounded.If case (c) holds, then there exists a sequence of points{
(
w
(
k
)
,
μ
k
)
}
⊂
Γ
w
(
0
) such that ∥
(
w
(
k
)
,
μ
k
)
∥
→
∞. Since Ω
(
μ
), Λ
+, and (
0,1
] are bounded, hence there exists a subsequence of points (denoted also by {
(
w
(
k
)
,
μ
k
)
}) such that x
(
k
)
→
x
*, u
(
k
)
→
∞, v
(
k
)
→
v
*, λ
(
k
)
→
λ
*, and μ
k
→
μ
* as k
→
∞. From the second equation in (9), we have
(16)
g
(
x
(
k
)
)
-
μ
k
γ
(
g
(
x
(
0
)
)
+
e
m
)
=
-
μ
k
(
U
(
k
)
)
-
1
β
.
When μ
*
>
0, the active index set is
(17)
I
(
x
*
,
μ
*
)
=
{
i
∈
{
1
,
…
,
m
}
:
lim
⁡
k
→
∞
u
i
(
k
)
=
∞
}
.
When μ
*
=
0, the index set is
(18)
I
0
(
x
*
,
0
)
=
{
i
∈
{
1
,
…
,
m
}
:
lim
⁡
k
→
∞
u
i
(
k
)
=
∞
}
⊂
I
(
x
*
,
0
)
.
(1) If μ
*
=
1, from the first equation in (9), we obtain
(19)
∑
i
∈
I
(
x
*
,
1
)
‍
[
(
1
-
μ
k
)
(
1
-
μ
k
)
u
i
(
k
)
∇
g
i
(
x
(
k
)
)
h
h
h
h
h
h
+
ξ
i
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)
]
+
(
x
(
k
)
-
x
(
0
)
)
+
(
1
-
μ
k
)
∇
h
(
x
(
k
)
)
v
(
k
)
+
∑
j
=
1
l
‍
η
j
(
x
(
k
)
,
μ
k
v
j
(
k
)
)
+
(
1
-
μ
k
)
μ
k
α
=
-
∑
i
∉
I
(
x
*
,
1
)
‍
[
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)

(
1
-
μ
k
)
(
1
-
μ
k
)
u
i
(
k
)
∇
g
i
(
x
(
k
)
)
hhhhhhhhhhi
+
ξ
i
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)
]
-
(
1
-
μ
k
)
∇
f
(
x
(
k
)
)
λ
(
k
)
+
(
1
-
μ
k
)
(
x
(
k
)
-
x
(
0
)
)
.
By assumptions (
C
2
),  (
C
3
), and (19), we have
(20)
lim
⁡
k
→
∞
(
1
-
μ
k
)
u
i
(
k
)
=
u
i
*
,
where u
i
*
≧
0. Therefore by (19) and (20), we get
(21)
x
*
+
∑
i
∈
I
(
x
*
,
1
)
‍
ξ
i
(
x
*
,
u
i
*
)
+
∑
j
=
1
l
‍
η
j
(
x
*
,
v
j
*
)
=
x
(
0
)
,
which contradicts assumption (
C
4
).(2) If0
<
μ
*
<
1, from the first equation in (9), we conclude
(22)
∑
i
∈
I
(
x
*
,
μ
*
)
‍
[
(
1
-
μ
k
)
(
1
-
μ
k
)
u
i
(
k
)
∇
g
i
(
x
(
k
)
)
h
h
h
h
h
h
h
+
ξ
i
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)
]
=
-
(
1
-
μ
k
)
∇
f
(
x
(
k
)
)
λ
(
k
)
-
μ
k
(
x
(
k
)
-
x
(
0
)
)
-
(
1
-
μ
k
)
∇
h
(
x
(
k
)
)
v
(
k
)
-
∑
j
=
1
l
‍
η
j
(
x
(
k
)
,
μ
k
v
j
(
k
)
)
-
∑
i
∉
I
(
x
*
,
μ
*
)
‍
[
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)

(
1
-
μ
k
)
(
1
-
μ
k
)
u
i
(
k
)
∇
g
i
(
x
(
k
)
)
hhhhhhhhhhhh
+
ξ
i
(
x
(
k
)
,
μ
k
(
1
-
μ
k
)
u
i
(
k
)
)
]
-
(
1
-
μ
k
)
μ
k
α
.
When k
→
∞, since Ω
(
μ
*
) and u
i
(
k
)
,
i
∉
I
(
x
*
,
μ
*
), are bounded, the right-hand side of (22) is bounded. But by assumption (
C
2
), if u
i
(
k
)
→
∞
,
i
∈
I
(
x
*
,
μ
*
), then the left-hand side of (22) is infinite. This results in a contradiction.(3) Ifμ
*
=
0, since the nonempty index set I
0
(
x
*
,
0
)
⊂
I
(
x
*
,
0
), the proof is similar to (2).By the above discussion, we obtain that case (a) is the only possible case, and thus thex-component of w
* is a KKT point of (1).For almost allw
(
0
)
∈
R
n
×
R
+
+
m
×
{
0
}
×
Λ
+
+, by Theorem 6, the homotopy generates a C
1 curve Γ
w
(
0
); by differentiating the first equation in (13), we get the following theorem.Theorem 7.
The homotopy pathΓ
w
(
0
) is determined by the following initial value problem to the ordinary differential equation:
(23)
D
H
(
w
(
s
)
,
μ
(
s
)
)
(
w
˙
(
s
)
μ
˙
(
s
)
)
=
0
,
(
w
(
0
)
,
μ
(
0
)
)
=
(
w
(
0
)
,
1
)
,
where s is the arclength of the curve Γ
w
(
0
).Based on Theorems6 and 7, various predictor-corrector procedures for numerically tracing the smooth homotopy path Γ
w
(
0
) can be given (see [33, 34] and references therein).


## 3. Numerical Results

By using the homotopy (9) and the predictor-corrector algorithm, several numerical examples are given to illustrate the work in this paper. To illustrate that our result is an extension of the work in [32], we choose some examples whose feasible sets do not satisfy the normal cone condition but satisfy assumptions (
C
1
)
–
(
C
4
). In addition, the initial points are chosen not certainly to be in the interior of the feasible sets. In each example, we set ϵ
1
=
1
·
e
-
3, ϵ
2
=
1
·
e
-
6, and h
0
=
0.02. The behaviors of homotopy paths are shown in Figures 2, 3, 4, and 5. Computational results are given in Table 1, where x
(
0
) denotes the initial point, IT the number of iterations, H the value of ∥
H
w
(
0
)
(
w
(
k
)
,
μ
k
)
∥ when the algorithm stops, and x
* the KKT point.Table 1
Numerical results of Examples1–4.
Example
x
(
0
)
IT
μ
*
H
x
*
f
(
x
*
)
Example1
(1.5, 0.8)
23
0.000000
0.000000
(−0.123076, 0.690768)
(−1.774478, 5.888987)
(0.9, 1.2)
26
0.000000
0.000000
(−0.123064, 0.690781)
(−1.773676, 5.888962)
Example2
(2, 3)
17
0.000000
0.000000
(−0.000812, −2.000000)
(0.000001, 0.003248)
(2, −3)
21
0.000000
0.000000
(0.000861, −2.000000)
(0.000001, −0.003444)
Example3
(5, 19)
25
0.000000
0.000000
(3.148448, 0.274224)
(13.160018, 0.987923)
(4.5, 12)
22
0.000000
0.000000
(3.148456, 0.274232)
(13.160109, 0.987978)
Example4
(10, 2)
19
0.000000
0.000000
(2.587977, 0.618034)
(7.079591, 15.269080)
(20, 7)
20
0.000000
0.000000
(2.587984, 0.618042)
(7.079637, 15.305130)Figure 2
The discrete homotopy pathways of Example1.Figure 3
The discrete homotopy pathways of Example2.Figure 4
The discrete homotopy pathways of Example3.Figure 5
The discrete homotopy pathways of Example4.Example 1 (adapted from [25, Example 3.1]).
f
(
x
), g
(
x
), and h
(
x
) are defined as in problem (1). The objective functions are given by
(24)
f
1
(
x
)
=
2
(
x
1
-
3
)
3
+
(
x
2
+
7
)
2
,
f
2
(
x
)
=
(
x
1
-
2
)
2
+
2
x
2
.
The feasible set is given by
(25)
Ω
=
{
(
x
1
,
x
2
)
∈
R
2
:
x
1
2
+
x
2
2
-
4
≦
0
,
-
(
x
1
+
2
)
2
-
x
2
2
+
4
≦
0
,
(
x
1
-
0.6
)
2
+
x
2
2
-
1
=
0
}
.
Since ∇
h
(
x
)
=
(
2
(
x
1
-
0.6
)
,
2
x
2
)
T, it is easy to see assumption (
A
3
) is not satisfied at most points in Ω
0. Therefore, the method presented in [32] can not be used to solve this example. However, if we introduce C
2 mappings ξ
1
(
x
,
u
1
)
=
(
2
x
1
u
1
,
2
x
2
u
1
)
T, ξ
2
(
x
,
u
2
)
=
(
-
2
(
x
1
+
2
)
u
2
,
-
2
x
2
u
2
)
T, and η
(
x
,
v
)
=
(
(
-
10
+
2
(
x
1
-
0.6
)
)
v
,
2
x
2
v
)
T, then it is easy to verify that assumptions (
C
1
)
–
(
C
4
) are satisfied in this example. Thus, we are able to solve this example via the algorithm presented in this paper. In addition, we choose two initial points arbitrarily which are not confined in the interior of the feasible sets; this is another improvement of the results in [32], which require that initial points should be confined in the interior of the feasible sets.Example 2 (adapted from [48, problem 42]).
f
(
x
), g
(
x
), and h
(
x
) are defined as in problem (1). The objective functions are given by
(26)
f
1
(
x
)
=
x
1
2
+
2
(
x
2
+
2
)
2
,
f
2
(
x
)
=
2
x
1
x
2
.
The feasible set is given by
(27)
Ω
=
{
(
x
1
,
x
2
)
∈
R
2
:
x
2
-
1.5
≦
0
,
-
x
2
-
4
≦
0
,
x
1
2
+
x
2
2
-
4
=
0
}
.
Since ∇
h
(
x
)
=
(
2
x
1
,
2
x
2
)
T, it is easy to see assumption (
A
3
) is not satisfied at most points in Ω
0. Therefore, the method presented in [32] can not be used to solve this example. However, if we introduce C
2 mappings ξ
1
(
x
,
u
1
)
=
(
0
,
u
1
)
T, ξ
2
(
x
,
u
2
)
=
(
0
,
-
u
2
)
T, and η
(
x
,
v
)
=
(
2
x
1
v
,
(
8
+
2
x
2
)
v
)
T, then it is easy to verify that assumptions (
C
1
)
–
(
C
4
) are satisfied in this example. Thus, we are able to solve this example via the algorithm presented in this paper. In addition, we choose two initial points arbitrarily which are not confined in the interior of the feasible sets; this is another improvement of the results in [32], which require that initial points should be confined in the interior of the feasible sets.Example 3 (adapted from [48, problem 56]).
f
(
x
), g
(
x
), and h
(
x
) are defined as in problem (1). The objective functions are given by
(28)
f
1
(
x
)
=
x
1
2
+
2
(
x
2
+
1
)
2
,
f
2
(
x
)
=
x
1
2
+
x
2
2
.
The feasible set is given by
(29)
Ω
=
{
(
x
1
,
x
2
)
∈
R
2
:
x
1
-
2
π
≦
0
,
π
-
x
1
≦
0
,
x
2
-
20
sin
⁡
(
2
x
1
)
=
0
(
x
1
,
x
2
)
∈
R
2
}
.
Since ∇
h
(
x
)
=
(
-
40
cos
⁡
(
2
x
1
)
,
1
)
T, it is easy to see assumption (
A
3
) is not satisfied at most points in Ω
0. Therefore, the method presented in [32] can not be used to solve this example. However, if we introduce C
2 mappings ξ
1
(
x
,
u
1
)
=
(
u
1
,
0
)
T, ξ
2
(
x
,
u
2
)
=
(
-
u
2
,
0
)
T, and η
(
x
,
v
)
=
(
0,10
v
)
T, then it is easy to verify that assumptions (
C
1
)
–
(
C
4
) are satisfied in this example. Thus, we are able to solve this example via the algorithm presented in this paper. In addition, we choose two initial points arbitrarily which are not confined in the interior of the feasible sets; this is another improvement of the results in [32], which require that initial points should be confined in the interior of the feasible sets.Example 4 (adapted from [48, problem 79]).
f
(
x
), g
(
x
), and h
(
x
) are defined as in problem (1). The objective functions are given by
(30)
f
1
(
x
)
=
x
1
2
+
x
2
2
,
f
2
(
x
)
=
2
x
1
2
+
(
x
2
-
2
)
2
.
The feasible set is given by
(31)
Ω
=
{
(
x
1
,
x
2
)
∈
R
2
:
-
x
2
-
6
≦
0
,
x
2
-
6
≦
0
,
3
x
1
-
2
x
2
2
-
7
=
0
}
.
Since ∇
h
(
x
)
=
(
3
,
-
4
x
2
)
T, it is easy to see assumption (
A
3
) is not satisfied at most points in Ω
0. Therefore, the method presented in [32] can not be used to solve this example. However, if we introduce C
2 mappings ξ
1
(
x
,
u
1
)
=
(
0
,
-
u
1
)
T, ξ
2
(
x
,
u
2
)
=
(
0
,
u
2
)
T, and η
(
x
,
v
)
=
(
10
v
,
0
)
T, then it is easy to verify that assumptions (
C
1
)
–
(
C
4
) are satisfied in this example. Thus, we are able to solve this example via the algorithm presented in this paper. In addition, we choose two initial points arbitrarily which are not confined in the interior of the feasible sets; this is another improvement of the results in [32], which require that initial points should be confined in the interior of the feasible sets.Although the feasible sets of Examples1–4 do not satisfy the normal cone condition in [32] and initial points are chosen not in the interior of the feasible sets, the numerical results for these examples can illustrate that the algorithm presented in this paper still works well.


## 4. Conclusions

In this paper, we apply proper perturbations to the constraint functions and hence develop a noninterior path following algorithm for solving a class of MOP problems. Our results extend the results in [32] to more general nonconvex sets and make initial points of the algorithm be chosen more easily than before. Since MOP problems have wide applications in engineering, management, economics, and so on, our results may be useful to propose a powerful solution tool for dealing with these practical problems. In the future, we want to propose new techniques to extend our results to more general nonconvex sets. In addition, we want to present a set of suitable unboundedness conditions to remove the boundedness assumptions on the feasible set so that we are able to solve MOP problems in unbounded sets.



---

*Source: 835819-2014-08-13.xml*