A First Course in Optimization: Answers to Selected Exercises

1 A First Course in optimization : Answers to Selected ExercisesCharles L. ByrneDepartment of Mathematical SciencesUniversity of Massachusetts LowellLowell, MA 01854 December 2, 2009(The most recent draft is available as a pdf file )2 Contents1 Preface32 exercise .. 53 optimization Without Exercises .. 74 Geometric exercise .. 135 Convex References Used in the Exercises .. Exercises .. 166 Linear Needed References .. Exercises .. 237 Matrix Games and Some Exercises .. 258 Exercises .. 279 Convex Exercises .. 2910 Fenchel Exercises .. 33iCONTENTS111 Convex Referenced Results .. Exercises .. 3512 Iterative Referenced Results .. Exercises .. 3913 Modified-Gradient Algorithms4314 Quadratic Programming4515 Solving Systems of Linear Regularizing the ART.

2 Exercises .. 4716 Conjugate-Direction Proofs of Lemmas .. Exercises .. 5317 Sequential Unconstrained Minimization Exercises .. 5718 Likelihood Maximization5919 Referenced Results .. Exercises .. 6220 Convex Feasibility and Related A Lemma .. Exercises .. 672 CONTENTSC hapter 1 PrefaceIn the chapters that follow you will find solutions to many, but not all,of the Exercises in the text. Some chapters in the text have no Exercises ,but those chapters are included here to keep the chapter numbers the sameas in the text. Please note that the numbering of Exercises within eachchapter may differ from the numbering in the text itself, because certainexercises have been 1. PREFACEC hapter the functionf(x)defined byf(x) =e x, forx >0and byf(x) = ex, forx <0.

3 Show that 1 = lim infx 0f(x)and1 = lim supx 0f(x).As we approachx= 0 from the left, the limit is 1, while as we approachfrom the right, the limit is +1. Therefore, the setSisS={ 1,0,1}. Thegreatest lower bound forSis its minimum member, 1, while the leastupper bound is its maximum member, + 1,2, .., letAn={x| x a 1n},and let nand nbe defined by n= inf{f(x)|x An},and n= sup{f(x)|x An}. a) Show that the sequence{ n}is increasing, bounded above byf(a)and converges to some , while the sequence{ n}is decreasing,bounded below byf(a)and converges to some . Hint: use thefact that, ifA B, whereAandBare sets of real numbers, theninf(A) inf(B).56 CHAPTER 2. INTRODUCTION b) Show that and are inS. Hint: prove that there is a sequence{xn}withxninAnandf(xn) n+1n. c) Show that, if{xm}is any sequence converging toa, then there isa subsequence, denoted{xmn}, such thatxmnis inAn, for eachn,and so n f(xmn) n.

4 D) Show that, if{f(xm)}converges to , then . e) Show that = lim infx af(x)and = lim supx af(x).According to the hint in a), we use the fact thatAn+1 An. For b),since nis the infimum, there must be a member ofAn, call itxn, suchthat n f(xn) n+ the sequence{xn}converges toaand the sequence{f(xn)}convergesto .Now suppose that{xm}converges toaand{f(xm)}converges to .We don t know that eachxmis inAm, but we do know that, for eachn,there must be a term of the sequence, call itxmn, that is within1nofa,that is,xmnis inAn. From c) we have n f(xmn) sequence{f(xmn)}also converges to , so that .Finally, since we have shown that is the smallest number inSit followsthat = lim infx af(x).The argument for is 3 optimization the arithmetic mean of a finite set of positive numbers, withxthe smallest of these numbers, andythe largest.

5 Show thatxy A(x+y A),with equality if and only ifx=y= is equivalent to showing thatA2 A(x+y) +xy= (A x)(A y) 0,which is true, sinceA x 0 andA y the functionf(x) =x2+1x2+ 4x+4x,over positivex. Note that the minimum value off(x, y)cannot be foundby a straight-forward application of the AGM Inequality to the four termstaken together. Try to find a way of rewritingf(x), perhaps using morethan four terms, so that the AGM Inequality can be applied to all the product of the four terms is 16, whose fourth root is 2, so the AGMI nequality tells us thatf(x) 8, with equality if and only if all four terms78 CHAPTER 3. optimization WITHOUT CALCULUSare equal. But it is not possible for all four terms to be equal. Instead, wecan writef(x) =x2+1x2+x+1x+x+1x+x+1x+x+ ten terms have a product of 1, which tells us thatf(x) 10,with equality if and only ifx= the maximum value off(x, y) =x2y, ifxandyare restrictedto positive real numbers for which6x+ 5y= (x, y) =xxy=145(3x)(3x)(5y),and45 = 6x+ 5y= 3x+ 3x+ the smallest value off(x) = 5x+16x+ 21,over focus on the First two the smallest value of the functionf(x) = x2+y2,among those values ofxandysatisfying3x y= Cauchy s Inequality, we know that20 = 3x y= (x, y) (3, 1) x2+y2 32+ ( 1)2= 10 x2+y2,with equality if and only if (x, y) =c(3, 1) for some numberc.

