# An Interior Point Method forL1/2-SVM and Application to Feature Selection in Classification

Authors: Lan Yao; Xiongji Zhang; Dong-Hui Li; Feng Zeng; Haowen Chen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper studies feature selection for support vector machine (SVM). By the use of theL1/2 regularization technique, we propose a new model L1/2-SVM. To solve this nonconvex and non-Lipschitz optimization problem, we first transform it into an equivalent quadratic constrained optimization model with linear objective function and then develop an interior point algorithm. We establish the convergence of the proposed algorithm. Our experiments with artificial data and real data demonstrate that the L1/2-SVM model works well and the proposed algorithm is more effective than some popular methods in selecting relevant features and improving classification performance.


---

## Body

## 1. Introduction

Feature selection plays an important role in solving the classification problems with high dimension features, such as text categorization [1, 2], gene expression array analysis [3–5], and combinatorial chemistry [6, 7]. The advantages of feature selection include (i) ignoring noisy or irrelevant features would prevent overfitting and improve the generalization performance; (ii) a sparse classifier can reduce the computation cost; (iii) a small set of important features is desirable for interpretability.We address the embedded feature selection methods in the context of linear support vector machines (SVMs). Existing feature selection methods embedded in SVMs fall into three approaches [8]. In the first approach, some greedy search strategies are applied to iteratively adding or removing features from the data. Guyon et al. [3] developed a recursive feature elimination (RFE) algorithm, which has shown good performance on gene selection for microarray data. Beginning with the full feature subset, SVM-RFE trains a SVM at each iteration, and then eliminates the feature that decreases the margin the least. Rakotomamonjy et al. [9] extended this method by using other ranking criteria including the radius margin bound and the span-estimate.The second approach is to optimize a scaling parameter vectorσ∈[0,1]n that indicates the importance of each feature. Weston et al. [10] proposed an iterative method to optimize the scaling parameters by minimizing the bounds on leave-one-out error. Peleg and Meir [11] learned the scaling factors based on the global minimization of a data-dependent generalization error bound.The third category of approaches is to minimize the number of features by adding a sparsity term to the SVM formulation. Though standard SVM based on∥w∥2 can be solved easily by convex quadratic programming, its solution may not be a desirable sparse solution. A popular way to deal with this problem is the use of Lp regularization technique, which results in a Lp-SVM. It is to minimize ∥w∥p, subject to some linear constraints, where p∈[0,1]. When p∈(0,1],
(1)∥w∥p=(∑j=1m‍|wi|p)1/p.
When p=0, ∥w∥0=∑j=1m‍I(wj≠0). The L0-SVM can find the sparsest classifier by minimizing ∥w∥0, the number of nonzero elements in w. However, it is discrete and NP-hard. From computational point of view, it is very difficult to develop efficient numerical methods to solve the problem. A widely used technique in dealing with the L0-SVM is to use a smoothing technique so that the discrete model is approached by a smooth problem [4, 12, 13]. However, as the function ∥w∥0 is not even continuous, it is not desirable that a smoothing technique based method would work well. Chan et al. [14] explored a convex relaxation to the cardinality constraint and obtained a relaxed convex problem that is close to but different from the previous L0-SVM. An alternative method is to minimize the convex envelope of the ∥w∥0, such as L1-SVM. The L1-SVM is a convex problem and can yield sparse solution. It can be equivalent to a linear programming and hence can be solved efficiently. Indeed the L1 regularization has become quite welcome in SVM [12, 15, 16] and is well known as the LASSO [17] in the statistics literature. However, the L1 regularization problem often leads to suboptimal sparsity in reality [18]. In many cases, the solutions yielded from L1-SVM are less sparse than those of L0-SVM. The Lp problem with 0<p<1 can find sparser solutions than the L1 problem, which was evidenced in extensive computational [19–21]. It has become a welcome strategy in sparse SVM [22–27].In this paper, we focus on theL1/2 regularization and propose a novel L1/2-SVM. Recently, Xu et al. [28] justified that the sparsity-promotion ability of the L1/2 problem was strongest among the Lp minimization problems with all p∈[1/2,1) and similar in p∈(0,1/2]. So the L1/2 problem can be taken as a representative of Lp (0<p<1) problems. However, as proved by Ge et al. [29], finding the global minimal value of the L1/2 problem was still strongly NP-hard. But computing a local minimizer of the problem could be done in polynomial time. Our contributions of this paper are twofold. One is to derive a smooth constrained optimization reformulation to the L1/2-SVM. The objective function of the problem is a linear function and the constraints are quadratic and linear. We will establish the equivalence between the constrained problem and the L1/2-SVM. We will also show the existence of the KKT condition of the constrained problem. Our second contribution is to develop an interior point method to solve the constrained optimization reformulation and establish its global convergence. We will also test and verify the effectiveness of the proposed method using artificial data and real data.The rest of this paper is organized as follows. In Section2, we first briefly introduce the model of the standard SVM (L2-SVM) and the sparse regularization SVMs. We then reformulate the L1/2-SVM into a smooth constrained optimization problem. We propose an interior point method to solve the constrained optimization reformulation and establish its global convergence in Section 3. In Section 4, we do numerical experiments to test the proposed method. Section 5 gives the conclusive remarks.


## 2. A Smooth Constrained Optimization Reformulation to theL1/2-SVM

In this section, after simply reviewing the model of the standard SVM (L2-SVM) and the sparse regularization SVMs, we derive an equivalent smooth optimization problem to the L1/2-SVM model. The smooth optimization problem is to minimize a linear function subject to some simple quadratic constraints and linear constraints.


### 2.1. Standard SVM

In a two-class classification problem, we are given a training data setD=(xi;yi)i=1n, where xi∈Rm is the feature vector and yi∈{0,1} is the class label. The linear classifier is to construct the following decision function:
(2)f(x)=wTx+b,
where w=(w1,w2,…,wm) is the weight vector and b is the bias. The prediction label is +1 if f(x)>0 and -1 otherwise. The standard SVM (L2-SVM) [30] aims to find the separating hyperplane f(x)=0 between two classes with maximal margin 2/∥w∥22 and minimal training errors, which leads to the following convex optimization problem:
(3)min⁡12∥w∥22+C∑i=1n‍ξis.t.yi(wTxi+b)≥1-ξii=1,…,n,ξi≥0,
where ∥w∥2=(∑j=1m‍wj2)1/2 is the L2 norm of w, ξi is the loss function to allow training errors for data that may not be linearly separable, and C is a user-specified parameter to balance the margin and the losses. As the problem is a convex quadratic program, it can be solved by existing methods, such as the interior point method and active set method efficiently.


### 2.2. Sparse SVM

TheL2-SVM is a nonsparse regularizer in the sense that the learned decision hyperplane often utilizes all the features. In practice, peoples prefer to sparse SVM so that only a few features are used to make a decision. For this purposes, the following Lp-SVM becomes very welcome:
(4)min⁡∥w∥pp+C∑i=1n‍ξis.t.yi(wTxi+b)≥1-ξii=1,…,n,ξi≥0,
where p∈[0,1]. ∥w∥0 stands for the number of nonzero elements of w, and for p∈(0,1], ∥w∥p is defined by (1). Problem (4) is obtained by replacing L2 penalty (∥w∥22) by Lp penalty (∥w∥pp) in (3). The standard SVM (3) corresponds to the model (4) with p=2.Figure1 plots the Lp penalty in one dimension. We can see from the figure that the smaller p is, the larger penalties are imposed on the small coefficients (|w|<1). Therefore, the Lp penalties with p<1 may achieve sparser solution than the L1 penalty. In addition, the L1 imposes large penalties on large coefficients, which may lead to biased estimation for large coefficients. Consequently, the Lp (0<p<1) penalties become attractive due to their good properties in sparsity, unbiasedness [31] and oracle [32]. We are particularly interested in the L1/2 penalty. Recently, Xu et al. [21] revealed the representative role of the L1/2 penalty in the Lp regularization with p∈(0,1). We will apply L1/2 penalty to SVM to perform feature selection and classification jointly.Figure 1
L
p penalty in one dimension.


### 2.3.L1/2-SVM Model

We pay particular attention to theL1/2-SVM, namely, problem (4) with p=1/2. We will derive a smooth constrained optimization reformulation to the L1/2-SVM so that it is relatively easy to design numerical methods. We first specify the L1/2-SVM:
(5)min⁡∑j=1m‍|wj|1/2+C∑i=1n‍ξi≜ϕ(w,ξ,b)s.t.yi(wTxi+b)≥1-ξi,i=1,…,n,s.t.ξi≥0,i=1,…,n.
Denote by u=(w,ξ,b) and 𝒟 the feasible region of the problem; that is,
(6)𝒟={(w,ξ,b)∣yi(wTxi+b)≥1-ξi,ξi≥0,i=1,…,n(w,ξ,b)∣yi(wTxi+b)}.
Then the L1/2-SVM can be written as an impact form
(7)min⁡ϕ(u),u∈𝒟.It is a nonconvex and non-Lipschitz problem. Due to the existence of the term|wi|1/2, the objective function is not even directionally differentiable at a point with some wi=0, which makes the problem very difficult to solve. Existing numerical methods that are very efficient for solving smooth problem could not be used directly. One possible way to develop numerical methods for solving (7) is to smoothing the term |wj|1/2 using some smoothing function such as ϕϵ(wj)=(wj2+ϵ2)1/4 with some ϵ>0. However, it is easy to see that the derivative of ϕϵ(wj) will be unbounded as wj→0 and ϵ→0. Consequently, it is not desirable that the smoothing function based numerical methods could work well.Recently, Tian and Yang [33] proposed an interior point L1/2-penalty function method to solve general nonlinear programming problems by using a quadratic relaxation scheme for their L1/2-lower order penalty problems. We will follow the idea of [33] to develop an interior point method for solving the L1/2-SVM. To this end, in the next subsection, we reformulate problem (7) to a smooth constrained optimization problem.


