DualityVector optimizationConvex Optimization EE364a:Review Session 4Using CVXStanford UniversityWinter Quarter, 2/5/20131OutlineDualityVector optimization2OutlineDualityVector optimizationDuality 3Dual of maximum entropy IThe concave function “entropy” is defined asH(p) = −nXi=1pilog pi.IH(p) is undefined if pi< 0 for some i ∈ {1, 2, . . . , n}.IBy convention 0 log 0 = 0.Duality 4Dual of maximum entropy IIWe shall find the dual of the following entropy maximizationproblem.minimizep∈RnnXi=1pilog pisubject to Ap  b1Tp = 1(The constraint p  0 is implicit.)Duality 5Dual of maximum entropy IIIInterpretation:minimizep∈RnnXi=1pilog pisubject to Ap  b1Tp = 1Let X be a random variable with P(X = j) = pjand Aij= fi(j).Then roughly speaking the problem finds the random variablewith maximum entropy (closest to the uniform distribution)under the constraint that E[fi(X )] ≤ bifor i = 1, 2, . . . m.Duality 6Dual of maximum entropy IVWe form the Lagrangian and collect the terms.L(p, µ, ν) =nXi=1pilog pi+ µT(Ap − b) + ν(1Tp − 1)= −µTb − ν +nXi=1pilog pi+ (µTA)ipi+ νpi= −µTb − ν +nXi=1pi(log pi+ (µTA)i+ ν)Duality 7Dual of maximum entropy VTo minimize we differentiate and equate the result to 0.∂∂piL(p, µ, ν) = 1 + log pi+ (µTA)i+ ν = 0p?i= exp(−(ATµ)i− ν − 1)ISince p? 0 we are within the domain of H(p).ISecond derivative test is unnecessary due to convexity.Duality 8Dual of maximum entropy VIFinally we plug in p?infpL(p, µ, ν) = L(p?, µ, ν)= −µTb − ν −nXi=1exp(−(ATµ)i− ν − 1)and obtain the dual problem.maximizeµ∈Rm, ν ∈R− µTb − ν −nXi=1exp(−(ATµ)i− ν − 1)subject to µ  0Duality 9Dual of maximum entropy VIIBetween the primal,minimizep∈RnnXi=1pilog pisubject to Ap  b1Tp = 1,and the dual problem,maximizeµ∈Rm, ν ∈R− µTb − ν −nXi=1exp(−(ATµ)i− ν − 1)subject to µ  0,does strong duality hold?Duality 10Dual of maximum entropy VIIIStrong duality may not hold.ISlater’s constraint qualification can fail is 2 waysIThe problem is simply infeasible.IThere is no feasible point such that p  0.IIf so, strong duality may or may not hold; we don’t know.IStrict feasibility of the constraint Ap  b can bedisregarded since it is a linear.IThe strict feasiblitiy p  0 cannot be disregarded since itcomes from the requirement p ∈ relint D, where D is thedomain of the entropy function.Duality 11Dual of maximum entropy VIIIStrong duality may not hold.ISlater’s constraint qualification can fail is 2 waysIThe problem is simply infeasible.IThere is no feasible point such that p  0.IIf so, strong duality may or may not hold; we don’t know.IStrict feasibility of the constraint Ap  b can bedisregarded since it is a linear.IThe strict feasiblitiy p  0 cannot be disregarded since itcomes from the requirement p ∈ relint D, where D is thedomain of the entropy function.Duality 11Dual of maximum entropy VIIIStrong duality may not hold.ISlater’s constraint qualification can fail is 2 waysIThe problem is simply infeasible.IThere is no feasible point such that p  0.IIf so, strong duality may or may not hold; we don’t know.IStrict feasibility of the constraint Ap  b can bedisregarded since it is a linear.IThe strict feasiblitiy p  0 cannot be disregarded since itcomes from the requirement p ∈ relint D, where D is thedomain of the entropy function.Duality 11Dual of maximum entropy VIIIStrong duality may not hold.ISlater’s constraint qualification can fail is 2 waysIThe problem is simply infeasible.IThere is no feasible point such that p  0.IIf so, strong duality may or may not hold; we don’t know.IStrict feasibility of the constraint Ap  b can bedisregarded since it is a linear.IThe strict feasiblitiy p  0 cannot be disregarded since itcomes from the requirement p ∈ relint D, where D is thedomain of the entropy function.Duality 11Dual of maximum entropy VIIIStrong duality may not hold.ISlater’s constraint qualification can fail is 2 waysIThe problem is simply infeasible.IThere is no feasible point such that p  0.IIf so, strong duality may or may not hold; we don’t know.IStrict feasibility of the constraint Ap  b can bedisregarded since it is a linear.IThe strict feasiblitiy p  0 cannot be disregarded since itcomes from the requirement p ∈ relint D, where D is thedomain of the entropy function.Duality 11Dual norm of k · k∞IIWe shall show that the dual norm of k · k∞is k · k1viaLagrange duality.IDisclaimer: This can be proven with much simplerarguments. The purpose of this example is solelypedagogical.Duality 12Dual norm of k · k∞IIBy definition, the dual norm, which we denote as kxk∞,∗, ismaximizey∈RnyTxsubject to kyk∞≤ 1Duality 13Dual norm of k · k∞IIITaking the dual of a maximization problem is error prone. So weflip the sign and make it a minimization problem.minimizey∈Rn− yTxsubject to kyk∞≤ 1Duality 14Dual norm of k · k∞IVThe norm is unwieldy. We transform it into an explicitly linearconstraint.minimizey∈Rn− yTxsubject to − 1  y  1Duality 15Dual norm of k · k∞VWe proceed to minimize the LagrangianL(y, µ+, µ−) = −xTy − µT+(1 − y) − µ−(1 + y)= −(x − µ++ µ−)Ty − 1Tµ+− 1Tµ−infyL(y, µ+, µ−) =−1Tµ+− 1Tµ−if x = µ+− µ−−∞ otherwiseDuality 16Dual norm of k · k∞VISo we arrive at the dual problem:maximizeµ+,µ−∈Rn− 1Tµ+− 1Tµ−subject to x = µ+− µ−µ+, µ− 0Duality 17Dual norm of k · k∞VIILet’s not forget that since we had flipped the sign of the primalwe should do the same with the dual.minimizeµ+,µ−∈Rn1Tµ++ 1Tµ−subject to x = µ+− µ−µ+, µ− 0Duality 18Dual norm of k · k∞VIIIIf you think about this carefully,minimizeµ+,µ−∈Rn1Tµ++ 1Tµ−subject to x = µ+− µ−µ+, µ− 0= kxk1Duality 19Dual norm of k · k∞IXBetween the primal,maximizey∈RnyTxsubject to kyk∞≤ 1,and dual problem,minimizeµ+,µ−∈Rn1Tµ++ 1Tµ−subject to x = µ+− µ−µ+, µ− 0,does strong duality hold?Duality 20Dual norm of k · k∞XIYes. We had transformed the primal problem into anequivalent problem with only linear constraints. So Slater’sconstraint qualification holds if the primal problem isfeasible and it is.INow we can safely conclude that the dual norm of k · k∞isindeed k · k1.Duality 21OutlineDualityVector optimizationVector optimization