### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Stru Des Sens AnaOpt EGM 6365

UF

GPA 3.79

### View Full Document

## 9

## 0

## 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

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.