### 2.4. A Reformulation to theL1/2-SVM Model

Consider the following constrained optimization problem:(8)min⁡∑j=1m‍tj+C∑i=1n‍ξi≜f(w,ξ,t,b)s.t.tj2-wj≥0,j=1,…,m,s.t.tj2+wj≥0,j=1,…,m,s.t.tj≥0,j=1,…,m,s.t.yi(wTxi+b)≥1-ξi,i=1,…,n,s.t.ξi≥0,i=1,…,n.
It is obtained by letting tj=|wj|1/2 in the objective function and adding constraints tj2-wj≥0 and tj2+wj≥0, j=1,…,m, in (7). Denote by ℱ the feasible region of the problem; that is,
(9)ℱ={(w,ξ,t,b)∣tj2-wj≥0,tj2+wj≥0,tj≥0,j=1,…,m}∩{(w,ξ,t,b)∣yi(wTxi+b)≥1-ξi,ξi≥0,i=1,…,n(w,ξ,t,b)∣yi(wTxi+b)≥}.
Let z=(w,ξ,t,b). Then the above problem can be written as
(10)min⁡f(z),z∈ℱ.The following theorem establishes the equivalence between theL1/2-SVM and (10).Theorem 1.
Ifu*=(w*,ξ*,b*)∈Rm+n+1 is a solution of the L1/2-SVM (7), then z*=(w*,ξ*,|w*|1/2,b*)∈Rm+n+m+1 is a solution of the optimization problem (10). Conversely, if (w*,ξ*,t*,b*) is a solution of the optimization problem (10), then (w*,ξ*,b*) is a solution of the L1/2-SVM (7).Proof.
Letu*=(w*,ξ*,b*) be a solution of the L1/2-SVM (7) and let z-=(w-,ξ-,t-,b-) be a solution of the constrained optimization problem (10). It is clear that z*=(w*,ξ*,|w*|1/2,b*)∈ℱ. Moreover, we have t-j2≥|w-j|, ∀j=1,2,…,m, and hence
(11)f(z-)=∑j=1m‍t-j+C∑i=1n‍ξ-i≥∑j=1m‍|w-j|1/2+C∑i=1n‍ξ-i≥∑j=1m‍|wj*|1/2+C∑i=1n‍ξi*=ϕ(u*).
Since z*∈ℱ, we have
(12)ϕ(u*)=f(z*)≥f(z-).
This together with (11) implies that f(z-)=ϕ(u*). The proof is complete.It is clear that the constraint functions of (10) are convex. Consequently, at any feasible point, the set of all feasible directions is the same as the set of all linearized feasible directions.As a result, the KKT point exists. The KKT system of the problem (10) can be written as the following system of nonlinear equations:
(13)R(w,ξ,t,b,λ)=(λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)yTλ(4)min⁡⁡{tj2-wj,λj(1)}j=1,2,…,mmin⁡⁡{tj2+wj,λj(2)}j=1,2,…,mmin⁡⁡{tj,λj(3)}j=1,2,…,mmin⁡⁡{pi,λi(4)}i=1,2,…,nmin⁡⁡{ξi,λi(5)}i=1,2,…,n)=0,
where λ=(λ(1),λ(2),λ(3),λ(4),λ(5)) are the Lagrangian multipliers, X=(x1,x2,…,xn)T, Y=diag⁡(y) is diagonal matrix and pi=yi(wTxi+b)-(1-ξi), i=1,2,…,n.For the sake of simplicity, the properties of the reformulation toL1/2-SVM are shown in Appendix A.


## 2.1. Standard SVM

In a two-class classification problem, we are given a training data setD=(xi;yi)i=1n, where xi∈Rm is the feature vector and yi∈{0,1} is the class label. The linear classifier is to construct the following decision function:
(2)f(x)=wTx+b,
where w=(w1,w2,…,wm) is the weight vector and b is the bias. The prediction label is +1 if f(x)>0 and -1 otherwise. The standard SVM (L2-SVM) [30] aims to find the separating hyperplane f(x)=0 between two classes with maximal margin 2/∥w∥22 and minimal training errors, which leads to the following convex optimization problem:
(3)min⁡12∥w∥22+C∑i=1n‍ξis.t.yi(wTxi+b)≥1-ξii=1,…,n,ξi≥0,
where ∥w∥2=(∑j=1m‍wj2)1/2 is the L2 norm of w, ξi is the loss function to allow training errors for data that may not be linearly separable, and C is a user-specified parameter to balance the margin and the losses. As the problem is a convex quadratic program, it can be solved by existing methods, such as the interior point method and active set method efficiently.


## 2.2. Sparse SVM

TheL2-SVM is a nonsparse regularizer in the sense that the learned decision hyperplane often utilizes all the features. In practice, peoples prefer to sparse SVM so that only a few features are used to make a decision. For this purposes, the following Lp-SVM becomes very welcome:
(4)min⁡∥w∥pp+C∑i=1n‍ξis.t.yi(wTxi+b)≥1-ξii=1,…,n,ξi≥0,
where p∈[0,1]. ∥w∥0 stands for the number of nonzero elements of w, and for p∈(0,1], ∥w∥p is defined by (1). Problem (4) is obtained by replacing L2 penalty (∥w∥22) by Lp penalty (∥w∥pp) in (3). The standard SVM (3) corresponds to the model (4) with p=2.Figure1 plots the Lp penalty in one dimension. We can see from the figure that the smaller p is, the larger penalties are imposed on the small coefficients (|w|<1). Therefore, the Lp penalties with p<1 may achieve sparser solution than the L1 penalty. In addition, the L1 imposes large penalties on large coefficients, which may lead to biased estimation for large coefficients. Consequently, the Lp (0<p<1) penalties become attractive due to their good properties in sparsity, unbiasedness [31] and oracle [32]. We are particularly interested in the L1/2 penalty. Recently, Xu et al. [21] revealed the representative role of the L1/2 penalty in the Lp regularization with p∈(0,1). We will apply L1/2 penalty to SVM to perform feature selection and classification jointly.Figure 1
L
p penalty in one dimension.


## 2.3.L1/2-SVM Model

We pay particular attention to theL1/2-SVM, namely, problem (4) with p=1/2. We will derive a smooth constrained optimization reformulation to the L1/2-SVM so that it is relatively easy to design numerical methods. We first specify the L1/2-SVM:
(5)min⁡∑j=1m‍|wj|1/2+C∑i=1n‍ξi≜ϕ(w,ξ,b)s.t.yi(wTxi+b)≥1-ξi,i=1,…,n,s.t.ξi≥0,i=1,…,n.
Denote by u=(w,ξ,b) and 𝒟 the feasible region of the problem; that is,
(6)𝒟={(w,ξ,b)∣yi(wTxi+b)≥1-ξi,ξi≥0,i=1,…,n(w,ξ,b)∣yi(wTxi+b)}.
Then the L1/2-SVM can be written as an impact form
(7)min⁡ϕ(u),u∈𝒟.It is a nonconvex and non-Lipschitz problem. Due to the existence of the term|wi|1/2, the objective function is not even directionally differentiable at a point with some wi=0, which makes the problem very difficult to solve. Existing numerical methods that are very efficient for solving smooth problem could not be used directly. One possible way to develop numerical methods for solving (7) is to smoothing the term |wj|1/2 using some smoothing function such as ϕϵ(wj)=(wj2+ϵ2)1/4 with some ϵ>0. However, it is easy to see that the derivative of ϕϵ(wj) will be unbounded as wj→0 and ϵ→0. Consequently, it is not desirable that the smoothing function based numerical methods could work well.Recently, Tian and Yang [33] proposed an interior point L1/2-penalty function method to solve general nonlinear programming problems by using a quadratic relaxation scheme for their L1/2-lower order penalty problems. We will follow the idea of [33] to develop an interior point method for solving the L1/2-SVM. To this end, in the next subsection, we reformulate problem (7) to a smooth constrained optimization problem.


## 2.4. A Reformulation to theL1/2-SVM Model

