Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications
Подождите немного. Документ загружается.
336 P. Krokhmal et al.
Of particular interest is the linear separating surface (hyperplane):
f(x) =w
x −γ =0 (18.1)
Clearly, existence of such a separating hyperplane is not guaranteed;
1
in general, a
separating hyperplane that minimizes some sort of misclassification error is desired.
Observe that if points y
(1)
, y
(2)
∈R
n
satisfy the inequalities
w
y
(1)
−γ>0, w
y
(2)
−γ<0
for some w and γ , then they are located on the opposite sides of the hyperplane
w
x − γ = 0. Consequently, the discrete sets A, B ⊂ R
n
are considered linearly
separable if and only if there exists w ∈R
n
such that
w
a
i
>γ >w
b
j
for all i =1,...,k, j =1,...,m
with an appropriately chosen γ , or, equivalently,
min
a
i
∈A
a
i
w > max
b
j
∈B
b
j
w (18.2)
Definition (18.2) is not amenable for use in mathematical programming models
since it involves strict inequalities. However, the fact that the separating hyperplane
can be scaled by any nonnegative factor allows one to formulate the following result,
whose proof we include for completeness of exposition.
Proposition 1 (Bennett and Mangasarian [5]) Discrete sets A, B ⊂R
n
represented
by matrices A = (a
1
,...,a
k
)
∈ R
k×n
and B = (b
1
,...,b
m
)
∈ R
m×n
, respec-
tively, are linearly separable if and only if
Aw ≥eγ +e, Bw ≤eγ −e for some w ∈R
n
,γ∈R, (18.3)
where e is the vector of ones of the appropriate dimension, e =(1,...,1)
.
Proof Let A and B be linearly separable, then in accordance to definition (18.2),
there exists v ∈R
n
such that
min
i=1,...,k
a
i
v =:a
∗
>b
∗
:= max
j=1,...,m
b
j
v (18.4)
Denote w =2v/(a
∗
−b
∗
), and γ =(a
∗
+b
∗
)/(a
∗
−b
∗
); then for any a
i
∈A
a
i
w −γ −1 =
2
a
∗
−b
∗
a
i
v −
2a
∗
a
∗
−b
∗
=
2
a
∗
−b
∗
a
i
v − min
i=1,...,m
a
i
v
≥0
which means that Aw −eγ −e ≥0. The second inequality in (18.3) follows analo-
gously.
1
It is easy to see that a separating hyperplane exists if the convex hulls of sets A and B are disjoint.
18 A p-norm Discrimination Model for Two Linearly Inseparable Sets 337
In the next section, we introduce a new linear separation model that is based on
p-order conic programming, and discuss its key properties.
18.2 The p-norm Linear Separation Model
In this chapter, we generalize the robust linear discrimination model proposed by
Bennett and Mangasarian [5].
min
1
k
e
y +
1
m
e
z (18.5a)
s.t. y ≥−Aw +eγ +e (18.5b)
z ≥Bw −eγ +e (18.5c)
z, y ≥0 (18.5d)
The linear programming model (18.5) determines a hyperplane w
∗
x −γ
∗
=0 that
minimizes the average misclassification error. Indeed, in accordance to the definition
(18.3), the points of sets A and B that violate (18.3) will correspond to the nonzero
components of vectors y and z in the constraints (18.5b) and (18.5c), respectively.
This interpretation allows us to reformulate the optimization problem (18.5)in
the form of a stochastic programming problem
min
(w,γ )∈R
n+1
E
−a
w +γ +1
+
+
E
b
w −γ +1
+
(18.6)
where a and b are uniformly distributed random vectors with support sets A and B,
correspondingly:
P{a =a
i
}=
1
k
,
P{b =b
j
}=
1
m
for all a
i
∈A, b
j
∈B (18.7)
and (x)
±
= max{0, ±x}. In this sense, the misclassification errors of points from
A and/or B can be viewed as realizations of random variables X
A
=X
A
(w,γ) and
X
B
=X
B
(w,γ), whose smaller values are preferred, and thus the parameters w and
γ must be selected so as X
A
and X
B
assume values that are “small”.
As it is well known in stochastic programming and risk analysis, the “risk” asso-
ciated with random outcome is often attributed to the “heavy” tails of the probability
distribution. The risk-inducing “heavy” tails of probability distributions, are, in turn,
characterized by the distribution’s higher moments. Thus, if the misclassifications
introduced by a separating hyperplane can be viewed as “random”, the misclassi-
fication risk may be controlled better if one minimizes not the average (expected
value) of the misclassification errors, but their moments of order p>1. This gives
rise to the following formulation for linear discrimination of sets A and B:
min
(w,γ )∈R
n+1
δ
1
−a
w +γ +1
+
p
+δ
2
b
w −γ +1
+
p
,p∈[1, +∞]
(18.8)
338 P. Krokhmal et al.
where ·
p
is the “functional” L
p
norm, which in the probabilistic context can be
written as
X
p
=
E|X|
p
1/p
,p∈[1, ∞)
sup|X|,p=∞
Assuming again that points of the sets A and B are “equiprobable” (or, in other
words, all points of set A, and, correspondingly, B , have equal “importance”), linear
discrimination problem (18.8) can be written as follows
min δ
1
k
−1/p
ξ +δ
2
m
−1/p
η (18.9a)
s.t. ξ ≥y
p
(18.9b)
η ≥z
p
(18.9c)
y ≥−Aw +eγ +e (18.9d)
z ≥Bw −eγ +e (18.9e)
z, y ≥0,ξ,η≥0 (18.9f)
In the mathematical programming formulation (18.9), ·
p
denotes the “vector”
norm in finite-dimensional space, i.e., for x ∈R
n
,
x
p
=
|x
1
|
p
+···+|x
n
|
p
1/p
,p∈[1, ∞)
max
|x
1
|,...,|x
n
|
,p=∞
(in the sequel, it shall be clear from the context whether the “functional” or “vector”
definition of p-norm is used).
Model (18.9) constitutes a linear programming problem with p-order conic con-
straints (18.9b)–(18.9c). Using the “vector” norm notation, formulation (18.9) can
be more succinctly presented as
min
(w,γ )∈R
n+1
δ
1
k
1/p
(−Aw +eγ +e)
+
p
+
δ
2
m
1/p
(Bw −eγ +e)
+
p
(18.10)
The p-conic programming linear separation model (18.8)–(18.9) shares many
key properties with the LP separation model of Bennett and Mangasarian [5], in-
cluding the guarantee that the optimal solution of (18.9) is nonzero in w for linearly
separable sets.
Proposition 2 When sets A and B, represented by matrices A and B, are linearly
separable (i.e., they satisfy (18.2) and (18.3)), the separating hyperplane w
∗
x =
γ
∗
given by an optimal solution of (18.8)–(18.9) satisfies w
∗
=0.
Proof Zero optimal value of (18.9a) immediately implies that at optimality y
∗
=
z
∗
=0, or, equivalently,
−Aw
∗
+eγ
∗
+e ≤0, Bw
∗
−eγ
∗
+e ≤0
18 A p-norm Discrimination Model for Two Linearly Inseparable Sets 339
If one assumes that w
∗
=0, then the above inequalities require that
γ
∗
≤−1,γ
∗
≥1
The contradiction furnishes the desired statement.
Secondly, the p-norm separation model (18.9) can produce a w =0 solution only
in a rather special case that is identified by Theorem 1 below.
Theorem 1 Assume that the p-order conic programming problem (18.9)–(18.10)
is strictly feasible and, without loss of generality,0<δ
1
<δ
2
. Then, for any
p ∈ (1, ∞) the p-order conic programming problem (18.9) has an optimal solu-
tion where w
∗
=0 if and only if
e
k
A =v
B, where e
v =1, v ≥0, v
q
≤
δ
2
δ
1
m
1/p
(18.11a)
where q satisfies
1
p
+
1
q
= 1. In other words, the arithmetic mean of the points in
A must be equal to some convex combination of points in B. In the case of δ
1
=δ
2
condition,(18.11a) reduces to
e
k
A =
e
m
B (18.11b)
i.e., the arithmetic means of the points of sets A and B must coincide.
Proof From formulation (18.10) of problem (18.9), it follows that in the case when
w = 0 at optimality, the corresponding optimal value of the objective (18.9a)is
determined as
min
γ ∈R
f(γ)=
δ
1
k
1/p
k
i=1
(1 +γ)
p
+
1/p
+
δ
2
m
1/p
m
j=1
(1 −γ)
p
+
1/p
Clearly,
f(γ)=
⎧
⎨
⎩
δ
1
(1 +γ), γ ≥1,
δ
1
+δ
2
+γ(δ
1
−δ
2
), −1 <γ <1,
δ
2
(1 −γ), γ ≤−1
whence
min
γ ∈R
f(γ)=f(1) =2δ
1
(18.12)
340 P. Krokhmal et al.
due to the assumption 0 <δ
1
<δ
2
. Next, consider the dual of the p-conic program-
ming problem (18.9):
max e
u +e
v
s.t. −A
u +B
v =0
e
u −e
v =0
0 ≤u ≤−s
0 ≤v ≤−t
s
q
≤δ
1
k
−1/p
t
q
≤δ
2
m
−1/p
(18.13)
where q is such that
1
p
+
1
q
=1. Since (18.9) is strictly feasible and bounded from
below, the duality gap for the primal-dual pair of p-order conic programming prob-
lems (18.9) and (18.13) is zero. Then, from the first two constraints of (18.13), we
have A
u
∗
=B
v
∗
as well as e
u
∗
=e
v
∗
, which given that the optimal objective
value (18.13)is2δ
1
, implies that an optimal u
∗
must satisfy
e
u
∗
=δ
1
(18.14a)
Also, from (18.13) it follows that
u
∗
q
≤δ
1
k
−1/p
(18.14b)
Then, it is easy to see that the unique solution of system (18.14)is
u
∗
=
δ
1
k
e =
δ
1
k
,...,
δ
1
k
(18.15)
which corresponds to the point where the surface (u
q
1
+···+u
q
k
)
1/q
= δ
1
k
−1/p
is
tangent to the hyperplane u
1
+···+u
k
=δ
1
in the positive orthant of R
k
.
Similarly, an optimal v
∗
must satisfy e
v
∗
= δ
1
and v
∗
q
≤ δ
2
m
−1/p
. Note,
however, that in the case when δ
2
/δ
1
> 1 such v
∗
is not unique. By substituting the
obtained characterizations for u
∗
and v
∗
in the constraint A
u
∗
=B
v
∗
of the dual
(18.13) and dividing by δ
1
, we obtain (18.11a). When δ
1
= δ
2
, the optimal v
∗
is
unique: v
∗
=
δ
1
m
e, and yields (18.11b).
Observe that Theorem 1 implies that in the case of δ
1
=δ
2
(i.e., when misclassi-
fication of points in one set is not favored over that for points of the other set), the
p-norm discrimination model (18.9) produces a separating hyperplane with w = 0
only when the “geometric centers” (arithmetic means) of the sets A and B coincide.
In many situations, this would mean that there is significant “overlap” between the
convex hulls of sets A and B. In practice, this means that such sets, indeed, cannot
be efficiently separated, at least by a hyperplane, thus occurrence of w
∗
=0 solution
in (18.9) should not be regarded as the shortfall of the particular formulation (18.9),
18 A p-norm Discrimination Model for Two Linearly Inseparable Sets 341
but rather the general inapplicability of the linear discrimination method to the spe-
cific sets A and B.
In the case when a “bias” with regard to the importance of misclassification of
points of sets A and B needs to be introduced by setting δ
2
>δ
1
, occurrence of a
w
∗
= 0 solution in (18.9) does not necessarily imply that sets A and B are hardly
amenable to linear separation. Indeed, in this case Theorem 1 only claims that the
“geometric center” of set A must coincide with some convex combination of points
of set B, i.e., it must coincide with some point inside the convex hull of set B.In
this case, linear discrimination can still be a feasible approach, albeit at a cost of
significant misclassification errors.
In order to have the stricter condition (18.11b) for the occurrence of w
∗
= 0
solution in the situation when the preferences for misclassification error are different
for sets Aand B,thep-norm linear discrimination model can be extended to the case
where misclassifications of points in Aand B are measured using norms of different
orders:
min
(w,γ )∈R
n+1
k
−1/p
1
(−Aw +eγ +e)
+
p
1
+m
−1/p
2
(Bw −eγ +e)
+
p
2
,
p
1,2
∈[1, ∞) (18.16)
Intuitively, a norm of higher order places more “weight” on outliers; indeed, ap-
plication of the p =1 norm would minimize the average misclassification error, in
effect regarding all misclassifications as equally important. In contrast, application
of the p =∞norm would minimize the largest misclassification error. Thus, by
selecting appropriately the orders p
1
and p
2
in (18.16) one may introduce tolerance
preferences on misclassifications in sets A and B. At the same time, it can be shown
that the occurrence of w
∗
= 0 solution in (18.16) would signal the presence of the
aforementioned singularity about the sets A, B. Namely, we have the following
corollary.
Corollary 1 The statement of Theorem 1 carries over to model (18.16) practically
without modifications.
In the next section, we discuss the details of practical implementation of the p-
norm linear discrimination model (18.9).
18.3 Implementation of p-order Conic Programming Problems
via Polyhedral Approximations
Constraints (18.9b)–(18.9c)inthep-norm linear separation model (18.9) consti-
tute p-order cones in R
m+1
and R
k+1
, correspondingly, and are central to practical
implementation of the p-norm separation method. Depending on the value of the
parameter p, the following cases can be identified.
342 P. Krokhmal et al.
p =1: in this case, given the nonnegativity of variables y, z, constraints (18.9b)–
(18.9c) reduce to linear inequalities
ξ ≥e
y,η≥e
z.
This particular case has been considered in [5]; in general, the amenability of the
1-norm, also known as the “Manhattan distance”, etc., to implementation via lin-
ear constraints has been exploited in a of variety approaches and applications, too
numerous to cite here.
p =∞: in this case x
∞
= max
i
|x
i
|, whereby the conic constraints (18.9b)–
(18.9c) reduce to a system of m +k inequalities
eξ ≥y, eη ≥z
Due to the linearity of the above constraints, we do not pursue this case further, as
our main interest is in models with “true” (or nonlinear) p-cone constraints.
p ∈ (1, ∞): this is the “general” case that constitutes the focus of the present
endeavor. In addition to the data mining application described above, the general
p-order conic programming has been considered in the context of Steiner minimum
tree problem on a given topology [19], stochastic programming and risk optimiza-
tion [8, 9]; an application of p-order conic programming to integer programming
problems is discussed in [6].
Of particular importance is the case p =2, when the constraints (18.9b)–(18.9c)
represent second-order (quadratic, “ice cream”, or Lorentz) cones,
ξ ≥y
2
=
y
y
1/2
η ≥z
2
=
z
z
1/2
(18.17)
The second-order conic programming (SOCP), which deals with optimization prob-
lems that contain constraints of form (18.17), constitutes a well-developed subject
of convex programming. A number of efficient SOCP algorithms have been devel-
oped in the literature (e.g., [12, 13], and others, see an overview in [1]), and some
of them were implemented into software solver codes such as MOSEK, SeDuMi
[2, 15].
From the computational standpoint, the case of general p, when the cone is not
self-dual, has received much less attention in the literature compared to the conic
quadratic programming. Interior-point approaches to p-order conic programming
have been considered by Xue and Ye [19] with respect to minimization of sum of
p-norms; a self-concordant barrier for p-cone has also been introduced in [10].
Glineur and Terlaky [7] proposed an interior point algorithm along with the cor-
responding barrier functions for a related problem of l
p
-norm optimization (see
also [17]). In the case when p is a rational number, the existing primal-dual methods
of SOCP can be employed for solving p-order conic optimization problems using a
reduction of p-order conic constraints to a system of linear and second-order conic
constraints proposed in [11] and [3].
18 A p-norm Discrimination Model for Two Linearly Inseparable Sets 343
Our approach to handling p-order conic constraints (18.9b)–(18.9c) in the case
of p ∈ (1, 2) ∪(2, +∞) consists in constructing of polyhedral approximations for
the p-order constraints and thus reducing the p-norm linear separation problem
(18.9) to an LP. In many respects, the proposed approach builds upon the work
of Ben-Tal and Nemirovski [4] where an efficient lifted polyhedral approximation
for the second-order (p = 2) cones was developed, and whose motivation was to
devise a practical method of solving problems with second-order conic constraints
that would utilize the powerful machinery of LP solvers. Recently, Ben-Tal and
Nemirovski’s polyhedral approximation has been proven very effective in solving
mixed integer conic quadratic problems in [18].
18.3.1 Polyhedral Approximations of p-order Cones
The proposed approach to solving the p-norm linear separation model (18.9)is
based on the construction of polyhedral approximations for p-order conic con-
straints. Without loss of generality, we restrict our attention to a p-order cone in
the positive orthant of (N +1)-dimensional space:
K
(N+1)
p
=
x ∈R
N+1
+
x
N+1
≥
x
p
1
+···+x
p
N
1/p
(18.18)
where R
+
=[0, +∞). By a polyhedral approximation of K
(N+1)
p
, we understand a
(convex) polyhedral cone in R
N+1+κ
m
, where κ
m
may be generally nonzero:
H
(N+1)
p,m
=
x
u
∈R
N+1+κ
m
+
H
(N+1)
p,m
x
u
≥0
(18.19)
having the properties that
(H1) Any x ∈K
(N+1)
p
can be extended to some (x, u) ∈H
(N+1)
p,m
(H2) For some prescribed ε>0, any (x, u) ∈H
(N+1)
p,m
satisfies
x
p
1
+···+x
p
N
1/p
≤(1 +ε)x
N+1
(18.20)
Here, m is the parameter of construction that controls the approximation error ε.
In constructing the polyhedral approximations (18.19)forp-order cone (18.18),
we follow the approach of Ben-Tal and Nemirovski [4](seealso[3, 11]), which
allows for reducing the dimensionality of approximation (18.19) by replacing the
(N +1)-dimensional conic constraint with an equivalent system of 3-dimensional
conic constraints, and then constructing a polyhedral approximation for each of the
3D cones.
344 P. Krokhmal et al.
18.3.2 “Tower-of-Variables” (Ben-Tal and Nemirovski [4])
The “tower-of-variables” technique has been originally proposed by Ben-Tal and
Nemirovski [4] for construction of a polyhedral approximation for quadratic (p =2)
cones, but it applies to p-order cones as well. Assuming that N = 2
d
for some
integer d,ap-cone in R
N+1
x
N+1
≥
x
p
1
+···+x
p
N
1/p
(18.21)
can equivalently be represented as an intersection of three-dimensional p-cones in
a higher-dimensional space R
2N−1
x
()
j
≥
x
(−1)
2j−1
,x
(−1)
2j
p
,j=1,...,2
d−
,=1,...,d (18.22)
The set of constraints (18.22) can be visualized as a “tower” or “pyramid” consisting
of d +1 “levels” denoted by the superscript = 0,...,d, with 2
d−
variables x
()
j
at level , such that the 2
d
= N variables x
(0)
j
≡ x
j
represent the “foundation” of
the “tower”, and the variable x
(d)
1
≡x
N+1
represents its “top”.
Observe that the number of three-dimensional p-cones in the “tower-of-
variables” representation (18.22)of(2
d
+1)-dimensional p-order cone is 2
d
−1 =
N −1. Further, it is easy to demonstrate that a “tower-of-variables” representation
can be constructed for p-order cones of general dimension N = 2
d
, such that the
number of resulting three-dimensional p-cones is still N −1.
Proposition 3 For any integer N>2,ap-order cone in R
N+1
can be represented
as intersection of N −1 three-dimensional p-order cones.
Proof For an integer N>2, let
N =
¯
d
k=0
π
k
2
k
(18.23)
where
¯
d =log
2
N
and π
k
∈{0, 1}, i.e., π
k
is the k-th digit in the binary representation of the integer N.
Let Π
N
denote the (ordered) set of those k in (18.23)forwhichπ
k
are nonzero:
Π
N
={k
0
<k
1
< ···<k
s−1
|δ
k
i
=1},s=|Π
N
|=
¯
d
k=1
π
k
(18.24)
Then, for each k such that 1 ≤ k ≤
¯
d and π
k
= 0, the following conic inequalities
can be written:
18 A p-norm Discrimination Model for Two Linearly Inseparable Sets 345
x
()
j
≥
x
(−1)
2j−1
p
+
x
(−1)
2j
p
1/p
,
j =1 +
¯
d
r=k+1
π
r
2
r−
,...,
¯
d
r=k
π
r
2
r−
,=1,...,k, k ∈Π
N
\{0} (18.25)
For every k ∈ Π
N
\{0} expressions (18.25) define a “sub-tower of variables”, each
having k +1 “levels” including the “foundation” ( =0) comprised of 2
k
variables
x
(0)
j
and the “top” variable
x
(k)
j
k
, where j
k
=
¯
d
r=k
π
r
2
r−k
(18.26)
To complete our representation of (N + 1)-dimensional p-order cone, we must
formulate the corresponding conic inequalities that “connect” the “top” vari-
ables (18.26). This can be accomplished in a recursive manner as follows
x
(κ
r+1
)
ν
r+1
≥
x
(k
r
)
j
k
r
p
+
x
(κ
r
)
ν
r
p
1/p
,r=1,...,
¯
d−2
k=0
π
k
(18.27)
where
κ
1
=k
0
,ν
1
=j
k
0
and
κ
r+1
=k
r
+1,ν
r+1
=
j
k
r
+1
2
for r =1,...,
¯
d−2
k=0
π
k
It is straightforward to verify that the projection of the set defined by (18.25), (18.27)
on the space of variables x
(0)
j
≡ x
j
, (j = 1,...,N), x
(
¯
d)
1
= x
N+1
is equal to the
set (18.21). It is also evident that when N = 2
d
= 2
¯
d
,thesetΠ
N
will contain just
one element: Π
N
={
¯
d}, whereby (18.25) reduces to (18.22) with cones (18.27)
being absent.
Observe that set (18.25) comprises
¯
d
k=1
π
k
“sub-towers”, each containing 2
k
−
1 cones, and set (18.27) consists of
¯
d−2
k=1
π
k
cones, therefore the representation
(18.25), (18.27)ofthep-order cone in R
N+1
contains
¯
d
k=1
π
k
2
k
−1
+
¯
d−2
k=1
π
k
=
¯
d
k=1
π
k
2
k
−π
¯
d−1
−π
¯
d
=N −1 (18.28)
three-dimensional p-order cones. Indeed,
π
¯
d
−1
+π
¯
d
=1
since π
¯
d
=1, π
¯
d
−1
=0ifN =2
d
=2
¯
d
, whereas π
¯
d
=0, π
¯
d
−1
=1forN<2
¯
d
.