### Create a StudySoup account

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

Already have a StudySoup account? Login here

# OPTIMIZATION THEORY CAAM 560

Rice University

GPA 3.58

### View Full Document

## 151

## 0

## Popular in Course

## Popular in Applied Mathematics

This 9 page Class Notes was uploaded by Walker Witting on Monday October 19, 2015. The Class Notes belongs to CAAM 560 at Rice University taught by Staff in Fall. Since its upload, it has received 151 views. For similar materials see /class/225011/caam-560-rice-university in Applied Mathematics at Rice University.

## Popular in Applied Mathematics

## Reviews for OPTIMIZATION THEORY

### 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/19/15

Chapter 1 Problems 11 H N 00 7 Distribution of this material is restricted It is for the use of students currently enrolled in CAAM 460 Problems Prove that a convergent sequence is a Cauchy sequence Let A be an n gtlt 71 matrix Prove that g ltAxgt is a continuous functional on IR Consider a function f R 6 R a Assume that f is homogeneous Show that f must have the form f ax for some xed real number 1 Hence f is additive and consequently linear b Assume that f is additive and continuous Show that f must have the form f ax for some xed real number a Additive and continuous implies linear Hint Establish the result for the integers then move to the ra tionals and nally move to the reals using continuity Hamel Show that there exists a function f R a R that is additive but not linear Outline of Solution Consider the following theorem CT CT 1 Draft 7 distribution restricted to CAAM 560 students Theorem Every vector space in which the scalar eld is the reals or the rationals has a basis To show that such an f exists consider the vector space in which the vectors are the real numbers and the scalars are the rationals By the theorem above this space must have a basis Choose one element of the basis and de ne f to be equal to one on that element and zero on all the other basis elements Extend the function to all the reals as follows If x a1 gt1 0445 where 151 n are elements of our basis and 041 04 are rationals then fz a1f 1 anf n Show that f is additive on the reals but that f is not of the form fz ax hence it is not homogeneous and therefore not linear on the reals Consider the linear program in standard form minimize cTz subject to Ax b x 2 0 Clearly this is a continuous optimization problem State an equivalent discrete optimization problem Give a reasonably complete argument concerning the equivalence of the problems You do not need to prove all statements rigorously but your argument should explain the neces sary steps Formulate the problem of nding the smallest eigenvalue of a symmetric matrix A as a constrained continuous optimization problem having a quadratic objective function and a single quadratic equality constraint Hint Consider the Rayleigh quotient Consider the linear regression problem of approximating the data z1y1 zmym with a function of the form fz a bx We may solve this problem by asking for values of a and b that give the fz mini mizing the Zp norm of the residuals Speci cally we want to nd ab that minimizes Gpa7b ll 1196071117 fmym Hp Draft 7 distribution restricted to CAAM 560 students 3 00 H 0 Recall that if z 217 72m7 then 1 Hsz l21l W for 1 p lt co and Hzlloo lrgg lzll a Show that for p 2 the linear regression problem can be formu lated as a quadratic programming problem b Show that for p 1 the linear regression problem is equivalent to a linear programming problem c Show that for p 00 the linear regression problem is equivalent to a linear programming problem Here7 equivaler1t77 means that one can construct a linear programming problem that has the same solution set as the original problem State and classify a The isoperimetric problem from the calculus of variations b The Traveling Salesman problem c An interesting problem of your choice lnclude reference Give a speci c example of a semi in nite programming problem Consider the collection of real valued functions de ned and continuous on the interval 071 We call this space C071 a Demonstrate that this collection of functions can be viewed as a real vector space De ne scalar multiplication and vector addition in a meaningful manner and then argue that vector addition and scalar multiplication are closed ie7 the result is something in the space Demonstrate that this vector space is in nite dimensional You can make this problem hard or easy think about your approach before you spend considerable time on it b Argue that the vector space of the reals with the rationals as the scalar eld has Hamel dimension equal to c7 the cardinality of the continuum 12 Show that the dimension of 30 is NO 13 H r H CH Draft 7 distribution restricted to CAAM 560 students Show that the dimension of 3B is c Hint Show that 1219197 t E 01 is a linearly independent set You can do this using the fundamental theorem of algebra concern ing the number of roots a polynomial can have Then show that the cardinality of IR is 07 the cardinality of the continuum Show that the dimension of C071 is c Hint For each 1217 construct a continuous function ft on 01 by letting ft1m t for m 17 27 7 letting f0 0 and extending ft to all of 01 by linear interpolation These functions are linearly independent of Problem 13 Hence the dimension of C071 is at least 0 New show that the cardinality by C071 is no greater than c To do this7 rst argue that two continuous functions are the same if and only if they agree on the rationals Hence C07 1 can be mapped one to one into R So the cardinality of C071 is less than or equal to c This shows that the dimension ofC01 is c Prove that if X and Y are normed linear spaces7 then LXY the space of all bounded linear operators from X into Y is also a normed linear space with the norm W1 for L e LXY HLH sup 7 m70 Consider a linear operator T X a Y7 where X and Y are normed linear spaces Show that the following three notions of the induced operator norm are equivalent a HTHsupMz7ampo Hill 0 HTH supfllT96ll i Hill 1 c inf M S for all z E X Consider the m gtlt 71 matrix A We may think of A as an operator from R into R a Show that the operator norm of A when A 171 a 1m is HAH1 maXZa ij1727n i1 Draft 7 distribution restricted to CAAM 560 students 5 H 00 H K 2 21 2 2 C40 0 E0 b Show that the operator norm of A when A 001 a Z m is maXZalj 127m j1 c Show that the operator norm of A when A 01 a 071 is mam 7 where Am is the largest eigenvalue of ATA or singular value of A Hint Consider the Rayleigh quotient HAM llAllz Show that the norm functional on any normed linear space is continu ous Show that Ca7b the set of continuous functions on ab is complete with the norm Hfll max l t l ia S t S b That is7 show that Claw is a Banach space Show that in any normed space a scalar multiplication is a continuous operation b vector addition is a continuous operation Let X be a normed linear space Prove that X is an inner product space if and only if the norm satis es the parallelogram law H96 yll2 H96 yllz 2M2 2Hyll2 Show that a normed linear space is a topological linear space Let X and Y be normed linear spaces A functional f X a R is said to be i subadditive if fz y S f fy for all my 6 X7 and ii positively homogeneous if ax afz for all 04 gt 0 3 CT 3 03 Draft 7 distribution restricted to CAAM 560 students Prove a A subadditive and homogeneous functional is linear b An additive and positively homogeneous functional is linear Let P be the space of all polynomials7 with the norm given by Hfll maXlftl i a S t S b Show that P is not complete Hint Consider the Weierstrass Approximation Theorem Let X be the inner product space consisting ofthe continuous functions on the interval 01 with the inner product de ned by 0 ggt 0 ftgtdt Show that X is not complete Show that the two norms given in Example 013 are equivalent7 ie7 the exists m7 M gt 0 satisfying mlllflll S llfll S Mlllflll for all f E Clla7b Let A be a subset of a normed linear space Show that the following three notions of closed sets are equivalent a The complement of A is open b If C A and M a x then x E A c A contains all of its cluster points Let A be a subset of IR compactness are equivalent Show that the following three notions of a Every open covering of A has a nite subcovering b Every sequence in A has a subsequence that converges to a point in A Draft 7 distribution restricted to CAAM 560 students 7 c A is closed and bounded 29 Let f be an operator from a normed linear space X into a normed 3 3 O H linear space Y Prove that the following three notions of continuity are equivalent a The usual 66 de nition b If xn a s then fz a c If B is an open subset of Y then f 1B x E X f E B is an open subset of X Suppose that f R a R and its rst 71 derivatives are continuous Show that f has a local extremum at 0 if and only if n is even where n is the order of the rst nonvanishing derivative at 0 The function f has a maximum at 0 if f x0 lt 0 and a minimum if f x0 gt 0 Show that all norms on R are equivalent in the sense that given two norms say 39 lla and H17 there exist positive constants m and M such that lt lt Mllxlla for all z 6 IR Hint The purpose of this problem is to demonstrate that norm equiv alence in nite dimensional spaces is really an optimization theoretic property We will base the proof on Proposition for Euclidean 71 space For an arbitrary norm H consider the functional Ms on the set S x 1 Here H2 is the Euclidean norm Show that b is continuous in the 2 norm and that S is closed and bounded in the 2 norm and therefore by Proposition b must have a minimizer and maximizer on S Use the result above to show that if an operator from R to Rm is continuous in one norm then it it continuous in all norms Bibliography 1 Magnus R Hestenes Optimization Theory The Finite Dimensional Case Wiley lnterscience John Wiley Kc Sons New York 1975 2 R C James Characterizations of re exivity Studia Math 232057216 19631964 E J M Ortega and W C Rheinboldt Iterative solution of nonlinear equa tions in several variables Society for Industrial and Applied Mathematics SIAM Philadelphia PA 2000 Reprint of the 1970 original E Richard A Tapia and James R Thompson Nonparametric probability density estimation Johns Hopkins University Press Baltimore Md 1978 E James R Thompson and Richard A Tapia Nonparametric function es timation modeling and simulation Society for Industrial and Applied Mathematics SIAM Philadelphia PA 1990 249 Index parallelogram law7 5 250

### 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 bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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