Consider the following constrained optimization problem:(8)min⁡∑j=1m‍tj+C∑i=1n‍ξi≜f(w,ξ,t,b)s.t.tj2-wj≥0,j=1,…,m,s.t.tj2+wj≥0,j=1,…,m,s.t.tj≥0,j=1,…,m,s.t.yi(wTxi+b)≥1-ξi,i=1,…,n,s.t.ξi≥0,i=1,…,n.
It is obtained by letting tj=|wj|1/2 in the objective function and adding constraints tj2-wj≥0 and tj2+wj≥0, j=1,…,m, in (7). Denote by ℱ the feasible region of the problem; that is,
(9)ℱ={(w,ξ,t,b)∣tj2-wj≥0,tj2+wj≥0,tj≥0,j=1,…,m}∩{(w,ξ,t,b)∣yi(wTxi+b)≥1-ξi,ξi≥0,i=1,…,n(w,ξ,t,b)∣yi(wTxi+b)≥}.
Let z=(w,ξ,t,b). Then the above problem can be written as
(10)min⁡f(z),z∈ℱ.The following theorem establishes the equivalence between theL1/2-SVM and (10).Theorem 1.
Ifu*=(w*,ξ*,b*)∈Rm+n+1 is a solution of the L1/2-SVM (7), then z*=(w*,ξ*,|w*|1/2,b*)∈Rm+n+m+1 is a solution of the optimization problem (10). Conversely, if (w*,ξ*,t*,b*) is a solution of the optimization problem (10), then (w*,ξ*,b*) is a solution of the L1/2-SVM (7).Proof.
Letu*=(w*,ξ*,b*) be a solution of the L1/2-SVM (7) and let z-=(w-,ξ-,t-,b-) be a solution of the constrained optimization problem (10). It is clear that z*=(w*,ξ*,|w*|1/2,b*)∈ℱ. Moreover, we have t-j2≥|w-j|, ∀j=1,2,…,m, and hence
(11)f(z-)=∑j=1m‍t-j+C∑i=1n‍ξ-i≥∑j=1m‍|w-j|1/2+C∑i=1n‍ξ-i≥∑j=1m‍|wj*|1/2+C∑i=1n‍ξi*=ϕ(u*).
Since z*∈ℱ, we have
(12)ϕ(u*)=f(z*)≥f(z-).
This together with (11) implies that f(z-)=ϕ(u*). The proof is complete.It is clear that the constraint functions of (10) are convex. Consequently, at any feasible point, the set of all feasible directions is the same as the set of all linearized feasible directions.As a result, the KKT point exists. The KKT system of the problem (10) can be written as the following system of nonlinear equations:
(13)R(w,ξ,t,b,λ)=(λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)yTλ(4)min⁡⁡{tj2-wj,λj(1)}j=1,2,…,mmin⁡⁡{tj2+wj,λj(2)}j=1,2,…,mmin⁡⁡{tj,λj(3)}j=1,2,…,mmin⁡⁡{pi,λi(4)}i=1,2,…,nmin⁡⁡{ξi,λi(5)}i=1,2,…,n)=0,
where λ=(λ(1),λ(2),λ(3),λ(4),λ(5)) are the Lagrangian multipliers, X=(x1,x2,…,xn)T, Y=diag⁡(y) is diagonal matrix and pi=yi(wTxi+b)-(1-ξi), i=1,2,…,n.For the sake of simplicity, the properties of the reformulation toL1/2-SVM are shown in Appendix A.


## 3. An Interior Point Method

In this section, we develop an interior point method to solve the equivalent constrained problem (10) of the L1/2-SVM (7).


### 3.1. Auxiliary Function

Following the idea of the interior point method, the constrained problem (10) can be solved by minimizing a sequence of logarithmic barrier functions as follows:
(14)min⁡Φμ(w,ξ,t,b)s.t.≜∑j=1m‍tj+C∑i=1n‍ξis.t.-μ∑j=1m‍[log⁡(tj2-wj)+log⁡(tj2+wj)+log⁡tj]s.t.-μ∑i=1n‍(log⁡pi+log⁡ξi)s.t.tj2-wj>0,j=1,2,…,m,s.t.tj2+wj>0,j=1,2,…,m,s.t.tj>0,j=1,2,…,m,s.t.pi=yi(wTxi+b)+ξi-1>0,i=1,2,…,n,s.t.ξi>0,i=1,2,⋯,n,
where μ is the barrier parameter, converging to zero from above.The KKT system of problem (14) is the following system of linear equations:
(15)λ(1)-λ(2)-XTYTλ(4)=0,C*en-λ(4)-λ(5)=0,em-2Tλ(1)-2Tλ(2)-λ(3)=0,yTλ(4)=0,(T2-W)λ(1)-μem=0,(T2+W)λ(2)-μem=0,Tλ(3)-μem=0,Pλ(4)-μen=0,Ξλ(5)-μen=0,
where λ=(λ(1),λ(2),λ(3),λ(4),λ(5)) are the Lagrangian multipliers, T=diag⁡(t), W=diag⁡(w), Ξ=diag⁡(ξ), and P=diag⁡(Y(Xw+b*en)+ξ-en) are diagonal matrices, and em∈Rm and en∈Rn stand for the vector whose elements are all ones.


### 3.2. Newton’s Method

We apply Newton’s method to solve the nonlinear system (15) in variables w, ξ, t, b, and λ. The subproblem of the method is the following system of linear equations:
(16)M=(ΔwΔξΔtΔbΔλ(1)Δλ(2)Δλ(3)Δλ(4)Δλ(5))=-(λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)enTYλ(4)(T2-W)λ(1)-μem(T2+W)λ(2)-μemTλ(3)-μemPλ(4)-μenΞλ(5)-μen),
where M is the Jacobian of the left function in (15) and takes the form(17)M=(0000I-I0-XTYT00000000-I-I00-2(D1+D2)0-2T-2T-I000000000yT0-D102TD10T2-W0000D202TD200T2+W00000D3000T00D4YXD40D4y000P00D5000000Ξ),where D1=diag⁡(λ(1)), D2=diag⁡(λ(2)), D3=diag⁡(λ(3)), D4=diag⁡(λ(4)), and D5=diag⁡(λ(5)).We can rewrite (16) as
(18)(λ(1)+Δλ(1))-(λ(2)+Δλ(2))-XTYT(λ(4)+Δλ(4))=0,(λ(4)+Δλ(4))+(λ(5)+Δλ(5))=C*en,2(D1+D2)Δt+2T(λ(1)+Δλ(1))+2T(λ(2)+Δλ(2))+(λ(3)+Δλ(3))=em,yT(λ(4)+Δλ(4))=0,-D1Δw+2TD1Δt+(T2-W)(λ(1)+Δλ(1))=μem,D2Δw+2TD2Δt+(T2+W)(λ(2)+Δλ(2))=μem,D3Δt+T(λ(3)+Δλ(3))=μem,D4YXΔw+D4Δξ+D4y*Δb+P(λ(4)+Δλ(4))=μen,D5Δξ+Ξ(λ(5)+Δλ(5))=μen.
It follows from the last five equations that vector λ^≜λ+Δλ can be expressed as
(19)λ^(1)=(T2-W)-1(μem+D1Δw-2TD1Δt),λ^(2)=(T2+W)-1(μem-D2Δw-2TD2Δt),λ^(3)=T-1(μem-D3Δt),λ^(4)=P-1(μen-D4YXΔw-D4Δξ-D4y*Δb),λ^(5)=Ξ-1(μen-D5Δξ).
Substituting (19) into the first four equations of (18), we obtain
(20)S(ΔwΔξΔtΔb)=(-μ(T2-W)-1em+μ(T2+W)-1em+XTYTP-1en-C*en+μP-1en+μΞ-1en-em+2μT(T2-W)-1em+2μT(T2+W)-1em+μT-1emμyTP-1en),
where matrix S takes the form
(21)S=(S11S12S13S14S21S22S23S24S31S32S33S34S41S42S43S44),
with blocks
(22)S11=U+V+XTYTP-1D4YX,S12=XTYTP-1D4,S13=-2(U-V)T,S14=XTYTP-1D4y,S21=P-1D4YX,S22=P-1D4+Ξ-1D5,S23=0,S24=P-1D4y,S31=-2(U-V)T,S32=0,S33=4T(U+V)T+T-1D3-2(D1+D2),S34=0,S41=yTP-1D4YX,S42=yTP-1D4,S43=0,S44=yTP-1D4y,
and U=(T2-W)-1D1 and V=(T2+W)-1D2.


### 3.3. The Interior Pointer Algorithm

