Description
28. For a constrained programming problem minw f(w) s.t. gi(w) ≤ 0, hj(w)=0, the generalized
Lagrangian is defined by L(w,α,β)=f(w)+∑ αigi(w)+ ∑ βjhj(w), αi ≥ 0. A primal linear program is
a constrained program of the form: minx c′x s.t. Ax≥ b, x≥ 0. Using the generalized Lagrangian,
show that the dual form of the primal LP is maxu b′u s.t. A′u ≤ c, u ≥ 0.
29. Suppose K1 and K2 are two valid kernels. Show that for positive a and b, aK1+bK2 is also a valid
kernel.
30. Suppose K1 and K2 are two valid kernels. Show that for positive a and b, aK1K2 is also a valid
kernel, where the product is the Hadamard product: if K=K1K2 then K(x,y)=K1(x,y)K2(x,y).
31. Define K(x,y)=(x·y+c)3
, where c is a positive constant. Prove that K is a valid kernel by finding φ
so that K= φ(x)∙φ(y) .
32. Prove that K above is a valid kernel by showing that K is symmetric positive semidefinite.