6 Then the maximum and minimum values of the functionf(x) = 100 +x2 xover EXERCISES9 The derivative off(x) is negative, sof(x) is decreasing and attains itsmaximum of 10 atx= 0. Asx ,f(x) goes to zero, but never out the product(x+y+z)(1x+1y+1z)and deduce that the least value of this product, over non-negativex,y, andz, is9. Use this to find the least value of the functionf(x) =1x+1y+1z,over non-negativex,y, andzhaving a constant the more general exercise meanof positive numbersa1, .., aNisH= [(1a1+..+1aN)/N] that the geometric meanGis not less the AGM Inequality to show thatH 1 G that(1a1+..+1aN)(a1+..+aN) N2,with equality if and only ifa1=..= we multiply everything out, we find that there areNones, andN(N 1)2pairs of the formaman+anam, form6=n.

7 Each of these pairs hasthe formx+1x, which is always greater than or equal to two. Therefore,the entire product is greater than or equal toN+N(N 1) =N2, withequality if and only if all theanare the that the EquationS=U LUT, can be written asS= 1u1(u1)T+ 2u2(u2)T+..+ NuN(uN)T,( )andS 1=1 1u1(u1)T+1 2u2(u2)T+..+1 NuN(uN)T.( )10 CHAPTER 3. optimization WITHOUT CALCULUSThis is just positive-definite, with positive eigenvalues 1 .. N>0and associated mutually orthogonal norm-one eigenvectorsun. Show thatxTQx 1,for all vectorsxwith x = 1, with equality ifx=u1. Hints: use1 = x 2=xTx=xTIx,I=u1(u1)T+..+uN(uN)T,and Equation ( ).Use the inequalityxTQx=N n=1 n|xTun|2 1N n=1|xTun|2= Example 4 to eigenvectors and can write 4 6 126 9 1812 18 36 = 49(27,37,67)T(27,37,67),so that(2x+ 3y+ 6z)2=|(x, y, z)(2,3,6)T|2= (x, y, z) 4 6 126 9 1812 18 36 (x, y, z) only positive eigenvalue of the matrix is 7 and the corresponding nor-malized eigenvector is (27,37,67)T.

8 Then use exercise Young s InequalitySuppose thatpandqare positive numbersgreater than one such that1p+1q= 1. Ifxandyare positive numbers, thenxy xpp+yqq,with equality if and only ifxp=yq. Hint: use the GAGM one is pretty given constantscandd, find the largest and smallest values ofcx+dytaken over all points(x, y)of the ellipsex2a2+y2b2= the largest and smallest values of2x+yon the circlex2+y2= do these values occur? What does this have to do with eigenvectorsand eigenvalues?This one is similar to exercise a realMbyNmatrixAis stored in the computer it is usuallyvectorized; that is, the matrixA= A11A12.. A1NA21A22.. AMN becomesvec(A) = (A11, A21, .., AM1, A12, A22, .., AM2, .., AMN) that the dot productvec(A) vec(B) =vec(B)Tvec(A)can be ob-tained byvec(A) vec(B) = trace (ABT) = trace (BTA).

9 3. optimization WITHOUT CALCULUSC hapter 4 Geometric that there is no solution to the problem of minimizing the func-tiong(t1, t2) =2t1t2+t1t2+t1,( )overt1>0,t2>0. Cang(t1, t2)ever be smaller than2 2?Show that the only vector that works must have 3= 0, which is answer the second part, begin by showing that ift2 1 theng(t1, t2) 4, and ift1 1, theng(t1, t2) 3. We want to considerthe case in whicht1 0,t2 , and botht1t2and (t1t2) 1remainbounded. For example, we tryt2=1t1(ae t1+ 1),for some positivea. Theng(t1, t2) 2a+1+a+ 1 ast1 0. Whichagives the smallest value? Minimizing the limit, with respect toa, givesa= 2 1, for which the limit is 2 generally, lett2=f(t1)t1,for some positive functionf(t1) such thatf(t1) does not go to zero ast1goes to zero. Then we haveg(t1, t2) =2f(t1)+f(t1) +t1,1314 CHAPTER 4.

10 GEOMETRIC PROGRAMMING which converges to2f(0)+f(0), ast1 0. The minimum of this limit, as afunction off(0), occurs whenf(0) = 2, and the minimum limit is 2 5 Convex References Used in the ExercisesProposition convex hull of a setSis the setCof all convexcombinations of members a givenx, a vectorzinCisPCxif and only if c z, z x 0,( )for allcin the (a, ),z=PHxis the vectorz=PHx=x+ ( a, x )a.( )Lemma (a, ),H0=H(a,0), and anyxandyinRJ, wehavePH(x+y) =PHx+PHy PH0,( )so thatPH0(x+y) =PH0x+PH0y,( )that is, the operatorPH0is an additive operator. In addition,PH0( x) = PH0x,( )so thatPH0is a linear any hyperplaneH=H(a, )andH0=H(a,0),PHx=PH0x+PH0,( )soPHis an affine linear 5. CONVEX SETSL emma 1, .., IletHibe the hyperplaneHi=H(ai, i),Hi0=H(ai,0), andPiandPi0the orthogonal projections ontoHiandHi0, respectively.