Letz=(w,ξ,t,b) and λ=(λ(1),λ(2),λ(3),λ(4),λ(5)); we first present the interior pointer algorithm to solve the barrier problem (14), and then discuss the details of the algorithm.Algorithm 2.
The interior pointer algorithm (IPA) is as follows.Step 0. Given toleranceϵμ, set τ1∈(0,(1/2)), l>0, γ1>1, β¯∈(0,1). Let k=0.Step 1. Stop if KKT condition (15) holds.Step 2. ComputeΔzk from (20) and λ^k+1 from (19). Compute zk+1=zk+αkΔzk. Update the Lagrangian multipliers to obtain λk+1.Step 3.   Letk∶=k+1. Go to Step 1.In Step 2, a step lengthαk is used to calculate zk+1. We estimate αk by Armijo line search [34], in which αk=max⁡{β-j∣j=0,1,2,…} for some β-∈(0,1) and satisfies the following inequalities:
(23)(tk+1)2-wk+1>0,(tk+1)2+wk+1>0,tk+1>0,Φμ(zk+1)-Φμ(zk)≤τ1αk(∇wΦμ(zk)TΔwk+∇tΦμ(zk)TΔtk+∇ξΦμ(zk)TΔξk+∇bΦμ(zk)TΔbk),
where τ1∈(0,1/2).To avoid ill-conditioned growth ofλ^k and guarantee the strict dual feasibility, the Lagrangian multipliers λk should be sufficiently positive and bounded from above. Following a similar idea of [33], we first update the dual multipliers by
(24)λ-i(1)(k+1)={min⁡{l,μ(tik)2-wik},ifλ^i(1)(k+1)<min⁡{l,μ(tik)2-wik},λ^i(1)(k+1),ifmin⁡{l,μ(tik)2-xik}≤λ^i(1)(k+1)≤μγ1(tik)2-wik,μγ1(tik)2-wik,ifλ^i(1)(k+1)>μγ1(tik)2-wik,λ-i(2)(k+1)={min⁡{l,μ(tik)2+wik},ifλ^i(2)(k+1)<min⁡{l,μ(tik)2+wik},λ^i(2)(k+1),ifmin⁡{l,μ(tik)2+wik}≤λ^i(2)(k+1)≤μγ1(tik)2+wik,μγ1(tik)2+wik,ifλ^i(2)(k+1)>μγ1(tik)2+wik,λ-i(3)(k+1)={min⁡{l,μtik},ifλ^i(3)(k+1)<min⁡{l,μtik},λ^i(3)(k+1),ifmin⁡{l,μtik}≤λ^i(3)(k+1)≤μγ1tik,μγ1tik,ifλ^i(3)(k+1)>μγ1tik,λ-i(4)(k+1)={min⁡{l,μpik},ifλ^i(4)(k+1)<min⁡{l,μpik},λ^i(4)(k+1),ifmin⁡{l,μpik}≤λ^i(4)(k+1)≤μγ1pik,μγ1pik,ifλ^i(4)(k+1)>μγ1pik,
where pi=yi(wTxi+b)+ξi-1;
(25)λ-i(5)(k+1)={min⁡{l,μξik},ifλ^i(5)(k+1)<min⁡{l,μξik},λ^i(5)(k+1),ifmin⁡{l,μξik}≤λ^i(5)(k+1)≤μγ1ξik,μγ1ξik,ifλ^i(5)(k+1)>μγ1ξik,
where the parameters l and γ1 satisfy 0<l, γ1>1.Since positive definiteness of the matrixS is demanded in this method, the Lagrangian multipliers λ-k+1 should satisfy the following condition:
(26)λ(3)-2(λ(1)+λ(2))t≥0.
For the sake of simplicity, the proof is given in Appendix B.Therefore, ifλ-k+1 satisfies (26), we let λk+1=λ-k+1. Otherwise, we would further update it by the following setting:
(27)λ(1)(k+1)=γ2λ-(1)(k+1),λ(2)(k+1)=γ2λ-(2)(k+1),λ(3)(k+1)=γ3λ-(3)(k+1),
where constants γ2∈(0,1) and γ3≥1 satisfy
(28)γ3γ2=max⁡i∈E{2tik+1(λ-i(1)(k+1)+λ-i(2)(k+1))λ-i(3)(k+1)},
with E={1,2,…,n}. It is not difficult to see that the vector (λ-(1)(k+1),λ-(2)(k+1),λ-(3)(k+1)) determined by (27) satisfies (26).In practice, the KKT conditions (15) are allowed to be satisfied within a tolerance ϵμ. It turns to be that the iterative process stops, while the following inequalities meet:
(29)Res(z,λ,μ)=∥λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)enTYλ(4)(T2-W)λ(1)-μem(T2+W)λ(2)-μemTλ(3)-μemPλ(4)-μenΞλ(5)-μen∥<ϵμ,(30)λ≥-ϵμe,
where ϵμ is related to the current barrier parameter μ, and satisfies ϵμ↓0 as μ→0.Since functionΦμ in (14) is convex, we have the following lemma which shows that Algorithm 2 is well defined (the proof is given in Appendix B).Lemma 3.
Letzk be strictly feasible for problem (10). If Δzk=0, then (23) is satisfied for all αk≥0. If Δzk≠0, then there exists a α-k∈(0,1] such that (23) holds for all αk∈(0,α-k].The proposed interior point method successively solves the barrier subproblem (14) with a decreasing sequence {μk}. We simply reduce both ϵμ and μ by a constant factor β∈(0,1). Finally, we test optimality for problem (10) by means of the residual norm ∥Res(z,λ^,0)∥.Here, we present the whole algorithm to solve theL1/2-SVM problem(10)Algorithm 4.
Algorithm for solvingL1/2-SVM problem is as follows.Step 0. Setw0∈Rm,b0∈R,ξ0∈Rn, λ0=λ^0>0, ti0≥|wi0|+(1/2), i∈{1,2,…,m}. Given constants μ0>0, ϵμ0>0, β∈(0,1) and ϵ->0, let j=0.Step 1. Stop ifRes(zj,λ^j,0)≤ϵ- and λ^j≥0.Step 2. Starting from(zj,λj), apply Algorithm 2 to solve (14) with barrier parameter μj and stopping tolerance ϵμj. Set zj+1=zj,k, λ^j+1=λ^j,k, and λj+1=λj,k.Step 3. Setμj+1=βμj and ϵμj+1=βϵμj. Let j∶=j+1 and go to Step 1.In Algorithm4, the index j denotes an outer iteration, while k denotes the last inner iteration of Algorithm 2.The convergence of the proposed interior point method can be proved. We list the theorem here and give the proof in AppendixC.Theorem 5.
Let{(zk,λk)} be generated by Algorithm 2. Then, any limit point of the sequence {(zk,λ^k)} generated by Algorithm 2 satisfies the first-order optimality conditions (15).Theorem 6.
Let{(zj,λ^j)} be generated by Algorithm 4 by ignoring its termination condition. Then the following statements are true. (i)
The limit point of{(zj,λ^j)} satisfies the first order optimality condition (13).(ii)
The limit pointz* of the convergent subsequence {zj}𝒥⊆{zj} with unbounded multipliers {λ^j}𝒥 is a Fritz-John point [35] of problem (10).


## 3.1. Auxiliary Function

Following the idea of the interior point method, the constrained problem (10) can be solved by minimizing a sequence of logarithmic barrier functions as follows:
(14)min⁡Φμ(w,ξ,t,b)s.t.≜∑j=1m‍tj+C∑i=1n‍ξis.t.-μ∑j=1m‍[log⁡(tj2-wj)+log⁡(tj2+wj)+log⁡tj]s.t.-μ∑i=1n‍(log⁡pi+log⁡ξi)s.t.tj2-wj>0,j=1,2,…,m,s.t.tj2+wj>0,j=1,2,…,m,s.t.tj>0,j=1,2,…,m,s.t.pi=yi(wTxi+b)+ξi-1>0,i=1,2,…,n,s.t.ξi>0,i=1,2,⋯,n,
where μ is the barrier parameter, converging to zero from above.The KKT system of problem (14) is the following system of linear equations:
(15)λ(1)-λ(2)-XTYTλ(4)=0,C*en-λ(4)-λ(5)=0,em-2Tλ(1)-2Tλ(2)-λ(3)=0,yTλ(4)=0,(T2-W)λ(1)-μem=0,(T2+W)λ(2)-μem=0,Tλ(3)-μem=0,Pλ(4)-μen=0,Ξλ(5)-μen=0,
where λ=(λ(1),λ(2),λ(3),λ(4),λ(5)) are the Lagrangian multipliers, T=diag⁡(t), W=diag⁡(w), Ξ=diag⁡(ξ), and P=diag⁡(Y(Xw+b*en)+ξ-en) are diagonal matrices, and em∈Rm and en∈Rn stand for the vector whose elements are all ones.


## 3.2. Newton’s Method

We apply Newton’s method to solve the nonlinear system (15) in variables w, ξ, t, b, and λ. The subproblem of the method is the following system of linear equations:
(16)M=(ΔwΔξΔtΔbΔλ(1)Δλ(2)Δλ(3)Δλ(4)Δλ(5))=-(λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)enTYλ(4)(T2-W)λ(1)-μem(T2+W)λ(2)-μemTλ(3)-μemPλ(4)-μenΞλ(5)-μen),
where M is the Jacobian of the left function in (15) and takes the form(17)M=(0000I-I0-XTYT00000000-I-I00-2(D1+D2)0-2T-2T-I000000000yT0-D102TD10T2-W0000D202TD200T2+W00000D3000T00D4YXD40D4y000P00D5000000Ξ),where D1=diag⁡(λ(1)), D2=diag⁡(λ(2)), D3=diag⁡(λ(3)), D4=diag⁡(λ(4)), and D5=diag⁡(λ(5)).We can rewrite (16) as
(18)(λ(1)+Δλ(1))-(λ(2)+Δλ(2))-XTYT(λ(4)+Δλ(4))=0,(λ(4)+Δλ(4))+(λ(5)+Δλ(5))=C*en,2(D1+D2)Δt+2T(λ(1)+Δλ(1))+2T(λ(2)+Δλ(2))+(λ(3)+Δλ(3))=em,yT(λ(4)+Δλ(4))=0,-D1Δw+2TD1Δt+(T2-W)(λ(1)+Δλ(1))=μem,D2Δw+2TD2Δt+(T2+W)(λ(2)+Δλ(2))=μem,D3Δt+T(λ(3)+Δλ(3))=μem,D4YXΔw+D4Δξ+D4y*Δb+P(λ(4)+Δλ(4))=μen,D5Δξ+Ξ(λ(5)+Δλ(5))=μen.
It follows from the last five equations that vector λ^≜λ+Δλ can be expressed as
(19)λ^(1)=(T2-W)-1(μem+D1Δw-2TD1Δt),λ^(2)=(T2+W)-1(μem-D2Δw-2TD2Δt),λ^(3)=T-1(μem-D3Δt),λ^(4)=P-1(μen-D4YXΔw-D4Δξ-D4y*Δb),λ^(5)=Ξ-1(μen-D5Δξ).
Substituting (19) into the first four equations of (18), we obtain
(20)S(ΔwΔξΔtΔb)=(-μ(T2-W)-1em+μ(T2+W)-1em+XTYTP-1en-C*en+μP-1en+μΞ-1en-em+2μT(T2-W)-1em+2μT(T2+W)-1em+μT-1emμyTP-1en),
where matrix S takes the form
(21)S=(S11S12S13S14S21S22S23S24S31S32S33S34S41S42S43S44),
with blocks
(22)S11=U+V+XTYTP-1D4YX,S12=XTYTP-1D4,S13=-2(U-V)T,S14=XTYTP-1D4y,S21=P-1D4YX,S22=P-1D4+Ξ-1D5,S23=0,S24=P-1D4y,S31=-2(U-V)T,S32=0,S33=4T(U+V)T+T-1D3-2(D1+D2),S34=0,S41=yTP-1D4YX,S42=yTP-1D4,S43=0,S44=yTP-1D4y,
and U=(T2-W)-1D1 and V=(T2+W)-1D2.


## 3.3. The Interior Pointer Algorithm

Letz=(w,ξ,t,b) and λ=(λ(1),λ(2),λ(3),λ(4),λ(5)); we first present the interior pointer algorithm to solve the barrier problem (14), and then discuss the details of the algorithm.Algorithm 2.
The interior pointer algorithm (IPA) is as follows.Step 0. Given toleranceϵμ, set τ1∈(0,(1/2)), l>0, γ1>1, β¯∈(0,1). Let k=0.Step 1. Stop if KKT condition (15) holds.Step 2. ComputeΔzk from (20) and λ^k+1 from (19). Compute zk+1=zk+αkΔzk. Update the Lagrangian multipliers to obtain λk+1.Step 3.   Letk∶=k+1. Go to Step 1.In Step 2, a step lengthαk is used to calculate zk+1. We estimate αk by Armijo line search [34], in which αk=max⁡{β-j∣j=0,1,2,…} for some β-∈(0,1) and satisfies the following inequalities:
(23)(tk+1)2-wk+1>0,(tk+1)2+wk+1>0,tk+1>0,Φμ(zk+1)-Φμ(zk)≤τ1αk(∇wΦμ(zk)TΔwk+∇tΦμ(zk)TΔtk+∇ξΦμ(zk)TΔξk+∇bΦμ(zk)TΔbk),
where τ1∈(0,1/2).To avoid ill-conditioned growth ofλ^k and guarantee the strict dual feasibility, the Lagrangian multipliers λk should be sufficiently positive and bounded from above. Following a similar idea of [33], we first update the dual multipliers by
(24)λ-i(1)(k+1)={min⁡{l,μ(tik)2-wik},ifλ^i(1)(k+1)<min⁡{l,μ(tik)2-wik},λ^i(1)(k+1),ifmin⁡{l,μ(tik)2-xik}≤λ^i(1)(k+1)≤μγ1(tik)2-wik,μγ1(tik)2-wik,ifλ^i(1)(k+1)>μγ1(tik)2-wik,λ-i(2)(k+1)={min⁡{l,μ(tik)2+wik},ifλ^i(2)(k+1)<min⁡{l,μ(tik)2+wik},λ^i(2)(k+1),ifmin⁡{l,μ(tik)2+wik}≤λ^i(2)(k+1)≤μγ1(tik)2+wik,μγ1(tik)2+wik,ifλ^i(2)(k+1)>μγ1(tik)2+wik,λ-i(3)(k+1)={min⁡{l,μtik},ifλ^i(3)(k+1)<min⁡{l,μtik},λ^i(3)(k+1),ifmin⁡{l,μtik}≤λ^i(3)(k+1)≤μγ1tik,μγ1tik,ifλ^i(3)(k+1)>μγ1tik,λ-i(4)(k+1)={min⁡{l,μpik},ifλ^i(4)(k+1)<min⁡{l,μpik},λ^i(4)(k+1),ifmin⁡{l,μpik}≤λ^i(4)(k+1)≤μγ1pik,μγ1pik,ifλ^i(4)(k+1)>μγ1pik,
where pi=yi(wTxi+b)+ξi-1;
(25)λ-i(5)(k+1)={min⁡{l,μξik},ifλ^i(5)(k+1)<min⁡{l,μξik},λ^i(5)(k+1),ifmin⁡{l,μξik}≤λ^i(5)(k+1)≤μγ1ξik,μγ1ξik,ifλ^i(5)(k+1)>μγ1ξik,
where the parameters l and γ1 satisfy 0<l, γ1>1.Since positive definiteness of the matrixS is demanded in this method, the Lagrangian multipliers λ-k+1 should satisfy the following condition:
(26)λ(3)-2(λ(1)+λ(2))t≥0.
For the sake of simplicity, the proof is given in Appendix B.Therefore, ifλ-k+1 satisfies (26), we let λk+1=λ-k+1. Otherwise, we would further update it by the following setting:
(27)λ(1)(k+1)=γ2λ-(1)(k+1),λ(2)(k+1)=γ2λ-(2)(k+1),λ(3)(k+1)=γ3λ-(3)(k+1),
where constants γ2∈(0,1) and γ3≥1 satisfy
(28)γ3γ2=max⁡i∈E{2tik+1(λ-i(1)(k+1)+λ-i(2)(k+1))λ-i(3)(k+1)},
with E={1,2,…,n}. It is not difficult to see that the vector (λ-(1)(k+1),λ-(2)(k+1),λ-(3)(k+1)) determined by (27) satisfies (26).In practice, the KKT conditions (15) are allowed to be satisfied within a tolerance ϵμ. It turns to be that the iterative process stops, while the following inequalities meet:
(29)Res(z,λ,μ)=∥λ(1)-λ(2)-XTYTλ(4)C*en-λ(4)-λ(5)em-2Tλ(1)-2Tλ(2)-λ(3)enTYλ(4)(T2-W)λ(1)-μem(T2+W)λ(2)-μemTλ(3)-μemPλ(4)-μenΞλ(5)-μen∥<ϵμ,(30)λ≥-ϵμe,
where ϵμ is related to the current barrier parameter μ, and satisfies ϵμ↓0 as μ→0.Since functionΦμ in (14) is convex, we have the following lemma which shows that Algorithm 2 is well defined (the proof is given in Appendix B).Lemma 3.
Letzk be strictly feasible for problem (10). If Δzk=0, then (23) is satisfied for all αk≥0. If Δzk≠0, then there exists a α-k∈(0,1] such that (23) holds for all αk∈(0,α-k].The proposed interior point method successively solves the barrier subproblem (14) with a decreasing sequence {μk}. We simply reduce both ϵμ and μ by a constant factor β∈(0,1). Finally, we test optimality for problem (10) by means of the residual norm ∥Res(z,λ^,0)∥.Here, we present the whole algorithm to solve theL1/2-SVM problem(10)Algorithm 4.
Algorithm for solvingL1/2-SVM problem is as follows.Step 0. Setw0∈Rm,b0∈R,ξ0∈Rn, λ0=λ^0>0, ti0≥|wi0|+(1/2), i∈{1,2,…,m}. Given constants μ0>0, ϵμ0>0, β∈(0,1) and ϵ->0, let j=0.Step 1. Stop ifRes(zj,λ^j,0)≤ϵ- and λ^j≥0.Step 2. Starting from(zj,λj), apply Algorithm 2 to solve (14) with barrier parameter μj and stopping tolerance ϵμj. Set zj+1=zj,k, λ^j+1=λ^j,k, and λj+1=λj,k.Step 3. Setμj+1=βμj and ϵμj+1=βϵμj. Let j∶=j+1 and go to Step 1.In Algorithm4, the index j denotes an outer iteration, while k denotes the last inner iteration of Algorithm 2.The convergence of the proposed interior point method can be proved. We list the theorem here and give the proof in AppendixC.Theorem 5.
Let{(zk,λk)} be generated by Algorithm 2. Then, any limit point of the sequence {(zk,λ^k)} generated by Algorithm 2 satisfies the first-order optimality conditions (15).Theorem 6.
Let{(zj,λ^j)} be generated by Algorithm 4 by ignoring its termination condition. Then the following statements are true. (i)
The limit point of{(zj,λ^j)} satisfies the first order optimality condition (13).(ii)
The limit pointz* of the convergent subsequence {zj}𝒥⊆{zj} with unbounded multipliers {λ^j}𝒥 is a Fritz-John point [35] of problem (10).


## 4. Experiments

In this section, we tested the constrained optimization reformulation to theL1/2-SVM and the proposed interior point method. We compared the performance of the L1/2-SVM with L2-SVM [30], L1-SVM [12], and L0-SVM [12] on artificial data and ten UCI data sets (http://archive.ics.uci.edu/ml/). These four problems were solved in primal, referencing the machine learning toolbox Spider (http://people.kyb.tuebingen.mpg.de/spider/). The L2-SVM and L1-SVM were solved directly by quadratic programming and linear programming, respectively. To the NP-hard problem L0-SVM, a commonly cited approximation method Feature Selection Concave (FSV) [12] was applied and then the FSV problem was solved by a Successive Linear Approximation (SLA) algorithm. All the experiments were run in the personal computer (1.6 GHz of CPU, 4 GB of RAM) with MATLAB R2010b on 64 bit Windows 7.In the proposed interior point method (Algorithms2 and 4), we set the parameters as β-=0.6, τ1=0.5, l=0.00001, γ1=100000, and β=0.5. The balance parameter C was selected by 5-fold cross-validation on training set over the range {2-10, 2-9,…,210}. After training, the weights that did not satisfy the criteria |wj|/max⁡i(|wi|)≥104 [14] were set to zero. Then the cardinality of the hyperplane was computed as the number of the nonzero weights.


### 4.1. Artificial Data

First, we took an artificial binary linear classification problem as an example. The problem is similar to that in [13]. The probability of y=1 or -1 is equal. The first 6 features are relevant but redundant. In 70% samples, the first three features {x1,x2,x3} were drawn as xi=yN(i,1) and the second three features {x4,x5,x6} as xi=N(0,1). Otherwise, the first three were drawn as xi=N(0,1) and the second three as xi=yN(i-3,1). The rest features are noise xi=N(0,20), i=7,…,m. Here, m is the dimension of input features. The inputs were scaled to mean zero and standard deviation. In each trial, 500 points were generated for testing and the average results were estimated over 30 trials.In the first experiment, we consider the cases with the fixed feature sizem=30 and different training sample sizes n=10,20,…,100. The average results over the 30 trials are shown in Table 1 and Figure 2. Figure 2 (left) plots the average cardinality of each classifier. Since the artificial data sets have 2 relevant and nonredundant features, the ideal average cardinality is 2. Figure 2 (left) shows that the three sparse SVMs, L1-SVM, L1/2-SVM, and L0-SVM, can achieve sparse solution, while the L2-SVM almost uses full features in each data set. Furthermore, the solutions of L1/2-SVM and L0-SVM are much sparser than L1-SVM. As shown in Table 1, the L1-SVM selects more than 6 features in all cases, which implies that some redundant or irrelevant features are selected. The average cardinalities of L1/2-SVM and L0-SVM are similar and close to 2. However, when n=10 and 20, the L0-SVM has the average cardinalities of 1.42 and 1.87, respectively. It means that the L0-SVM sometimes selects only one feature in low sample data set and maybe ignores some really relevant feature. Consequently, with the cardinalities between 2.05 and 2.9, L1/2-SVM has the more reliable solution than L0-SVM. In short, as far as the number of selected features is concerned, the L1/2-SVM behaves better than the other three methods.Table 1
Results comparison on 10 artificial data sets with various training sample sizes.
n
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Card
Acc
Card
Acc
Card
Acc
Card
Acc
10
29.97
84.65
6.93
88.55
1.43
77.65
2.25
88.05
20
30.00
92.21
8.83
96.79
1.87
93.17
2.35
95.50
30
30.00
94.27
8.47
98.23
2.03
94.67
2.05
97.41
40
29.97
95.99
9.00
98.75
2.07
95.39
2.10
97.75
50
30.00
96.61
9.50
98.91
2.13
96.57
2.45
97.68
60
29.97
97.25
10.00
98.94
2.20
97.61
2.45
97.98
70
30.00
97.41
11.00
98.98
2.20
97.56
2.40
98.23
80
30.00
97.68
10.03
99.09
2.23
97.61
2.60
98.50
90
29.97
97.89
9.20
99.21
2.30
97.41
2.90
98.30
100
30.00
98.13
10.27
99.09
2.50
97.93
2.55
98.36
On average
29.99
95.21
9.32
97.65
2.10
94.56
2.41
96.78
“n” is the number of training samples, “Card” represents the number of selected features,  and “Acc” is the classification accuracy.Figure 2
Results comparison on 10 artificial data sets with various training samples.Figure2 (right) plots the trend of the prediction accuracy versus the size of the training sample. The classification performance of all methods is generally improved with the increasing of the training sample size n. L1-SVM has the best prediction performance in all cases and a slightly better than L1/2-SVM. L1/2-SVM shows more accuracy in classification than L2-SVM and L0-SVM, especially in the case of n=10,…,50. As shown in Table 1, when there are only 10 training samples, the average accuracy of L1/2-SVM is 88.05%, while the results of L2-SVM and L0-SVM are 84.65% and 77.65%, respectively. Compared with L2-SVM and L0-SVM, L1/2-SVM has the average accuracy increased by 3.4% and 10.4%, respectively, as can be explained in what follows. To the L2-SVM, all features are selected without discrimination, and the prediction would be misled by the irrelevant features. To the L0-SVM, few features are selected, and some relevant features are not included, which would put negative impact on the prediction result. As the tradeoff between L2-SVM and L0-SVM, L1/2-SVM has better performance than the two.The average results over ten artificial data sets in the first experiment are shown in the bottom of Table1. On average, the accuracy of L1/2-SVM is 0.87% lower than the L1-SVM, while the features selected by L1/2-SVM are 74.14% less than L1-SVM. It indicates that the L1/2-SVM can achieve much sparser solution than L1-SVM with little cost of accuracy. Moreover, the average accuracy of L1/2-SVM over 10 data sets is 2.22% higher than L0-SVM with the similar cardinality. To sum up, the L1/2-SVM provides the best balance between accuracy and sparsity among the three sparse SVMs.To further evaluate the feature selection performance ofL1/2-SVM, we investigate whether the features are correctly selected. For the L2-SVM is not designed for feature selection, it is not included in this comparison. Since our artificial data sets have 2 best features (x3,x6), the best result should have the two features (x3,x6) ranking on the top according to their absolute values of weights |wj|. In the experiment, we select the top 2 features with the maximal |wj| for each method and calculate the frequency that the top 2 features are x3 and x6 in 30 runs. The results are listed in Table 2. When the training sample size is too small, it is difficult to discriminate the two most important features for all sparse SVMs. For example, when n=10, the selected frequencies of L1-SVM, L0-SVM, and L1/2-SVM are 7, 3, and 9, respectively. When n increases, all methods tend to make more correct selection. Moreover, Table 2 shows that the L1/2-SVM outperforms the other two methods in all cases. For example, when n=100, the selected frequencies of L1-SVM andL0-SVM are 22 and 25, respectively, and the result of L1/2-SVM is 27. The L1-SVM selects too many redundant or irrelevant features, which may influence the ranking in some extent. Therefore, L1-SVM is not so good as L1/2-SVM at distinguishing the critical features. The L0-SVM has the lower hit frequency than L1/2-SVM, which is probably due to the excessive small feature subset it obtained. Above all, Tables 1 and 2 and Figure 2 clearly show that the L1/2-SVM is a promising sparsity driven classification method.Table 2
Frequency of the most important features (x3,x6) ranked on top 2 in 30 runs.
n
10
20
30
40
50
60
70
80
90
100
L
1-SVM
7
14
16
18
22
23
20
22
21
22
L
0-SVM
3
11
12
15
19
22
22
23
22
25
L
1
/
2-SVM
9
16
19
24
24
23
27
26
26
27In the second simulation, we consider the cases with various dimensions of feature spacem=20,40,…,180,200 and the fixed training sample size n=100. The average results over 30 trials are shown in Figure 3 and Table 3. Since there are only 6 relevant features yet, the larger m means the more noisy features. Figure 3 (left) shows that as the dimension increases from 20 to 200, the number of features selected by L1-SVM increases from 8.26 to 23.1. However, the cardinalities of L1/2-SVM and L0-SVM keep stable (from 2.2 to 2.95). It indicates that the L1/2-SVM and L0-SVM are more suitable for feature selection than L1-SVM.Table 3
Average results over 10 artificial data sets with varies dimension.
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Cardinality
109.95
15.85
2.38
2.41
Accuracy
92.93
99.07
97.76
98.26Figure 3
Results comparison on artificial data set with various dimensions.Figure3 (right) shows that with the increasing of the noise features, the accuracy of L2-SVM drops significantly (from 98.68% to 87.47%). On the contrary, to the other three sparse SVMs, there is little change in the accuracy. It reveals that SVMs can benefit from the features reduction.Table3 shows the average results over all data sets in the second experiment. On average, the solution of L1/2-SVM yields much sparser than L1-SVM and a slightly better accuracy than L0-SVM.


### 4.2. UCI Data Sets

We further tested the reformulation and the proposed interior point methods toL1/2-SVM on 10 UCI data sets [36]. There are 8 binary classification problems and 2 multiclass problems (wine, image). Each feature of the input data was normalized to zero mean and unit variance, and the instances with missing value were deleted. Then, the data was randomly split into training set (80%) and testing set (20%). For the two multiclass problems, a one-against-rest method was applied to construct a binary classifier for each class. We repeated the training and testing procedure 10 times, and the average results were shown in Tables 4 and 5 and Figure 4.Table 4
Feature selection performance comparison on UCI data sets (Cardinality).
No.
UCI Data Set
n
m
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Mean
Std
Mean
Std
Mean
Std
Mean
Std
1
Pima diabetes
768
8
8.00
0.00
7.40
0.89
6.20
1.10
7.60
1.52
2
Breast Cancer
683
9
9.00
0.00
8.60
1.22
6.40
2.07
8.40
1.67
3
Wine (3)
178
13
13.00
0.00
9.73
0.69
3.73
0.28
4.07
0.49
4
Image (7)
2100
19
19.00
0.00
8.20
0.53
3.66
0.97
5.11
0.62
5
SPECT
267
22
22.00
0.00
17.40
5.27
9.80
4.27
9
1.17
6
WDBC
569
30
30.00
0.00
9.80
1.52
9.00
3.03
5.60
2.05
7
Ionosphere
351
34
33.20
0.45
25.00
3.35
24.60
10.21
21.80
8.44
8
SPECTF
267
44
44.00
0.00
38.80
10.98
24.00
11.32
25.60
7.75
9
Sonar
208
60
60.00
0.00
31.40
13.05
27.00
7.18
13.60
10.06
10
Musk1
476
166
166.00
0.00
85.80
18.85
48.60
4.28
41
14.16
Average cardinality
40.50
40.42
24.21
16.30
14.18Table 5
Classification performance comparison on UCI data sets (accuaracy).
No.
UCI Data Set
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Mean
Std
Mean
Std
Mean
Std
Mean
Std
1
Pima diabetes
76.99
3.47
76.73
0.85
76.73
2.94
77.12
1.52
2
Breast cancer
96.18
2.23
97.06
0.96
96.32
1.38
96.47
1.59
3
Wine (3)
97.71
3.73
98.29
1.28
93.14
2.39
97.14
2.56
4
Image (7)
88.94
1.49
91.27
1.77
86.67
4.58
91.36
1.94
5
SPECT
83.40
2.15
78.49
2.31
78.11
3.38
82.34
5.10
6
WDBC
96.11
2.11
96.46
1.31
95.58
1.15
96.46
1.31
7
Ionosphere
83.43
5.44
88.00
3.70
84.57
5.38
87.43
5.94
8
SPECTF
78.49
3.91
74.34
4.50
73.87
3.25
78.49
1.89
9
Sonar
73.66
5.29
75.61
5.82
74.15
7.98
76.10
4.35
10
Musk1
84.84
1.73
82.11
2.42
76.00
5.64
82.32
3.38
Average accuracy
85.97
85.84
83.51
86.52Figure 4
Results comparison on UCI data sets.Tables4 and 5 summarize the feature selection and classification performance of the numerical experiments on UCI data sets, respectively. Here, n is the numbers of samples and m is the number of the input features. For the two multiclass data sets, the numbers of the classes are marked behind their names. Sparsity is defined as card/m and the small value of sparsity is preferred. The data sets are arranged in descending order according to the dimension. The lowest cardinality and the best accuracy rate for each problem are bolded.As shown in Tables4 and 5, the three sparse SVMs can encourage sparsity in all data sets, while remaining roughly identical accuracy with L2-SVM. Among the three sparse methods, the L1/2-SVM has the lowest cardinality (14.18) and the highest classification accuracy (86.52%) on average. While the L1-SVM has the worst feature selection performance with the highest average cardinality (24.21), and the L0-SVM has the lowest average classification accuracy (83.51%).Figure4 plots the sparsity (left) and classification accuracy (right) of each classifier on UCI data sets. In three data sets (6, 9, 10), the L1/2-SVM has the best performance both in feature selection and classification among the three sparse SVMs. Compared with L1-SVM, L1/2-SVM can achieve sparser solution in nine data sets. For example, in the data set “8 SPECTF,” the features selected by L1/2-SVM are 34% less than L1-SVM, at the same time, the accuracy of L1/2-SVM is 4.1% higher than L1-SVM. In most data sets (4, 5, 6, 9, 10), the cardinality of L1/2-SVM drops significantly (at least 37%) with the equal or a slightly better result in accuracy. Only in the data set “3 Wine,” the accuracy of L1/2-SVM is decreased by 1.1%, but the sparsity provided by L1/2-SVM leads to 58.2% improvement over L1-SVM. In the rest three data sets (1, 2, 7), the two methods have similar results in feature selection and classification. As seen above, the L1/2-SVM can provide lower dimension representation than L1-SVM with the competitive prediction performance.Figure4 (right) shows that, compared with L0-SVM, L1/2-SVM has the classification accuracy improved in all data sets. For instance, in four data sets (3, 4, 8, 10), the classification accuracy of L1/2-SVM is at least 4.0% higher than L0-SVM. Especially in the data set “10 Musk,” L1/2-SVM gives a 6.3% rise in accuracy over L0-SVM. Meanwhile, it can be observed from Figure 4 (left) that L1/2-SVM selects fewer feature than L0-SVM in five data sets (5, 6, 7, 9, 10). For example, in the data sets 6 and 9, the cardinalities of L1/2-SVM are 37.8% and 49.6% less than L0-SVM, respectively. In summary, L1/2-SVM presents better classification performance than L0-SVM, while it is effective in choosing relevant features.


## 4.1. Artificial Data

First, we took an artificial binary linear classification problem as an example. The problem is similar to that in [13]. The probability of y=1 or -1 is equal. The first 6 features are relevant but redundant. In 70% samples, the first three features {x1,x2,x3} were drawn as xi=yN(i,1) and the second three features {x4,x5,x6} as xi=N(0,1). Otherwise, the first three were drawn as xi=N(0,1) and the second three as xi=yN(i-3,1). The rest features are noise xi=N(0,20), i=7,…,m. Here, m is the dimension of input features. The inputs were scaled to mean zero and standard deviation. In each trial, 500 points were generated for testing and the average results were estimated over 30 trials.In the first experiment, we consider the cases with the fixed feature sizem=30 and different training sample sizes n=10,20,…,100. The average results over the 30 trials are shown in Table 1 and Figure 2. Figure 2 (left) plots the average cardinality of each classifier. Since the artificial data sets have 2 relevant and nonredundant features, the ideal average cardinality is 2. Figure 2 (left) shows that the three sparse SVMs, L1-SVM, L1/2-SVM, and L0-SVM, can achieve sparse solution, while the L2-SVM almost uses full features in each data set. Furthermore, the solutions of L1/2-SVM and L0-SVM are much sparser than L1-SVM. As shown in Table 1, the L1-SVM selects more than 6 features in all cases, which implies that some redundant or irrelevant features are selected. The average cardinalities of L1/2-SVM and L0-SVM are similar and close to 2. However, when n=10 and 20, the L0-SVM has the average cardinalities of 1.42 and 1.87, respectively. It means that the L0-SVM sometimes selects only one feature in low sample data set and maybe ignores some really relevant feature. Consequently, with the cardinalities between 2.05 and 2.9, L1/2-SVM has the more reliable solution than L0-SVM. In short, as far as the number of selected features is concerned, the L1/2-SVM behaves better than the other three methods.Table 1
Results comparison on 10 artificial data sets with various training sample sizes.
n
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Card
Acc
Card
Acc
Card
Acc
Card
Acc
10
29.97
84.65
6.93
88.55
1.43
77.65
2.25
88.05
20
30.00
92.21
8.83
96.79
1.87
93.17
2.35
95.50
30
30.00
94.27
8.47
98.23
2.03
94.67
2.05
97.41
40
29.97
95.99
9.00
98.75
2.07
95.39
2.10
97.75
50
30.00
96.61
9.50
98.91
2.13
96.57
2.45
97.68
60
29.97
97.25
10.00
98.94
2.20
97.61
2.45
97.98
70
30.00
97.41
11.00
98.98
2.20
97.56
2.40
98.23
80
30.00
97.68
10.03
99.09
2.23
97.61
2.60
98.50
90
29.97
97.89
9.20
99.21
2.30
97.41
2.90
98.30
100
30.00
98.13
10.27
99.09
2.50
97.93
2.55
98.36
On average
29.99
95.21
9.32
97.65
2.10
94.56
2.41
96.78
“n” is the number of training samples, “Card” represents the number of selected features,  and “Acc” is the classification accuracy.Figure 2
Results comparison on 10 artificial data sets with various training samples.Figure2 (right) plots the trend of the prediction accuracy versus the size of the training sample. The classification performance of all methods is generally improved with the increasing of the training sample size n. L1-SVM has the best prediction performance in all cases and a slightly better than L1/2-SVM. L1/2-SVM shows more accuracy in classification than L2-SVM and L0-SVM, especially in the case of n=10,…,50. As shown in Table 1, when there are only 10 training samples, the average accuracy of L1/2-SVM is 88.05%, while the results of L2-SVM and L0-SVM are 84.65% and 77.65%, respectively. Compared with L2-SVM and L0-SVM, L1/2-SVM has the average accuracy increased by 3.4% and 10.4%, respectively, as can be explained in what follows. To the L2-SVM, all features are selected without discrimination, and the prediction would be misled by the irrelevant features. To the L0-SVM, few features are selected, and some relevant features are not included, which would put negative impact on the prediction result. As the tradeoff between L2-SVM and L0-SVM, L1/2-SVM has better performance than the two.The average results over ten artificial data sets in the first experiment are shown in the bottom of Table1. On average, the accuracy of L1/2-SVM is 0.87% lower than the L1-SVM, while the features selected by L1/2-SVM are 74.14% less than L1-SVM. It indicates that the L1/2-SVM can achieve much sparser solution than L1-SVM with little cost of accuracy. Moreover, the average accuracy of L1/2-SVM over 10 data sets is 2.22% higher than L0-SVM with the similar cardinality. To sum up, the L1/2-SVM provides the best balance between accuracy and sparsity among the three sparse SVMs.To further evaluate the feature selection performance ofL1/2-SVM, we investigate whether the features are correctly selected. For the L2-SVM is not designed for feature selection, it is not included in this comparison. Since our artificial data sets have 2 best features (x3,x6), the best result should have the two features (x3,x6) ranking on the top according to their absolute values of weights |wj|. In the experiment, we select the top 2 features with the maximal |wj| for each method and calculate the frequency that the top 2 features are x3 and x6 in 30 runs. The results are listed in Table 2. When the training sample size is too small, it is difficult to discriminate the two most important features for all sparse SVMs. For example, when n=10, the selected frequencies of L1-SVM, L0-SVM, and L1/2-SVM are 7, 3, and 9, respectively. When n increases, all methods tend to make more correct selection. Moreover, Table 2 shows that the L1/2-SVM outperforms the other two methods in all cases. For example, when n=100, the selected frequencies of L1-SVM andL0-SVM are 22 and 25, respectively, and the result of L1/2-SVM is 27. The L1-SVM selects too many redundant or irrelevant features, which may influence the ranking in some extent. Therefore, L1-SVM is not so good as L1/2-SVM at distinguishing the critical features. The L0-SVM has the lower hit frequency than L1/2-SVM, which is probably due to the excessive small feature subset it obtained. Above all, Tables 1 and 2 and Figure 2 clearly show that the L1/2-SVM is a promising sparsity driven classification method.Table 2
Frequency of the most important features (x3,x6) ranked on top 2 in 30 runs.
n
10
20
30
40
50
60
70
80
90
100
L
1-SVM
7
14
16
18
22
23
20
22
21
22
L
0-SVM
3
11
12
15
19
22
22
23
22
25
L
1
/
2-SVM
9
16
19
24
24
23
27
26
26
27In the second simulation, we consider the cases with various dimensions of feature spacem=20,40,…,180,200 and the fixed training sample size n=100. The average results over 30 trials are shown in Figure 3 and Table 3. Since there are only 6 relevant features yet, the larger m means the more noisy features. Figure 3 (left) shows that as the dimension increases from 20 to 200, the number of features selected by L1-SVM increases from 8.26 to 23.1. However, the cardinalities of L1/2-SVM and L0-SVM keep stable (from 2.2 to 2.95). It indicates that the L1/2-SVM and L0-SVM are more suitable for feature selection than L1-SVM.Table 3
Average results over 10 artificial data sets with varies dimension.
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Cardinality
109.95
15.85
2.38
2.41
Accuracy
92.93
99.07
97.76
98.26Figure 3
Results comparison on artificial data set with various dimensions.Figure3 (right) shows that with the increasing of the noise features, the accuracy of L2-SVM drops significantly (from 98.68% to 87.47%). On the contrary, to the other three sparse SVMs, there is little change in the accuracy. It reveals that SVMs can benefit from the features reduction.Table3 shows the average results over all data sets in the second experiment. On average, the solution of L1/2-SVM yields much sparser than L1-SVM and a slightly better accuracy than L0-SVM.


## 4.2. UCI Data Sets

We further tested the reformulation and the proposed interior point methods toL1/2-SVM on 10 UCI data sets [36]. There are 8 binary classification problems and 2 multiclass problems (wine, image). Each feature of the input data was normalized to zero mean and unit variance, and the instances with missing value were deleted. Then, the data was randomly split into training set (80%) and testing set (20%). For the two multiclass problems, a one-against-rest method was applied to construct a binary classifier for each class. We repeated the training and testing procedure 10 times, and the average results were shown in Tables 4 and 5 and Figure 4.Table 4
Feature selection performance comparison on UCI data sets (Cardinality).
No.
UCI Data Set
n
m
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Mean
Std
Mean
Std
Mean
Std
Mean
Std
1
Pima diabetes
768
8
8.00
0.00
7.40
0.89
6.20
1.10
7.60
1.52
2
Breast Cancer
683
9
9.00
0.00
8.60
1.22
6.40
2.07
8.40
1.67
3
Wine (3)
178
13
13.00
0.00
9.73
0.69
3.73
0.28
4.07
0.49
4
Image (7)
2100
19
19.00
0.00
8.20
0.53
3.66
0.97
5.11
0.62
5
SPECT
267
22
22.00
0.00
17.40
5.27
9.80
4.27
9
1.17
6
WDBC
569
30
30.00
0.00
9.80
1.52
9.00
3.03
5.60
2.05
7
Ionosphere
351
34
33.20
0.45
25.00
3.35
24.60
10.21
21.80
8.44
8
SPECTF
267
44
44.00
0.00
38.80
10.98
24.00
11.32
25.60
7.75
9
Sonar
208
60
60.00
0.00
31.40
13.05
27.00
7.18
13.60
10.06
10
Musk1
476
166
166.00
0.00
85.80
18.85
48.60
4.28
41
14.16
Average cardinality
40.50
40.42
24.21
16.30
14.18Table 5
Classification performance comparison on UCI data sets (accuaracy).
No.
UCI Data Set
L
2-SVM
L
1-SVM
L
0-SVM
L
1
/
2-SVM
Mean
Std
Mean
Std
Mean
Std
Mean
Std
1
Pima diabetes
76.99
3.47
76.73
0.85
76.73
2.94
77.12
1.52
2
Breast cancer
96.18
2.23
97.06
0.96
96.32
1.38
96.47
1.59
3
Wine (3)
97.71
3.73
98.29
1.28
93.14
2.39
97.14
2.56
4
Image (7)
88.94
1.49
91.27
1.77
86.67
4.58
91.36
1.94
5
SPECT
83.40
2.15
78.49
2.31
78.11
3.38
82.34
5.10
6
WDBC
96.11
2.11
96.46
1.31
95.58
1.15
96.46
1.31
7
Ionosphere
83.43
5.44
88.00
3.70
84.57
5.38
87.43
5.94
8
SPECTF
78.49
3.91
74.34
4.50
73.87
3.25
78.49
1.89
9
Sonar
73.66
5.29
75.61
5.82
74.15
7.98
76.10
4.35
10
Musk1
84.84
1.73
82.11
2.42
76.00
5.64
82.32
3.38
Average accuracy
85.97
85.84
83.51
86.52Figure 4
Results comparison on UCI data sets.Tables4 and 5 summarize the feature selection and classification performance of the numerical experiments on UCI data sets, respectively. Here, n is the numbers of samples and m is the number of the input features. For the two multiclass data sets, the numbers of the classes are marked behind their names. Sparsity is defined as card/m and the small value of sparsity is preferred. The data sets are arranged in descending order according to the dimension. The lowest cardinality and the best accuracy rate for each problem are bolded.As shown in Tables4 and 5, the three sparse SVMs can encourage sparsity in all data sets, while remaining roughly identical accuracy with L2-SVM. Among the three sparse methods, the L1/2-SVM has the lowest cardinality (14.18) and the highest classification accuracy (86.52%) on average. While the L1-SVM has the worst feature selection performance with the highest average cardinality (24.21), and the L0-SVM has the lowest average classification accuracy (83.51%).Figure4 plots the sparsity (left) and classification accuracy (right) of each classifier on UCI data sets. In three data sets (6, 9, 10), the L1/2-SVM has the best performance both in feature selection and classification among the three sparse SVMs. Compared with L1-SVM, L1/2-SVM can achieve sparser solution in nine data sets. For example, in the data set “8 SPECTF,” the features selected by L1/2-SVM are 34% less than L1-SVM, at the same time, the accuracy of L1/2-SVM is 4.1% higher than L1-SVM. In most data sets (4, 5, 6, 9, 10), the cardinality of L1/2-SVM drops significantly (at least 37%) with the equal or a slightly better result in accuracy. Only in the data set “3 Wine,” the accuracy of L1/2-SVM is decreased by 1.1%, but the sparsity provided by L1/2-SVM leads to 58.2% improvement over L1-SVM. In the rest three data sets (1, 2, 7), the two methods have similar results in feature selection and classification. As seen above, the L1/2-SVM can provide lower dimension representation than L1-SVM with the competitive prediction performance.Figure4 (right) shows that, compared with L0-SVM, L1/2-SVM has the classification accuracy improved in all data sets. For instance, in four data sets (3, 4, 8, 10), the classification accuracy of L1/2-SVM is at least 4.0% higher than L0-SVM. Especially in the data set “10 Musk,” L1/2-SVM gives a 6.3% rise in accuracy over L0-SVM. Meanwhile, it can be observed from Figure 4 (left) that L1/2-SVM selects fewer feature than L0-SVM in five data sets (5, 6, 7, 9, 10). For example, in the data sets 6 and 9, the cardinalities of L1/2-SVM are 37.8% and 49.6% less than L0-SVM, respectively. In summary, L1/2-SVM presents better classification performance than L0-SVM, while it is effective in choosing relevant features.


## 5. Conclusions

In this paper, we proposed aL1/2 regularization technique for simultaneous feature selection and classification in the SVM. We have reformulated the L1/2-SVM into an equivalent smooth constrained optimization problem. The problem possesses a very simple structure and is relatively easy to develop numerical methods. By the use of this interesting reformulation, we proposed an interior point method and established its convergence. Our numerical results supported the reformulation and the proposed method. The L1/2-SVM can get more sparsity solution than L1-SVM with the comparable classification accuracy. Furthermore, the L1/2-SVM can achieve more accuracy classification results than L0-SVM (FSV).Inspired by the good performance of the smooth optimization reformulation ofL1/2-SVM, there are some interesting topics deserving further research. For examples, to develop more efficient algorithms for solving the reformulation, to study nonlinear L1/2-SVM, and to explore varies applications of the L1/2-SVM and further validate its effective are interesting research topics. Some of them are under our current investigation.



---

*Source: 942520-2014-04-10.xml*