Description

1 Lagrange Multipliers: Warm-up

In class we have seen the formulation of the Support Vector Machines (SVMs), which has been successfully used for many classification tasks. We saw that the parameters of the SVMs are learned using the Lagrange Multipliers. The Lagrange Multiplier is a method of optimizing a function subject to a set of constraints, e.g. in SVMs we have the following optimization problems
1k k2 (1)
min w
w 2
s.t. 8i 2 {1,2,…,N} : yi(w · xi b) 1 (2)
In this exercise, we will deal the same optimization problems using Lagrange Multipliers. Suppose we would like to maximize the function
(3)
which has two input dimensions x1 and x2 (they can be considered as the parameters that we would like to learn). This function is plotted in Figure 1(a). We can see the function is concave and there is no local minimum. The optimization of the function is subject to a constraint function. Therefore the optimal solution that is found has to satisfies the constraints.
For example, if we set the constraints x1 + x2 = 1, then the optimization problem is to find the maximal value of f(x) where x is also on the constraint plane. Figure 1(b) shows the constraint function (black) separates f(x) into two parts.
The 3D view of f(x) is slighted changed in Figure 1(b) for better visualization. Answer the following questions:
1. Find the maximum of 1 , subject to the constraint that x1+x2 = 1.
2. Find the maximum of 1 subject to the constraint x1 + x2 1 > 0
3. Find the maximum of 1 subject to the constraint x1 x2 +1 > 0

(a) (b)
Figure 1: (a) Plot of the example function. Plot (b) also illustrates the constraint surface.
4. Find the maximum of x1 + 2×2 2×3, subject to the constraint that

5. A company manufactures a chemical product out of two ingredients, knownas ingredient X and ingredient Y. The number of doses produced, D, is given by 6×2/3y1/2, where x and y are the number of grams of ingredients X and Y respectively. Suppose ingredient X consts 4 euro per gram, and ingredient Y costs 3 euro per gram. Find out the maximum number of doses that can be made if no more than 7000 euro can be spent on the ingredients.
2 Kernel Outlier Detection
Consider the picture in Figure 2. The dots represent data-items. Our task is to derive an algorithm that will detect the outliers (in this example there are 2 of them). To that end, we draw a circle rooted at location a and with radius R. All data-cases that fall outside the circle are detected as outliers.
We will now write down the primal program that will find such a circle:
N

s.t. 8i :kxi ak2  R2 + ⇠i, ⇠i 0
In words: we want to minimize the radius of the circle subject to the constraint that most data-cases should lay inside it. Outliers are allowed to stay outside but they pay a price proportional their distance from the circle boundary and C.
Answer the following questions:

Figure 2: Kernel Outlier Detection
1. Introduce Lagrange multipliers for the constraints and write down the primalLagrangian. Use the following notation: {↵i} are the Lagrange multipliers for the first constraint and {µi} for the second constraint.
2. Write down all KKT conditions. (Hint: take the derivative w.r.t. R2 instead of R).
3. Identify the complementary slackness conditions. Use these conditions toderive what data-cases (e.g. in Figure 2) will have ↵i > 0 (support vectors) and which ones will have µi > 0.
4. Derive the dual Lagrangian and specify the dual optimization problem. Kernelize the problem, i.e. write the dual program only in terms of kernel entries and Lagrange multipliers.
5. The dual program will return optimal values for {↵i}. In terms of these, compute the optimal values for the other dual variables {µi}.
Then, solve the primal variables {a,R,⇠} (in that order) in terms of the dual variables {µi,↵i}. Note that you do not need to know the dual optimization program to solve this question. You only need the KKT conditions.
7. What kind of solution do you expect if we use C = 0. And what solution if we use C = 1?
9. Now assume that you are given labels (e.g. y=1 for outlier and y=-1 for“inlier”). Change the primal problem to include these labels and turn it into a classification problem similar to the SVM. (You do not have to derive the dual program).