凸规划组合同伦内点法的计算复杂性
- 格式：pdf
- 大小：469.25 KB
- 文档页数：22
1
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
Abstract. In [1], [2] and [8], a combined homotopy was constructed for solving nonconvex programming and convex programming with weaker conditions, without assuming the logarithmic barrier function to be strictly convex and the solution set to be bounded. It was proven that a smooth interior path from an interior point of the feasible set to a K-K-T point of the problem exists. This shows that combined homotopy interior point methods can solve the problem that commonly used interior point methods can’t solve. However, so far, there is no result on its complexity, even for linear programming. The main difficulty is that the objective function is not monotonically decrease on the combined homotopy path. In this paper, by taking a piecewise technique, under commonly used conditions, polynomiality of a combined homotopy interior point method is given for convex nonlinear programming. Keywords. convex programming, polynomiality, homotopy method, interior-point method, path-following.
In this paper, we will discuss polynomiality of a combined homotopy interior point method for convex programming under commonly used conditions. We obtain the upper bound for the total number of iterations for the long-step path-following method and for the short-step path-following method.
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
1. Introduction
The interior point method, which began from 1950’s and has been deeply studied since Kamrarkar published his famous paper [6], has become one of the most efficient methods for solving linear programming and convex programming (see [3, 4, 5, 7], [9, 10, 11, 12, 13, 14, 15, 16, 17, 18] and references therein). In [1], [2] and [8], a combined homotopy was constructed for solving non-convex programming and convex programming with weaker conditions, without assuming the logarithmic barrier function to be strictly convex and the solution set to be bounded, and it was proven that a smooth interior path from an interior point of the feasible set to a K-K-T point of the problem exists. This shows that combined homotopy interior point methods can solve the problem that commonly used interior point methods can’t solve. But so far there is no result on its complexity, even for linear programming problems.
i=1
−yigi(x) = µ,
gi(x) ≤ 0, yi ≥ 0, i = 1, · · · , m.
(1.2)
Or, equivalently,
min{ϕ¯(x,
x∈Ω
µ)
=
(1
−
µ)f (x)
+
µ 2
||x
−
x0||2
−
µ(1
−
µ)
m
ln(−gi(x))}
i=1
1
(1.3).
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
supplying the additional constraint f (x) ≤ f (x¯) to (1.1) will make the feasible region bounded.
_______________________________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
On the Complexity of a Combined Homotopy Interior Point Method for Convex Programming ∗
The smooth interior path defined by them is called the combined homotopy path.
For convenience, we denote
ϕ(x, µ)
=
ϕ¯(x, µ) µ(1 − µ)
=
f (x) µ
+
||x − x0||2 2(1 − µ)
Definition1.3. A function ϕ : Ω0 → R is called κ-self-concordant on Ω0, κ ≥ 0, if ϕ is
three times continuously differentiable in Ω0 and for all x ∈ Ω0 and h ∈ Rn the following
−
m
ln(−gi(x)).
i=1
It is clear that for any µ ∈ (0, 1) the minimal point of ϕ(x, µ) is the same as that of
ϕ¯(x, µ), and (1.2) is equivalent to the following system
Bo Yu
Department of Applied Mathematics, Dalian University of Technology Dalian, Liaoning 116024, P.R. China, yubo@
Qing Xu
Naval Submarine Academy, Qingdao, Shandong 266071, otxq@
Ω0
=
{x
∈
Rn:
gi(x)
<
0
(i
=
1,
2,
.
.
.
,
m)}
be
its
strictly
feasible
region,
let
f∗
=
inf
x∈Ω
f (x).
The combined homotopy used in [1], [2] and [8] is as follows:
m
(1 − µ)∇f (x) + (1 − µ) yi∇gi(x) + µ(x − x0) = 0,
inequality holds
3 |∇3ϕ(x)[h, h, h]| ≤ 2κ(hT ∇2ϕ(x)h) 2
where ∇3ϕ(x)[h, h, h] denotes the third differential of ϕ at x and h, i.e.,
∇3ϕ(x)[h, h, h]
=
∂
∂3 t1∂t2
∂
t3
ϕ(x
+
t1h1
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
Abstract. In [1], [2] and [8], a combined homotopy was constructed for solving nonconvex programming and convex programming with weaker conditions, without assuming the logarithmic barrier function to be strictly convex and the solution set to be bounded. It was proven that a smooth interior path from an interior point of the feasible set to a K-K-T point of the problem exists. This shows that combined homotopy interior point methods can solve the problem that commonly used interior point methods can’t solve. However, so far, there is no result on its complexity, even for linear programming. The main difficulty is that the objective function is not monotonically decrease on the combined homotopy path. In this paper, by taking a piecewise technique, under commonly used conditions, polynomiality of a combined homotopy interior point method is given for convex nonlinear programming. Keywords. convex programming, polynomiality, homotopy method, interior-point method, path-following.
In this paper, we will discuss polynomiality of a combined homotopy interior point method for convex programming under commonly used conditions. We obtain the upper bound for the total number of iterations for the long-step path-following method and for the short-step path-following method.
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
1. Introduction
The interior point method, which began from 1950’s and has been deeply studied since Kamrarkar published his famous paper [6], has become one of the most efficient methods for solving linear programming and convex programming (see [3, 4, 5, 7], [9, 10, 11, 12, 13, 14, 15, 16, 17, 18] and references therein). In [1], [2] and [8], a combined homotopy was constructed for solving non-convex programming and convex programming with weaker conditions, without assuming the logarithmic barrier function to be strictly convex and the solution set to be bounded, and it was proven that a smooth interior path from an interior point of the feasible set to a K-K-T point of the problem exists. This shows that combined homotopy interior point methods can solve the problem that commonly used interior point methods can’t solve. But so far there is no result on its complexity, even for linear programming problems.
i=1
−yigi(x) = µ,
gi(x) ≤ 0, yi ≥ 0, i = 1, · · · , m.
(1.2)
Or, equivalently,
min{ϕ¯(x,
x∈Ω
µ)
=
(1
−
µ)f (x)
+
µ 2
||x
−
x0||2
−
µ(1
−
µ)
m
ln(−gi(x))}
i=1
1
(1.3).
__中__国__科__技__论__文__在__线_______________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
supplying the additional constraint f (x) ≤ f (x¯) to (1.1) will make the feasible region bounded.
_______________________________________________________________w_w_w__.p_a_p_e_r_.e_d_u_._c_n__
On the Complexity of a Combined Homotopy Interior Point Method for Convex Programming ∗
The smooth interior path defined by them is called the combined homotopy path.
For convenience, we denote
ϕ(x, µ)
=
ϕ¯(x, µ) µ(1 − µ)
=
f (x) µ
+
||x − x0||2 2(1 − µ)
Definition1.3. A function ϕ : Ω0 → R is called κ-self-concordant on Ω0, κ ≥ 0, if ϕ is
three times continuously differentiable in Ω0 and for all x ∈ Ω0 and h ∈ Rn the following
−
m
ln(−gi(x)).
i=1
It is clear that for any µ ∈ (0, 1) the minimal point of ϕ(x, µ) is the same as that of
ϕ¯(x, µ), and (1.2) is equivalent to the following system
Bo Yu
Department of Applied Mathematics, Dalian University of Technology Dalian, Liaoning 116024, P.R. China, yubo@
Qing Xu
Naval Submarine Academy, Qingdao, Shandong 266071, otxq@
Ω0
=
{x
∈
Rn:
gi(x)
<
0
(i
=
1,
2,
.
.
.
,
m)}
be
its
strictly
feasible
region,
let
f∗
=
inf
x∈Ω
f (x).
The combined homotopy used in [1], [2] and [8] is as follows:
m
(1 − µ)∇f (x) + (1 − µ) yi∇gi(x) + µ(x − x0) = 0,
inequality holds
3 |∇3ϕ(x)[h, h, h]| ≤ 2κ(hT ∇2ϕ(x)h) 2
where ∇3ϕ(x)[h, h, h] denotes the third differential of ϕ at x and h, i.e.,
∇3ϕ(x)[h, h, h]
=
∂
∂3 t1∂t2
∂
t3
ϕ(x
+
t1h1
