Review•QP examples: Huber regression, LASSO!!!"#" $%&'!"#"$%&'#'"#"'$#$'%#%'&#&''#mina,b (z + a – b)2 + 2a + 2b s.t. a, b ! 0minw,s !(yi - xi’w)2 + "!sjs.t. sj ! wj, sj ! –wj1Thursday, February 11, 2010Support vector machines(separable case)18Wednesday, February 3, 2010minv,d ||v||2/2 s.t. yi (xi!v – d) ! 12Thursday, February 11, 2010And again•Note = constraint! min x – 2y s.t.! x + y " 2! x, y " 0# 3x + y = 25Wednesday, February 3, 2010Review: duality•Use multipliers to write combined constraints•Constrain multipliers to give us a bound on objective•Optimize to get tightest bound3Thursday, February 11, 2010Review: duality•Primal feasible ! primal opt:# •Dual opt ! dual feasible:# •Primal feasible (& opt) ! dual feasible (& opt):# •If primal opt = dual opt:# 4Thursday, February 11, 2010Matrix form•Primal:#minx c’x s.t. Ax ! b•Multipliers: •Linear comb. of constrs:•Lower bound on obj:•Dual:5Thursday, February 11, 2010Dual dual•Dual:#maxy b’y s.t. A’y = c, y ! 0•Multipliers:•Linear comb. of constrs:•Upper bound on obj:•Primal:6Thursday, February 11, 2010Geometric interpretation•min 3y s.t.#–x + 2y ! 0#x + y ! 27Thursday, February 11, 2010Geometric interpretation•min x+3y s.t.#–x + 2y ! 0#x + y ! 28Thursday, February 11, 2010Geometric interpretation•a * constr1 + b * constr2# •Do this until:# •In dimension d# 9Thursday, February 11, 2010More constraints•min x+3y s.t.#–x + 2y ! 0#x + y ! 2#–2x + y ! –4•Interpret: 0 dual variable =10Thursday, February 11, 2010Complementary slackness•Primal-dual pair:#min c’x s.t. Ax ! b#max b’y s.t. A’y = c, y ! 0•Let x be primal optimal, y be dual optimal#define s = •Then: at most one of or•Usual statement:11Thursday, February 11, 2010LP duality cheat sheetmin c’x + d’y s.t.Ax + By ! pEx + Fy = qx free, y ! 0max p’v + q’w s.t.A’v + E’w = cB’v + F’w " dv ! 0, w freeSwap RHS and objective Transpose constraint matrixSwap max/min +ve vars yield ", free vars yield = 12Thursday, February 11, 2010LP duality summaryPrimal" " " Dualmin problemmax problemconstraint#$ constraint#! constraint" = constraintvariable13Thursday, February 11, 2010LP duality summaryPrimal" " " Dualtight constraintslack constraintzero/nonzero variableinfeasible problemunbounded problemfinite optimal value14Thursday, February 11, 2010What about QP duality?•min x2 + y2 s.t. # x + 2y ! 2# x, y ! 0•How can we lower-bound OPT?#recall: supporting hyperplane thm: for x on boundary of convex set C,#apply to epigraph: { (x, z) | z ! f(x) }15Thursday, February 11, 2010What about QP duality?•min x2 + y2 s.t. # x + 2y ! 2# x, y ! 0•How can we lower-bound OPT?16Thursday, February 11, 2010Can bound at any point•min x2 + y2 s.t. # x + 2y ! 2# x, y ! 0•Try Taylor @ (x, y) = (v, w)17Thursday, February 11, 2010SVM duality•Recall: min" " s.t.•Taylor bound objective:•Linear comb. of constraints:•To get bound, need:•So, ||w||2/2 !•Dual: max s.t.18Thursday, February 11, 2010Interpreting SVM dual•max$,v !i $i – ||v||2/2 s.t.#!i $iyi = 0#!i $iyixij = vj # "j#$i ! 0# # "iWhat are optimal $, v?!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$19Thursday, February 11, 2010Interpreting SVM dual•max$,v !i $i – ||v||2/2 s.t.#!i $iyi = 0#!i $iyixij = vj # "j#$i ! 0# # "iWhat are optimal $, v?!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$19Thursday, February 11, 2010Optimal b!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$20Thursday, February 11, 2010Optimal b!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$!! !"#$ " "#$! !#$% %#$ &!!!"#$""#$!!#$%%#$20Thursday, February 11,