Review of duality so farSet dualitySet dualityLP/QP objectiveDual functionsFenchel’s inequalityDuality and subgradientsDuality examplesMore examplesIndicator functionsDuals of indicatorsPropertiesWorking with dual functionsWorking with dual functionsAn odd-looking operationInfimal convolution exampleDual of infimal convolutionConvex program dualityDuality exampleDual functionDual functionENDCP duality w/ cone constraintsEx: 2nd order cone programDuality of normsDual norm examplesDual norm examplesDual norm examplesCuboctahedron||y||* is a normDual-norm ballsMulti-criterion optimizationBuying the perfect carPareto optimalityPareto examplesScalarizationEND***Epigraph representationConvex program dualityExample: cone programsExample: SVM dualityExample: QP dualityReview of duality so far• LP/QP duality, cone duality, set duality• All are halfspace bounds– on a cone– on a set– on objective of LP/QPSet dualitySet dualityLP/QP objectivemin z s.t.z ≥ x - 1z ≥ 3 - 2xDual functions• Arbitrary function F(x)• Dual is F*(y) = • For example: F(x) = xTx/2•F*(y) =Fenchel’s inequality• F*(y) = supx[xTy-F(x)]Duality and subgradients• Suppose F(x) + F*(y) – xTy= 0Duality examples• -1/2 – ln(x)•ex• x ln(x) – xMore examples•F(x) = xTQx/2 + cTx, Q psd:• F(X) = –ln |X|, X psd:Indicator functions• Recall: for a set S,IS(x) =• E.g., I[-1,1](x):Duals of indicators•Ia(x), point a:•IK(x), cone K:•IC(x), set C:Properties•F(x) ≥ G(x) F*(y) G*(y)• F* is closed, convex• F** = cl conv F (= F if F closed, convex)• If F is differentiable:Working with dual functions• G(x) = F(x) + k• G(x) = k F(x) k > 0• G(x) = F(x) + aTxWorking with dual functions•G(x1, x2) = F1(x1) + F2(x2)An odd-looking operation• Definition: infimal convolution• E.g., F1(x) = I[-1,1](x), F2(x) = |x|Infimal convolution example•F1(x) = I≤0(x), F2(x) = x2F1F F2F1F F2Dual of infimal convolution• G(x) = F1(x) F F2(x)•G*(y) =• G(x) = F1(x) + F2(x) G*(y) =Convex program duality• min f(x) s.t.Ax = bgi(x) ≤ 0i ∈