Pattern Classification, and Quadratic Problems

Pattern Classification, and Quadratic Problems 1 1 Overview • Pattern Classification, Linear Classifiers, and Quadratic Optimization • Constructing the Dual of CQP • The Karush-Kuhn-Tucker Conditions for CQP • Insights from Duality and the KKT Conditions • Pattern Classification without strict Linear Separation 2 Pattern Classification, Linear Classifiers, and Quadratic Optimization 2.1 The Pattern Classification Problem We are given: • points a1 , . . . , ak ∈ n that have property “P” • points b1 , . . . , bm ∈ n that do not have property “P” We would like to use these k + m points to develop a linear rule that can be used to predict whether or not other points x might or might not have property P. In particular, we seek a vector v and a scalar β for which: • v T ai > β for all i = 1, . . . , k • v T bi < β for all i = 1, . . . , m We will then use v, β to predict whether or not other points c have property P or not, using the rule: • If v T c > β, then we declare that c has property P. • If v T c < β, then we declare that c does not have property P. 2 We therefore seek v, β that defines the hyperplane Hv,β := {x|v T x = β} for which: • v T ai > β for all i = 1, . . . , k • v T bi < β for all i = 1, . . . , m This is illustrated in Figure 1. Figure 1: Illustration of the pattern classification problem. 3 2.2 The Maximal Separation Model We seek v, β that defines the hyperplane Hv,β := {x|v T x = β} for which: • v T ai > β for all i = 1, . . . , k • v T bi < β for all i = 1, . . . , m We would like the hyperplane Hv,β not only to separate the points with different properties, but to be as far away from the points a1 , . . . , ak , b1 , . . . , bm as possible. It is easy to derive via elementary analysis that the distance from the hyperplane Hv,β to any point ai is equal to v T ai − β . v Similarly, the distance from the hyperplane Hv,β to any point bi is equal to β − v T bi . v If we normalize the vector v so that v = 1 , then the minimum distance from the hyperplane Hv,β to any of the points a1 , . . . , ak , b1 , . . . , bm is then:
min v T a1 − β, . . . , v T ak − β, β − v T b1 , . . . , β − v T bm  . We therefore would like v and β to satisfy: • v = 1, and
 • min v T a1 − β, . . . , v T ak − β, β − v T b1 , . . . , β − v T bm is maximized. 4 This yields the following optimization model: δ PCP : maximizev,β,δ s.t. v T ai − β ≥ δ, i = 1, . . . , k β − v T bi ≥ δ, i = 1, . . . , m v = 1, v ∈ n , β ∈  Now notice that PCP is not a convex optimization problem, due to the presence of the constraint “v = 1”. 2.3 Convex Reformulation of PCP To obtain a convex optimization problem equivalent to PCP, we perform the following transformation of variables: x= v β , α= . δ δ
