an introduction to optimization 4th edition solution manual.pdf

【实例简介】
an introduction to optimization 4th edition solution manual.pdf 最优化导论（第四版）课后习题答案
A are linearly dependent, and Ay is a linear combination of the columns of A). Let a be a solution to Ac=b. Then clearly a+yt is also a solution. This contradicts the uniqueness of the solution. Hence rank A +:By Theorem 2.1, a solution exists. It remains to prove that it is unique. For this, let a and y be solutions, i.e.,A= b and Ay=b. Subtracting, we get A(a-y)=0. Since rank A= n and A has n columns, then -y=0 and hence =y, which shows that the solution is unique 2.3 Consider the vectors ai=1,a∈Rn+1,讠=1,…,k. Since k≥n+2, then the vectors a1,, ak must be linearly independent in Rn+I. llence, there exist a1, .. ak, not all zero, such that 0 The first component of the above vector equation is 2i_i ai=0, while the last n components have the form i-l diai=0, completing the proof 2.4 We first postmultiply M by the matrix Mm-kk Im-k to obtain 7-h,k Mkk O Mm-k, k Im-kMkk O Note that the determinant of the postmultiplying matrix is 1. Next we postmultiply the resulting product m-k O Mkk O O O ME, k otice that NM=(O)(.6 where det The above easily follows from the fact that the determinant changes its sign if we interchange columns, as discusscd in Scction 2. 2. Morcovcr, det (I k)det(mk, k) Mk,k) o Mkk dctM=± dct Mk b. We can see this on the following examples. We assume, without loss of generality that Mm-kk=O and let kb=2. Thus k=1. First consider the case when m= 2. Then we have k, ke O Us det m=-2= det(-M k, k) Next consider the case when m=3. Then m-h =2≠det(-Mk,k) Mkk O Therefore, in general detM≠det(-Mk,k) However, when k= m/2, that is, when all sub-matrices are square and of the same dimension then it is true that etm= det (Mn, k) Sc[121] 2.5 Let A B C D and suppose that each block is k k. John R. Silvester [121] showed that if at least one of the blocks is equal too(zero matrix), thell the desired formula holds. Indeed, if a row or coluMn block is zero, then the determinant, is equal to zero as follows from the determina.nt,'s properties discussed Section 2.2. That, is, if A=B=O, or A=C=O, and so on, then obviously dct M=0. This includes the casc when any thrcc or all four block matrices are zero matrices IfB= or c=o then A B det m= det det (ad) C D The only case left to analyze is when a=O or D=O. We will show that in either case det M =det(-BC) Without loss of generality suppose that D=O. Following arguments of John R. Silvester [121], we premul tiply M by the product of three matrices whose determinants are unity: Ik IkA B o I OI A B He ence a B de A B det(c)det B det(-1k)detC det B Thus we have detaB C O det(bc)=det(CB) 2.6 We represent the given system of equations in the form Aa=b, where 1 and b 1-20-1 Using elementary row operations yield 1121 4 ane A,b 1-20-1-2 from which rank A=2 and rankA, b= 2. Therefore, by Theorem 2.1, the system has a solution We next represent the system of equations as 2+4 Assigning arbitrary values to cs and 4(3=d3, a4=d4), we get 1 1[1-23 4 2+x2 2-11-2 4 2+x ds -od 1-2d3 Therefore, a general solution is d3-寺d4 d 3 d4+ 3 1 0 where d and d4 are arbitrary values 2.7 1. Apply the definition of -a if 0 if-a if >= if a <0 if 0 a if a>>0 2. If>0, then a=a. If a <0, then a=-u>0>a. Hence a>u On the other hand, -u2-a (by the above). Hence, a2--a=-la(by property 1) 3. We have four cases to consider. First, if a, b20, then a+b20. Ilence, a+b=a+b-a+bl Second, if a, b20, then a+bs0. Hence a+b=-(a+b) b=a+ b Third. if a>o and b <0. then we have two further subcases: 1.Ifa+b≥0, then a+b=a-b≤|a+|b 2.Ifa+b≤0, then a+b ≤|a|+|b The fourth case, a<0 and b>0 is identical to the third case. with a and b interchanged 4. We first show a-bsa+b. We have a-b=a+(-b) ≤a|+|- b by property3 a|+b by property 1 To show al-b <la-b. we note that al=la-b+bl s la-b+bl, which implies la-b< la-b. On the other hand, from the above wc havc b-a<b-a=a-b by propcrty 1. Thcrcforc. a-blls a-b 5. We have four cases. First, if a, b>0, we have ab >0 and hence ab= ab=| allb. Second, if a, b<0 we have cb≥0 and hence abl=ab=(-am)(-b)=||b. Third,ifa≤0,b≤0, we have ab≤ 0 and hence b)=a b. The fourth case, a<0 and b> 0, is identical to the third case, with a and b interchanged 6. We have a+b≤|a+|b c+d 7.→: By property2,-a≤ al and a≤la. Therefore,|l< b implies-a≤|a|< b and a≤lal<b +:If a 20, then a=a<b If a <0, then a=-a< b For the case when“<” is replaced by“<”, we simply repeat the above proof with“<” replaced by“<” 8. This is simply the negation of property 7(apply DeMorgan's Law) 2.8 Observe that we can rcprcscnt(ac, 9 )2 as (m,y) y=(Qa)'(Qy) Qy 35 where Note that the matrix Q=Q is nonsingular 1. Now,(a, a )2=(Q)(Q)=Q22>0, and 0分|Qxl|2=0 分Qx-0 since Q is nonsingular 2.(a,y)2=(Qx)(Qy)=(Qy)(Qx)=(y,m)2 3. We have Kac +y, 22=(2+y Q Q22+y Q (x,z)2+(y,z) 4.ra, y)2=(rcQy-ra=r(a, y) 2.9 We have a=(a-y)+y <a-yl+ly by the Triangle Inequality. Hence lxe-lyll s a-y. On the other hand, from the above we have y-lc‖≤‖y-a‖=‖m-y/|. Combining the two inequalities, we obtain|ll-|y‖|≤‖x-y/‖ 2.10 Let e>0 be given Set 8=E. Hence, if a-y< 5, then by Exercise 2.9, la-ys a-y<8=E 3. Transformations 3.1 Let v be the vector such that a are the coordinates of v with respect to e1, e2, .. en], and a'are the coordinates of v with respect, to fe. el The U=me+……+nen=e1;…,enl, H Cna which implies enJa=fa 3.2 a. We have e1,e2,e3]=|e1,e2, 3-15 herefore 2 1414 2,e3]-e1,e2,e 5 2 453 11137 b. We have 123 1 1-10 Therefore, Wc havc 1,62 12 6 Therefore, the transformation matrix from el, e2,e3 to fel, e2, es) is 1 0I Now, COnsider a linear transformation L: RS-Rs, and let A be its representation with respect to Lel, e2, es, and B its representation with respect to el,e Let y= Ax and y= B r. Then, y'=Ty=T(Ax)=Ta(T x')=(TAr-)' Hence, the representation of the linear transformation with respect to el, e2, es) is B= TAT 184 2 13-7 3.4 We have 0111 0011 00 Therefore, the transformation matrix from el, e2, e3, e4 to lel, e2, e3, e4 is 1 111 1-100 0111 10 0011 001 000 Now, consider a lincar transformation L: R4+R, and lct a bc its reprcscntation with rcspcct to e1, e2, e3, e4), and B its representation with respect to el,e2, e3,e4. Let y= Ar and y=B Then y=Ty=T(A)=TA(T)=(tat)a Therefore 5343 32-12 B=AT 10 3 Let u1, 02, 03, 4 be a set of linearly independent eigenvectors of A corresponding to the eigenvalues A1 2,A3,and入4.LetT={U,v2,3,v小.Then, AT-AU1,2,3,v4]-[A1,Av2,AU3,Av4 入100 0A200 00入 000入 Hence 入100 AT=Ti0 A2 0 00入 or TAT=0入20 00入 Therefore, the linear transformation has a diagonal matrix form with respect to the basis formed by a linearly independent set of eigenvectors Because det(A)=(入-2)(入-3)(入-1)(入+1) the eigenvalues are A1=2, X2=3, A3=1, and A4=- From Avi=Aivi, where vi+0(i=1, 2, 3), the corresponding eigenvectors are 24 12 1 03=-9 and Therefore. the basis we are interested in is 24 01.09.0 9 3.6 Supposeυ1,…, Un are eigenvectors of A corresponding toλ1,…,λn, respectively.Then, for each i= h (In-A0;=t;-A=0;-U;=(1-A)Uz which shows that1-入 1- An are the eigenvalues of In-A Alternatively, we may write the characteristic polynomial of In-A 丌n-A(1-入)-det(1-A)In-(In-A))-det(-[入In-A])-(-1)”rA(入), which shows the desired result 3.7 Let m. yEv-, and a, BER. To show that v-is a subspace, we need to show that aa By Ev. For this let v be any vector in v. Then, v(ac- By=av 'a+Bvy=0, since v'a=v y=0 by definition 3.8 The null space of A is N(A)=aER: Ax=0]. Using elementary row operations and back-substitution we can solve the system of equations 4-20 4-20 4-20 02-1 0 0 2-31 000 2=23,1=22=423 2 2 3 3 erefore 2|c:c∈武 3.9 Lot a, y C R(A), and a, BC R. Thcn, therc exists v, u such that a= Av and y=Au. Thus, a+ By=aAu+ BAu=A(au+ Bu Hence, Ca+By E R(A), which shows that R(A) is a subspace Let , y EN(A), and a, B E R. Then, A=0 and Ay=0. Thus A(o.+ By)=cA m +BAy=0 Hence, aa+By EM(A), which shows that N(A)is a subspace 3.10 Let vFR(B),i.e, v= Br for some a. Consider the matrix [A v]. Then, N(A=N(A U), since if WEN(A), then u E N(B)by assumption, and hence u v=u Bx=aBu=0. Now, dim R(A)+dim N(A)=m dim r(la u+dim N(A a])=m Since dim(A)=dim(A U), then we have dim R(A)=dimR(LA v). Hence, v is a linear combi- nation of the columns of A,.c, vCR(A), which completes the proof 3.11 We first show V C(V).Let vE V, and u any element of V. Then u v=v u=0. Therefore, ∈(V We now show(V)Cv. Let a1,..., ak i be a basis for V, and (61, . bu) a basis for(V).Define A-al.ak] and B-[b1.bil, so that V-R(A)and(V)=R(). Ilence, it remains to show that R(B)C R(A). Using the result of Exercise 3.10, it suffices to show that N(A)CW(B). So let E N(A ), which implies that E R(A)=v, since R(A)=N(A). Hence, for all y, we have (By)=0=y B, which implies that B a=0. Thcrcforc, a CN(B ) which completes thc proof 3.12 Let wE w, and y be any element of v. Since vc w, then y E w. Therefore, by definition of w, we have 0. Therefore,w∈ Let r= dim v. Let v1,..., Ur be a basis for v, and v the matrix whose ith column is v;. Then, clearly =R(V) Let ul,. um-r be a basis for y, and U the matrix whose ith row is u. Then, v=R(U ),and V=(2)=R(U )=NU)(by Exercise 3.11 and Theorem 3.4) 3.14 a.Lt∈v.Then.x=P+(IP)x. Notc that pr∈,and(IP)a∈). Thcrcforc w= P:-(I- P) is all orthogonal decompositiOn of with respect to v. However, =i+0 is also all orthogonal decomposition of m with respect to v. Since the ort hogonal decomposition is unique, we must have Pa b. Suppose P is an orthogonal projector onto v. Clearly, r(P)c by definition. However, from part a, ac= Pa for all E v, and hence VC R(P). Therefore, R(P)=V 3.15 To answer the question, we have to represent the quadratic form with a symmetric matrix as 7/21 【实例截图】
【核心代码】