# How to implement the dual Lagrange?

I have seen in the Pang book of data mining the following example:

x1            x2                 y             Lagrange multiplier
0.3858     0.4687                1             65.5261
0.4871     0.611                -1             65.5261
0.9218     0.4103               -1                  0
0.7382     0.8936               -1                  0
0.1763     0.0579                1                  0
0.4057     0.3529                1                  0
0.9355     0.8132               -1                  0
0.2146     0.0099                1                  0


which is related to SVM, in almost all the literature about his topic is used the Lagrangian multipliers that are obtained after solving the dual Lagrange:

where x_i and x_j are vectors corresponding to the train data showed in x1 and x2. The value of y corresponds when a data set (xi,xj) is classified with a label of 1 and which with a label of -1. The alpha values are the Lagrange multipliers that should be obtained after making the partial derivatives of each of the terms in LD.

In the book is only mentioned the values of the Lagrange multiplier, but I am lost about how to implement it in Mathematica. Is there any way to obtain the list of Lagrange multipliers that the author mentions for the different cases?

• Can you share Mathematica code in which you've attempted an implementation? Can you make your question complete by providing all of the information in your question on this site? What aspect, for example, are you trying to implement? Mar 11 '15 at 8:05
• If all terms in the above expression were sufficiently defined evaluating it would be easy in Mathematica. However, much information is missing. You mention the expression should be solved? How? It isn't even an equation. Something needs to be minimized perhaps? Please say so. What is alpha? The xi and xj in the expression can't be the x1 and x2 in the table heading, as, judging from the expression, x is a matrix with xi a row or column from that table. Mar 11 '15 at 8:37
• thank you for your comment @SjoerdC.deVries, I have updated the formula and put some extra data about it. Mar 11 '15 at 14:50
• With your additional information I take it that m=2 (because there are only 2 x vectors). It follows that alpha is a 2D vector. I'm still lost as to the meaning of yi then, because your description would only leave two values for that, y1 and y2. Obviously, something still missing here. Mar 11 '15 at 15:28
• @SjoerdC.deVries, yes, you are right m=2; in this case y is a vector of probable outcomes: 1 or -1. Here it is a rough description of how a SVM classifies, the part of the dual Lagrange is mentioned there also: en.wikipedia.org/wiki/Support_vector_machine Mar 11 '15 at 15:49

data = SemanticImportString[
"0.3858     0.4687                1             65.5261
0.4871     0.611                -1             65.5261
0.9218     0.4103               -1                  0
0.7382     0.8936               -1                  0
0.1763     0.0579                1                  0
0.4057     0.3529                1                  0
0.9355     0.8132               -1                  0
0.2146     0.0099                1                  0",
{"Number", "Number", "Number", "Number"}] // Normal;


For those without version 10 get the data here:

data = {{0.3858, 0.4687, 1., 65.5261}, {0.4871, 0.611, -1., 65.5261},
{0.9218, 0.4103, -1., 0.}, {0.7382, 0.8936, -1., 0.},
{0.1763, 0.0579, 1., 0.}, {0.4057, 0.3529, 1., 0.},
{0.9355, 0.8132, -1., 0.}, {0.2146, 0.0099, 1., 0.}}


The remainder of the code should work for most versions that I'm aware of:

l = Length@data;
x = data[[All, {1, 2}]];
y = data[[All, 3]];
α = Array[a, l];

g[α_?VectorQ] := Total[α] - 1/2 Sum[α[[i]] α[[j]] y[[i]] y[[j]] x[[i]].x[[j]], {i, l}, {j, l}]

Maximize[{g[α], y.α == 0, Thread[0 <= α <= 100]}, α]


{65.5502, {a[1] -> 65.5539, a[2] -> 65.5539, a[3] -> 0., a[4] -> 0., a[5] -> 0., a[6] -> 0., a[7] -> 0., a[8] -> 0.}}

• thank you, but it should not take the values of the last column, because I want to obtain those results Mar 12 '15 at 2:08
• @Janny I don't see where Sjoerd used the fourth column. It's just the data you posted, no doubt copied and pasted into Mathematica. If you don't want it included in the table, you shouldn't have put it in there in the first place. Mar 12 '15 at 2:28
• @MichaelE2 I understand, but in the question I posted that I wanted to obtain the list of Lagrange multipliers; I mean the values of the last column. Mar 12 '15 at 4:37
• @janny As Michael said, I haven't used the fourth column, it's just a straight copy of your question to save me some typing. The Lagrange multipliers were calculated from the first three columns only and can be seen in the output at the bottom. Mar 12 '15 at 6:25
• @SjoerdC.deVries thank you I got it; sorry, but I have a problem with my output in Mathematica 7. Could you be so kind to give it a look? Mar 12 '15 at 12:44