v
1 Then notice that δ =
x
=
x
, and so maximizing δ is equivalent to 1 maximizing
x
, which is equivalent to minimizing x. This yields the following reformulation of PCP: minimizex,α x s.t. xT ai − α ≥ 1, i = 1, . . . , k α − xT bi ≥ 1, i = 1, . . . , m x ∈ n , α ∈  5 Since the function f (x) = 12 x2 = 12 xT x is monotone in x we have that the point that minimizes the function x also minimizes the function 1 T 2 x x. We therefore write the pattern classification problem in the following form: 1 T 2x x CQP : minimizex,α s.t. xT ai − α ≥ 1, i = 1, . . . , k α − xT bi ≥ 1, i = 1, . . . , m x ∈ n , α ∈  Notice that CQP is a convex program with a differentiable objective function. We can solve CQP for the optimal x = x∗ and α = α∗ , and compute the optimal solution of PCP as: v∗ = x∗ x∗  , β∗ = α∗ x∗  , δ∗ = 1 . x∗  Problem CQP is a convex quadratic optimization problem in n + 1 variables, with k+m linear inequality constraints. There are very many software packages that are able to solve quadratic programs such as CQP. However, one difficulty that might be encountered in practice is that the number of points that are used to define the linear decision rule might be very large (say, k + m ≥ 1, 000, 000 or more). This can cause the model to become too large to solve without developing special-purpose algorithms. 3 Constructing the Dual of CQP As it turns out, the Lagrange dual of CQP yields much insight into the structure of optimal solution of CQP, and also suggests several algorithmic 6 approaches for solving the problem. In this section we derive the dual of CQP. We start by creating the Lagrangian function. Assign a nonnegative multiplier λi to each constraint “1 − xT ai + α ≤ 0” for i = 1, . . . , k and a nonnegative multiplier γi to each constraint “1 + xT bi − α ≤ 0” for i = 1, . . . , m. Think of the λi as forming the vector λ = (λ1 , . . . , λk ) and the γi as forming the vector γ = (γ1 , . . . , γm ). The Lagrangian then is: L(x, α, λ, γ) = k m   1 T λi (1 − xT ai + α) + γj (1 + xT bj − α) x x+ 2 i=1 j=1  =    k m k m k m       1 T γj bj  +  λi − γj  α + λi + γj x x − xT  λi ai − 2 i=1 j=1 i=1 j=1 i=1 j=1 We next create the dual function L∗ (λ, γ): L∗ (λ, γ) = minimumx,α L(x, α, λ, γ) . In solving this unconstrained minimization problem, we observe that L(x, α, λ, γ) is a convex function of x and α for fixed values of λ and γ. Therefore L(x, α, λ, γ) is minimized over x and α when ∇Lx (x, α, λ, γ) = 0 ∇Lα (x, α, λ, γ) = 0 . The first condition above states that the value of x will be: x= k  λi ai − i=1 m  γj bj , j=1 and the second condition above states that (λ, γ) must satisfy: 7 (1) k  λi − i=1 m  γj = 0 . (2) j=1 Substituting (1) and (2) back into L(x, α, λ, γ) yields: k   m  T   k m k m    1  γj −  λi ai − γj bj   λi ai − γj bj  λi + L∗ (λ, γ) = 2 i=1 j=1 i=1 j=1 i=1 j=1 where (λ, γ) must satisfy (2). Finally, the dual problem problem is constructed as: D1 : maximumλ,γ k  i=1 λi + m  j=1 γj − k  1 2 i=1 λi k  s.t. − ai λi − i=1 m  j=1 m  T γj bj k  i=1 λi ai − m  j=1 γj = 0 j=1 λ ≥ 0, γ ≥ 0 λ ∈ k , γ ∈ m . By utilizing (1), we can re-write this last formulation with the extra variables x as: k  D2 : maximumλ,γ,x s.t. i=1 x− λi + k  i=1 k  i=1 m  j=1 γj − 12 xT x λi ai − λi − m  j=1 m  γj bj γj = 0 j=1 λ ≥ 0, γ ≥ 0 λ ∈ k , γ ∈ m . 8 =0 γj bj Comparing D1 and D2, it might seem wiser to use D1 as it uses fewer variables and fewer constraints. But notice one disadvantage of D1. The quadratic portion of the objective function in D1, expressed as a quadratic form of the variables (λ, γ) will look something like: (λ, γ)T Q(λ, γ) where Q has dimension (m + k) × (m + k). The size of this matrix grows with the square of (m + k), which is bad. In contrast, the growth in the problem size of D2 is only linear in (m + k). Our next result shows that if we have an optimal solution to the dual problem D1 (or D2, for that matter), then we can easily write down an optimal solution to the original problem CQP.  0 is an optimal solution of D1, then: Property 1 If (λ∗ , γ ∗ ) = x∗ = k  λ∗i ai − i=1 α∗ = m  γj∗ bj (3) j=1  1 k  2 λ∗i (x∗ )T  k  i=1 λ∗i ai + m   γj∗ bj  (4) j=1 i=1 is an optimal solution to CQP. We will prove this property in the next section, as a consequence of the Karush-Kuhn-Tucker optimality conditions for CQP. 4 The Karush-Kuhn-Tucker Conditions for CQP The problem CQP is: 9 1 T 2x x CQP : minimizex,α s.t. xT ai − α ≥ 1, i = 1, . . . , k α − xT bi ≥ 1, i = 1, . . . , m x ∈ n , α ∈  The KKT conditions for this problem are: • Primal feasibility: xT ai − α ≥ 1, i = 1, . . . , k α − xT bj ≥ 1, j = 1, . . . , m x ∈ n , α ∈  • The Gradient Condition: x− k  λi ai + i=1 k  m  γj bj = 0 j=1 λi − i=1 m  γj = 0 j=1 • Nonnegativity of Multipliers: λ≥0 , 10 γ≥0 • Complementarity: λi (1 − xT ai + α) = 0 i = 1, . . . , k γj (1 + xT bj − α) = 0 j = 1, . . . , m 5 Insights from Duality and the KKT Conditions 5.1 The KKT Conditions Yield Primal and Dual Solutions Since CQP is the minimization of a convex function under linear inequality constraints, the KKT conditions are necessary and sufficient to characterize an optimal solution. Property 2 If (x, α, λ, γ) satisfies the KKT conditions, then (x, α) is an optimal solution to CQP and (λ, γ) is an optimal solution to D1. Proof: From the primal feasibility conditions, and the nonnegativity conditions on (λ, γ), we have that (x, α) and (λ, γ) are primal and dual feasible, respectively. We therefore need to show equality of the primal and dual objective functions to prove optimality. If we call z(x, α) the objective function of the primal problem evaluated at (x, α) and v(λ, γ) the objective function of the dual problem evaluated at (λ, γ) we have: 1 z(x, α) = xT x 2 and v(λ, γ) = k  i=1 λi + m  j=1  γj − k  m  T  k  m   1 λi ai − γj bj   λi ai − γj bj  . 2 i=1 j=1 i=1 j=1 However, we also have from the gradient conditions that: 11   k m   x =  λi ai − γj bj  . i=1 j=1 Substituting this in above yields: v(λ, γ) − z(x, α) = = k  λi + i=1 j=1 k  m  λi + i=1 = m  k  γj − xT x  γj − xT  j=1 k  λi ai − i=1 λi 1 − xT ai + i=1 = k  m  j=1  γj bj   γj 1 + xT bj + α  j=1 λi 1 − xT ai + α + i=1 m  k  i=1 m  λi − m  j=1 γj 1 + xT bj − α j=1 = 0 and so (x, α) and (λ, γ) are optimal for their respective problems. 5.2 Nonzero values of x, λ, and γ If (x, α, λ, γ) satisfy the KKT conditions, then x =  0 from the primal feasibility constraints. This in turn implies that λ = 0 and γ =  0 from the gradient conditions. 5.3 Complementarity The complementarity conditions imply that the dual variables λi and γj are only positive if the corresponding primal constraint is tight: λi > 0 ⇒ (1 − xT ai + α) = 0 γj > 0 ⇒ (1 + xT bj − α) = 0 12  γj  Equality in the primal constraint means that the corresponding point, ai or bj , is at the minimum distance from the hyperplane. In combination with  0, this implies that the optimal the observation above that λ = 0 and γ = hyperplane will have points of both classes at the minimum distance. 5.4 A Further Geometric Insight Consider the example of Figure 2. In Figure 2, the hyperplane is determined by the three points that are at the minimum distance from it. Since the points we are separating are not likely to exhibit collinearity, we can conclude in general that most of the dual variables will be zero at the optimal solution. Figure 2: A separating hyperplane determined by three points. More generally, we would expect that at most n + 1 points will lie at the minimum distance from the hyperplane. Therefore, we would expect that all but at most n + 1 dual variables will be zero at the optimal solution. 13 5.5 The Geometry of the Normal Vector Consider the example shown in Figure 3. In Figure 3, the points corresponding to active primal constraints are labeled a1 , a2 , a3 , b1 , b2 . 00 0 0 0 0 0 x 0 0 a3 0 0 0 0 * b2 0 a2 * * * * * * * 0 a1 b1 * * * * * * Figure 3: Separating hyperplane and points with tight primal constraints. In this example, we see that xT (a1 − a2 ) = xT a1 − xT a2 = (1 + α) − (1 + α) = 0. Here we only used the fact that 1 − xT ai + α = 0. In general we have the following property: Property 3 The normal vector x to the separating hyperplane is orthogonal to any difference between points of the same class whose primal constraints are active. Proof: Without loss of generality, we can consider the points a1 , . . . , aı̂ and b1 , . . . , bˆ to be the points corresponding to tight primal constraints. This means that xT ai = 1 + α, i = 1, . . . , ı̂, and also that xT bj = α − 1, j = 1, . . . , ̂. From this it is clear that xT (ai − aj ) = 0, i, j = 1, . . . , ı̂ and xT (bi − bj ) = 0, i, j = 1, . . . , ̂. 14 5.6 More Geometry of the Normal Vector From the gradient conditions, we have: k  x = λi ai − i=1 ı̂  = m  γj bj j=1 λi ai − i=1 ̂  γj bj j=1 where we amend our notation so that the points ai correspond to active constraints for i = 1, . . . , ı̂ and the points bj correspond to active constraints for j = 1, . . . , ̂. If we set δ = ı̂  i=1 λi = ̂  γj , we have: j=1   ̂ ı̂   λ γ i i j j a − b x = δ i=1 δ j=1 δ From this last equation we see that x is the scaled difference between a convex combination of a1 , . . . , aˆı and a convex combination of b1 , . . . , bˆ. 5.7 Proof of Property 1 We will now prove Proposition 1, which asserts that (3 - 4) yields an optimal solution to CQP given an optimal solution (λ, γ) of D1. We start by writing down the KKT optimality conditions for D1: 15 • Feasibility: k  λi − i=1 m  γj = 0 j=1 λ ≥ 0, γ ≥ 0 λ ∈ k , γ ∈ m • Gradient Conditions:   k m   γj bj  + α + µi = 0 1 − (ai )T  λl al − 1 + (bj )T i = 1, . . . , k j=1 l=1 k  λi ai − i=1 m  − α + νj = 0 γl bl j = 1, . . . , m l=1 µ ≥ 0, ν ≥ 0 µ ∈ k , ν ∈ m • Complementarity: λi µi = 0 i = 1, . . . , k γj νj = 0 j = 1, . . . , m Now suppose that (λ, γ) is an optimal solution of D1, whereby (λ, γ) satisfy the above KKT conditions for some values of α, µ, ν. We will now show that the point (x, α) is optimal for CQP, where x is defined by (3), namely x= k  λi ai − i=1 m  j=1 16 γj bj , and α arises in the KKT conditions. Substituting the expression for x in the gradient conditions, we obtain: 1 = xT ai − α − µi ≤ xT ai − α i = 1, . . . , k, 1 = −xT bj + α − νj ≤ −xT bj + α j = 1, . . . , m. Therefore (x, α) is feasible for CQP. Now let us compare the objective function values of (x, α) in the primal and (λ, γ) in the dual. The primal objective function value is: 1 z = xT x , 2 and the dual objective function value is: v= k  λi + i=1 m   γj − j=1 k  T  m  k   m  1 λi ai − γj bj   λi ai − γj bj  . 2 i=1 j=1 i=1 j=1 Substituting in the equation: x= k  λi ai − i=1 m  γ j bj j=1 and taking differences, we compute the duality gap between these two solutions to be: v−z = = k  m  i=1 j=1 k  m  i=1 = λi + k  i=1 λi + γj − xT x   k m   γj − xT  λi ai − γj bj  j=1 λi 1 − xT ai + i=1 m  j=1  γj 1 + xT bj + α  j=1 k  i=1 17 λi − m  j=1  γj  = k  λi 1 − xT ai + α + i=1 = − m  γj 1 + xT bj − α j=1 k  λi µi − i=1 m  γj ν j j=1 = 0 which demonstrates that (x, α) must therefore be an optimal primal solution. To finish the proof we must validate the expression for α in (4). If we multiply the first set of expressions of the gradient conditions by λi and the second set by −γj we obtain: 0 = λi 1 − xT ai + α + µi = λi − λi xT ai + λi α i = 1, . . . , k 0 = −γj 1 + xT bj − α + νj = −γj − γj xT bj + γj α j = 1, . . . , m Summing these, we obtain: 0 = k  i=1 λi − m      k m k m     γj − xT  λi ai + γj bj  + α  λi + γj  j=1 i=1 j=1   k m k    = −xT  λi ai + γj bj  + 2 λi α i=1 j=1 i=1 which implies that:   k m   xT  λi ai + γj bj  1 α= 2 k  i=1 λi i=1 18 j=1 i=1 j=1 5.8 Final Comments The fact that we can expect to have at most n + 1 dual variables different than zero in the optimal solution (out of a possible number which could be as high as k + m) is very important. It immediately suggests that we might want to develop solution methods that try to limit the number of dual variables that are different from zero at any iteration. Such algorithms are called “Active Set Methods”, which we will visit in the next lecture. 6 Pattern Classification without strict Linear Sep­ aration The are very many instances of the pattern classification problem where the observed data points do not give rise to a linear classifier, i.e., a hyperplane Hv,β that separates a1 , . . . , ak from b1 , . . . , bm . If we still want to construct a classification function that is based on a hyperplane, we will have to allow for some error or “noise” in the data. Alternatively, we can allow for separation via a non-linear function rather than a linear function. 6.1 Pattern Classification with Penalties Consider the following optimization problem: QP3 : minimizex,α,ξ s.t. k+m  1 T x x+C ξi 2 i=1 xT ai − α ≥ 1 − ξi i = 1, . . . , k α − xT bj ≥ 1 − ξk+j j = 1, . . . , m ξi ≥ 0 i = 1, . . . , k + m. (5) In this model, the ξi variables allow the constraints to be violated, but at a cost of C, where we presume that C is a large number. Here we see that C represents the tradeoff between the competing objectives of producing a 19 hyperplane that is far from the points ai , i = 1, . . . , k and bi , i = 1, . . . , m, and that penalizes points for being close to the hyperplane. The dual of this quadratic optimization problem turns out to be: D3 : maximizeλ,γ s.t. k   T  λi − i=1 m  γj = 0 j=1 (6) λi ≤ C i = 1, . . . , k γj ≤ C j = 1, . . . , m λ ≥ 0, γ≥0. In an analogous fashion to Property 1 stated earlier for the separable case, one can derive simple formulas to directly compute an optimal primal solution (x∗ , α∗ , ξ ∗ ) from an optimal dual solution (λ∗ , γ ∗ ). As an example of the above methodology, consider the pattern classification data shown in Figure 4. Figure 5 and Figure 6 show solutions to this problem with different values of the penalty parameter C = 10 and C = 100, respectively. 6.2  k m k m    1  λi + γj −  λi ai − γj bj   λi ai − γ j bj  2 i=1 j=1 i=1 j=1 i=1 j=1 k  k  Pattern Classification via Non-linear Mappings Another way to separate sets of points that are not separable using a linear classifier (a hyperplane) is to create a non-linear transformation, usually to a higher-dimensional space, in such a way that the transformed points are separable by a hyperplane in the transformed space (or are nearly separable, with the aid of penalty terms). Suppose we have on hand a mapping: 20 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 Figure 4: Pattern classification data that cannot be separated by a hyperplane. 21 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 Figure 5: Solution to the problem with C = 1.0. 22 1 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 Figure 6: Solution to the problem with C = 1, 000.0. 23 1 φ(·) : n → l where one should think of l as satisfying l >> n. Under this mapping, we have: ˜i = φ(ai ), i = 1, . . . , k ai → a bi → b̃i = φ(bi ), i = 1, . . . , m. We then solve for our separating hyperplane
˜ ∈ l | ṽ T x ˜ = β̃ Hv,β ˜ ˜ = x  via the methods described earlier. If we are given a new point c that we would like to classify, we compute c̃ = φ(c) and use the rule: • If v˜T c˜ > β̃, then we declare that c has property P. • If v˜T c˜ < β̃, then we declare that c does not have property P. Quite often we do not have to explicitly work with the function φ(·), as we now demonstrate. Consider the pattern classification problem shown in Figure 7. In Figure 7, the two classes of points are clearly not separable with a hyperplane. However, it does seem that there is a smooth function that would easily separate the two classes of points. We can of course solve the linear separation problem (with penalties) for this problem. Figure 8 shows the linear classifier for this problem, computed using the penalty value C = 100. As Figure 8 clearly shows, this separator is clearly not adequate. We might think of trying to find a quadratic function (as opposed to a linear function) that will separate our points. In this case we would seek to find values of: Q= Q11 Q12 Q12 Q22  , satisfying: 24 q= q1 q2  , d Figure 7: Two classes of points that can be separated by a nonlinear surface. 25 Figure 8: Illustration of a linear classifier for a non-separable case. 26 • (ai )T Qai + q T ai + d > 0 for all i = 1, . . . , k • (bi )T Qbi + q T bi + d < 0 for all i = 1, . . . , m We would then use this data to classify any new point c as follows: • If cT Qc + q T c + d > 0, then we declare that c has property P. • If cT Qc + q T c + d < 0, then we declare that c does not have property P. Although this problem seems much more complicated than linear classification, indeed it is really linear classification in a slightly higher-dimensional space! To see why this is true, let us look at our 2-dimensional example in detail. Let one of the ai values be denoted as the data (ai1 , ai2 ). Then (ai )T Qai + q T ai + d = (ai1 )2 × Q11 + 2a1i a2i × Q12 + (a2i )2 × Q22 + a1i × q1 + ai2 × q2 + d =  (ai1 )2 , 2ai1 a2i , (a2i )2 , a1i , ai2 T (Q11 , Q12 , Q22 , q1 , q2 ) + d ˜2 , a ˜3 , a ˜4 , a ˜5 )T (Q11 , Q12 , Q22 , q1 , q2 ) + d = (˜ a1 , a where ã := φ(a) = φ(a1 , a2 ) := (a21 , 2a1 a2 , a22 , a1 , a2 ) . Notice here that this problem is one of linear classification in 5 . We therefore can solve this problem using the usual optimization formulation, but now stated in the higher-dimensional space. The problem we wish to solve then becomes: HPCP : s.t. maximizeQ,q,d,δ  (ai1 )2 , 2ai1 a2i , (a2i )2 , a1i , ai2  T − (bi1 )2 , 2bi1 bi2 , (bi2 )2 , bi1 , bi2 T δ ≥ δ, i = 1, . . . , k (Q11 , Q12 , Q22 , q1 , q2 ) − d ≥ δ, i = 1, . . . , m (Q11 , Q12 , Q22 , q1 , q2 ) + d  (Q11 , Q12 , Q22 , q1 , q2 )  27 = 1, This problem then can be transformed into a convex quadratic program by using the transformation used in Section 2.3. If one solves the problem this way, the optimized quadratic separator turns out to be: −24.723c21 − 0.261c1 c2 − 1.706c22 + 14.438c1 − 2.794c2 − 0.163 Figure 9 shows the solution to this problem. Notice that the solution indeed separates the two classes of points. 1 0.8 0.6 0.4 y 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 x 0.2 0.4 0.6 0.8 1 Figure 9: Illustration of separation by a quadratic separator. 6.3 Pattern Classification via Ellipsoids As it turns out, the quadratic surface separator described in the previous section can be developed further. Recall the model: 28 HPCP : maximizeQ,q,d,δ  s.t. (ai1 )2 , 2ai1 a2i , (a2i )2 , a1i , ai2  T − (bi1 )2 , 2bi1 bi2 , (bi2 )2 , bi1 , bi2 T δ ≥ δ, i = 1, . . . , k (Q11 , Q12 , Q22 , q1 , q2 ) − d ≥ δ, i = 1, . . . , m (Q11 , Q12 , Q22 , q1 , q2 ) + d  (Q11 , Q12 , Q22 , q1 , q2 )  = 1, Suppose that we would like the resulting quadratic surface to be an ellipsoid. This corresponds to requiring that the matrix Q11 Q12 Q= Q12 Q22  be an SPSD matrix. Suppose that we would like this ellipsoid to be as “round” as possible, which means that we would like the condition number κ(Q) := λmax (Q) λmin (Q) to be as small as possible. Then our problem becomes: RP : s.t. λmax (Q) λmin (Q) minimizeQ,q,d  (ai1 )2 , 2ai1 a2i , (a2i )2 , a1i , ai2  T − (bi1 )2 , 2bi1 bi2 , (bi2 )2 , bi1 , bi2 T ≥ 0, i = 1, . . . , k (Q11 , Q12 , Q22 , q1 , q2 ) − d ≥ 0, i = 1, . . . , m (Q11 , Q12 , Q22 , q1 , q2 ) + d  (Q11 , Q12 , Q22 , q1 , q2 )  Q is SPSD . 29 = 1, As it turns out, this problem can be re-cast as a convex optimization problem, using the tools of the new field of semi-definite programming. Figure 10 shows an example of a solution to a pattern classification problem obtained by solving the problem RP. 098414 x2 −011589 2 x y +...−012838 = 0 1 0.8 0.6 0.4 y 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 x 0.2 0.4 0.6 0.8 1 Figure 10: Illustration of an ellipsoidal separator using semi-definite programming. 30