椭球法应用-课件

椭球法应用Optimization-Lecture 4,Part 1M.Pawan KumarSlides available online“Recap”of Linear ProgrammingPolyhedronAx bA:m x n matrixb:m x 1 vectorBounded Polyhedron=PolytopeAx bA:m x n matrixb:m x 1 vectorVertexz is a vertex of P=x,Ax bz is not a convex combination of two points in PThere does not exist x,y P and 0 1x z and y zsuch that z=x+(1-)y Vertexz is a vertex of P=x,Ax bAz is a submatrix of AContains all rows of A such that aiTz=biRecall A is an m x n matrixVertexz is a vertex of PRank of Az=nProof?See“hidden”slidesLinear ProgrammingDualitySolving the LPOutlineLinear ProgramMaximize a linear functionOver a polyhedral feasible regions.t.A x bmaxx cTxA:m x n matrixb:m x 1 vectorc:n x 1 vectorObjective functionConstraintsx:n x 1 vectorExample4x1 x2 8maxx x1+x22x1+x2 105x1-2x2 -2x1 0 x2 0s.t.What is c?A?b?Examplex1 0 x2 0Example4x1 x2=8x1 0 x2 0Example4x1 x2 8x1 0 x2 0Example4x1 x2 82x1+x2 10 x1 0 x2 0Example4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0Example4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0maxx x1+x2x1+x2=0Example4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0maxx x1+x2x1+x2=8Optimal solutionLinear ProgrammingDualitySolving the LPOutlineExample2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.3 x2 x7 xScale the constraints,add them up3x1+x2+2x3 90Upper bound on solutionExample2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.1 x1 xScale the constraints,add them up3x1+x2+2x3 36Upper bound on solutionExample2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.1 x1 xScale the constraints,add them up3x1+x2+2x3 36Tightest upper bound?Example2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.y4y1y2y3y5y6y1,y2,y3,y4,y5,y6 0We should be able to add up the inequalitiesExample2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.y4y1y2y3y5y6-y1+y4+2y5+4y6=3Coefficient of x1 should be 3Example2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.y4y1y2y3y5y6-y2+y4+2y5+y6=1Coefficient of x2 should be 1Example2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.y4y1y2y3y5y6-y3+3y4+5y5+2y6=2Coefficient of x3 should be 2Example2x1+2x2+5x3 24maxx 3x1+x2+2x34x1+x2+2x3 36-x1 0,-x2 0,-x3 0 x1+x2+3x3 30s.t.y4y1y2y3y5y6miny 30y4+24y5+36y6Upper bound should be tightestDualminy 30y4+24y5+36y6s.t.y1,y2,y3,y4,y5,y6 0-y1+y4+2y5+4y6=3-y2+y4+2y5+y6=1-y3+3y4+5y5+2y6=2Original problem is called primalDual of dual is primalDuals.t.A x bmaxx cTxDual-yT(A x b)maxx cTxminy0KKT Condition?ATy=cminy0bTys.t.ATy=cminy0bTys.t.ATy=cs.t.A x bmaxx cTxPrimalDualStrong Dualityminy0bTys.t.ATy=cs.t.A x bmaxx cTxPrimalDualp=d=If p or d ,then p=d.Skipping the proofThink back to the intuition of dualQuestions.t.A1 x b1maxx cTxA2 x b2A3 x=b3Dual?Linear ProgrammingDualitySolving the LPOutlineGraphical Solution4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0maxx x1+x2x1+x2=8Optimal solution at a vertexGraphical Solution4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0maxx x1x1=3Optimal solution at a vertexGraphical Solution4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0maxx x2x2=6Optimal solution at a vertexGraphical Solution4x1 x2 82x1+x2 105x1-2x2 -2x1 0 x2 0An optimal solution always at a vertexProof?maxx cTxDantzig(1951):Simplex MethodSearch over vertices of the polyhedraWorst-case complexity is exponentialSmoothed complexity is polynomialKhachiyan(1979,1980):Ellipsoid MethodPolynomial time complexityLP is a P optimization problemKarmarkar(1984):Interior-point MethodPolynomial time complexityCompetitive with Simplex MethodSolving the LPPlenty of standard software availableMosek()C+APIMatlab APIPython APIFree academic licenseSolving the LP