### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Intro Nonlinear Prog IOE 519

UM

GPA 3.76

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Industrial Engineering

This 3 page Class Notes was uploaded by Loy King on Thursday October 29, 2015. The Class Notes belongs to IOE 519 at University of Michigan taught by Marina Epelman in Fall. Since its upload, it has received 16 views. For similar materials see /class/231592/ioe-519-university-of-michigan in Industrial Engineering at University of Michigan.

## Reviews for Intro Nonlinear Prog

### 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: 10/29/15

IOE 519 NLP Winter 2009 51 7 Projection methods for linear equality constrained problems 71 Optimization over linear equality constraints Suppose we want to solve P min x st Ax 1 Assume that the problem is feasible Then without loss of generality matrix A has full row rank The KKT conditions are necessary for this problem and are as follows Ari b Vf AT7T39 0 We therefore wish to nd such a KKT point 9 7739 Suppose we are at an iterate x where Ax b ie x is a feasible point Just like in the steepest descent algorithm we wish to nd a direction d which is a direction of steepest descent of the objective function but in order to stay in the feasible region we also need to have Ad 0 Therefore the direction nding problem takes form min VfxTd st dT I d g 1 Ad 0 The rst constraint of the problem requires that the search direction d has length l in the Euclidean norm We can however adapt a more generalized approach and replace the Euclidean norm VdTI Vde with a more general norm HdHQ xdTQd where Q is an arbitrary symmetric pd matrix Using this general norm in the direction nding problem we can state the projected steepest descent algorithm Step 0 Given 950 set k lt 0 Step 1 Solve the direction nding problem de ned at point 95 DFPM d1 argmin VfxkTd st dTQd g 1 Ad 0 If VfxkTdk 0 stop 95 is a KKT point Step 2 Choose stepsize 06 by performing an exact or inexact line search Step 3 Set KIWI lt 95k o dk k lt k 1 Go to Step 1 Notice that if Q I and the equality constraints are absent the above is just the steepest descent algorithm The choice of name projected steepest descent may not be apparent at this point but will be clari ed later IOE 519 NLP Winter 2009 52 72 Analysis of DFP Notice that the search direction at each iteration is the solution of a nonlinearly constrained opti mization problem DFPM above Note that DFPM is a convex program and d 0 is a Slater point Therefore the KKT conditions are necessary and suf cient for optimality These conditions are we omit the superscript k for simplicity Ad 0 clTQd g 1 Vfx ATir Q Qd 0 4 2 0 m1 7 dTQd 0 Let d solve these equations With multipliers and 7139 Proposition 71 x is a KKT point of P and only VfacTd 0 where d is the KKT point of DFPm Proof First suppose x is a KKT point of Then there exists v such that Ar 1 vm 14 0 Let d be any KKT point of DFPI together With multipliers 7139 and Then in particular Ad 0 Therefore vm l AT UTCl UTACl 0 To prove the converse suppose that d together With multipliers 7139 and is a KKT point of DFPE and VfacTd 0 Then 0 vm ATW 2 QdTd vm z TAd 2ngch 2g and so 0 Therefore Ax b and AT7139 0 ie the point 95 together With multiplier vector 7139 is a KKT point of I Proposition 72 x is a KKT point of P and only 0 where B is the appropriate KKT multiplier of DFPE Proposition 73 fat is not a KKT point of P then d is a descent direction where d is the KKT point of DFPE Proposition 74 The projected steepest descent algorithm has the same convergence properties and the same linear convergence as the steepest descent algorithm Under the same conditions as in the steepest descent algorithm the iterates converge to a KKT point of P and the convergence rate is linear with a convergence constant that is bounded in terms of eigenvalues identically as in the steepest descent algorithm 73 Solving DFPm Approach 1 to solving DFP solving linear equations IOE 519 NLP Winter 2009 53 Create the system of linear equations Qd ATi39 7Vfx 5 Ad 0 and solve this linear system for d7 7 by any method at your disposal If Qd 07 then ATir 0 and so at is a KKT point of If 07 then rescale the solution as follows d J mi 7139 7 2 amp Proposition 75 d771397 de ned above satisfy HgtY Note that the rescaling step is not necessary in practice7 since we use a line search Approach 2 to solving DFP Formulas Let PQ Q4 7 Q lATMQ lATVIAQ l 7 V IDTPQW ID 7 2 7T AQPIATVIAQ VVHIN lf gt 07 let d 7PQVfx xVf96TPQV 96 lf 0letd0 Proposition 76 PQ is symmetric and positive semide nite Hence 2 0 Proposition 77 d7777 de ned above satisfy 74 The Variable Metric Method In the projected steepest descent algorithm7 the direction d must be contained in the ellipsoid EQ d E Rquot dTQd g 17 Where Q is xed for all iterations In a variable metric method7 Q can vary at every iteration The variable metric algorithm is Step 0 Given 950 set k H 0 Step 1 Choose a pd symmetric matrix Perhaps Q ie7 the choice of Q may depend on the current point Solve the direction nding problem de ned at point at DFPM d1 argmin VfackTd st dTQd g 1 Ad 0

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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