Stru Des Sens AnaOpt
Stru Des Sens AnaOpt EGM 6365
Popular in Course
Popular in Engineering & Applied Science
This 4 page Class Notes was uploaded by Rollin Mann DVM on Saturday September 19, 2015. The Class Notes belongs to EGM 6365 at University of Florida taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/207077/egm-6365-university-of-florida in Engineering & Applied Science at University of Florida.
Reviews for Stru Des Sens AnaOpt
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/19/15
3 LargerScole Algorithms LargeScale Linear Programming Linear programming is de ned as Aeq X beq min fIX such that Aineq XS bineq IS XS u 314 The largeiscale method is based on LIPSOL 11 which is a variant of Mehrotra s predictoricorrector algorithm 7 a primalidual interioripoint method Main Algorithm The algorithm begins by applying a series of preprocessing steps see quotPreprocessingquot on page 3717 After preprocessing the problem has the form T A X b min f X such that 315 0 S XS u The upper bounds constraints are implicitly included in the constraint matrix A with the addition of primal slack variables 5 Eq 3715 becomes AX b min fIX such that Xs u 316 X20520 which is referred to as the primal problem Xconsists of the primal variables and 5 consists of the primal slack variables The dual problem is AT ye w Z f 22 0 W2 0 max bTy 7 LITW such that 317 where y and wconsist of the dual variables and Z consists of the dual slacks The optimality conditions for this linear program ie the primal Eq 3716 and the dual Eq 3717 are LargerScole Linear Programming A X7 b X 57 u F ATy w Z f 0 X z s W 39 i i V 318 X121 51 X20 Z20 520 W20 where Xizi and 51W1 denote componentiwise multiplication The quadratic equations iji 0 and st1 0 are called the complementarityconditions for the linear program the other linear equations are called the feasibility conditions The quantity XTZ STW is the duality gap which measures the residual of the complementarity portion owahen X2 5 W20 The algorithm is a primalidual algorithm meaning that both the primal and the dual programs are solved simultaneously It can be considered a Newtonilike method applied to the lineariquadratic system FX y Z s W 0 in Eq 3718 while at the same time keeping the iterates X Z W and spositive thus the name interioripoint method T he iterates are in the strictly interior region represented by the inequality constraints in Eq 3716 The algorithm is a variant of the predictoricorrector algorithm proposed by Mehrotra Consider an iterate V X y Z s W whereX Z s W gt 0 We rst compute the soicalled prediction direction T 71 AV F V FV which is the Newton direction then the soicalled corrector direction T 1 A Ave 7F V FVAVP7LL8 where LL gt 0 is called the centeringparameter and must be chosen carefully E is a zeroione vector with the ones corresponding to the quadratic equations in F V ie the perturbations are only applied to the complementarity conditions 3 LargerScole Algorithms which are all quadratic but not to the feasibility conditions which are all linear We combine the two directions with a stepilength parameter at gt 0 and update Vto obtain the new iterate V 7 V 7 v 0LAVP Ave where the stepilength parameter at is chosen so that VXyZSW satis es X39 2 5 Wgt0 In solving for the steps above the algorithm computes a sparse direct factorization on a modi cation of the Cholesky factors of A A T If A has dense columns it instead uses the ShermaniMorrison formula and if that solution is not adequate the residual is too large it uses preconditioned conjugate gradients to nd a solution The algorithm then repeats these steps until the iterates converge The main stopping criteria is a standard one Ilfbll IIFAI Ilfull IrTXAbTwawl maxlt1llbllgt maxlt1llrngt maxlt1llullgt maxgj llewawl where S to rb AXib T rf A yew271 ru xsiu are the primal residual dual residual and upperibound feasibility respectively and fTXi bTy LITW is the difference between the primal and dual objective values and to is some tolerance The sum in the stopping criteria measures the total relative errors in the optimality conditions in Eq 3718 LargerScole Linear Programming Preprocessing A number of preprocessing steps occur before the actual iterative algorithm begins The resulting transformed problem is one where I All variables are bounded below by zero I All constraints are equalities I Fixed variables those with equal upper and lower bounds are removed I Rows of all zeros in the constraint matrix are removed I The constraint matrix has full structural rank I Columns of all zeros in the constraint matrix are removed I When a significant number of singleton rows exist in the constraint matrix the associated variables are solved for and the rows removed While these preprocessing steps can do much to speed up the iterative part of the algorithm if the Lagrange multipliers are required the preprocessing steps must be quotundonequot since the multipliers calculated during the algorithm are for the transformed and not the original problem Thus if the multipliers are not requested this transformation back will not be computed and may save some time computationally