Quadratic Functions, Optimization, and Quadratic Forms

1 Quadratic Functions, Optimization, and Quadratic Fo r m s Robert M. Freund February, 2004 1 2004 Massachusetts Institute of 1 Quadratic Optimization A Quadratic optimization problem is an optimization problem of the form: T(QP) : minimize f (x):= 1 xT Qx + c x . Problems of the form QP are natural models that arise in a variety of settings. For example, consider the problem of approximately solving an over-determined linear system Ax = b, where A has more rows than columns. We might want to solve: (P1) : minimize Ax b x . Now notice that Ax b 2 = xT AT Ax 2bT Ax+bT b, and so this problem is equivalent to: (P1) : minimize xT AT Ax 2bT Ax + bT b x , which is in the format of QP. A symmetric matrix is a square matrix Q n n with the property that Qij = Qji for all i, j =1.

2 ,n . 3 We can alternatively define a matrix Q to be symmetric if QT = Q. We denote the identity matrix ( , a matrix with all 1 s on the diagonal and 0 s everywhere else) by I, that is, 10 .. 0 01 .. 0 I = .. , 00 .. 1 and note that I is a symmetric matrix. The gradient vector of a smooth function f(x): n is the vector of first partial derivatives of f(x): f(x) x1 . f(x):= .. f(x) xn The Hessian matrix of a smooth function f(x): n is the ma-trix of second partial derivatives. Suppose that f(x): n is twice differentiable, and let 2f(x)[H(x)]ij := xi xj . Then the matrix H(x) is a symmetric matrix, reflecting the fact that 2f(x) = 2f(x) . xi xj xj xi A very general optimization problem is: 4 (GP) : minimize f (x) x , where f (x): n is a function.

3 We often design algorithms for GP by building a local Quadratic model of f ( )atagivenpoint x = form the gradient f ( x) (the vector of partial derivatives) and the Hessian H( x) (the matrix of second partial derivatives), and approximate GP by the following problem which uses the Taylor expansion of f (x)at x = x up to the Quadratic term. (P2) : minimize f (x):= f ( x)T (x 2(x x)(x x)+ f ( x)+ 1 x)T H( x) x . This problem is also in the format of QP. Notice in the general model QP that we can always presume that Q is a symmetric matrix, because: 1T x Qx = x T (Q + QT )x2 and so we could replace Q by the symmetric matrix Q := 1 2(Q + QT ). Now suppose that f (x):= 1 x T Qx + c T x 2 where Q is symmetric. Then it is easy to see that: f (x)= Qx + c and H (x)= Q.

4 5 Before we try to solve QP, we first review some very basic properties of symmetric matrices. 2 Convexity, Definiteness of a Symmetric Matrix, and Optimality Conditions A function f (x): n is a convex function if nf ( x+(1 )y) f (x)+(1 )f (y) for all x, y , for all [0, 1]. A function f (x) as above is called a strictly convex function if the inequality above is strict for all x = y and (0, 1). A function f (x): n is a concave function if nf ( x+(1 )y) f (x)+(1 )f (y) for all x, y , for all [0, 1]. A function f (x) as above is called a strictly concave function if the inequality above is strict for all x = y and (0, 1). Here are some more definitions: Q is symmetric and positive semidefinite (abbreviated SPSD and de-noted by Q 0) if T x Qx 0 for all x n.

5 Q is symmetric and positive definite (abbreviated SPD and denoted by Q 0) if T x Qx > 0 for all x n ,x =0 . Theorem 1 The function f (x):= xT Qx + cT x is a convex function if and only if Q is SPSD. 1 26 Proof: First, suppose that Q is not SPSD. Then there exists r such that r T Qr < 0. Let x = r. Then f (x)= f ( r)=1 2 2rT Qr + cT r is strictly concave on the subset {x | x = r},since rT Qr < 0. Thus f ( ) is not a convex function. Next, suppose that Q is SPSD. For all [0, 1], and for all x, y, f ( x +(1 )y)= f (y + (x y)) 1 21 (y + (x y))T Q(y + (x y)) + cT (y + (x y))= = 1 2T Qy + (x y)T Qy + T 2(x y)T Q(x y)+ cT x +(1 )cyy211 2T Qy + (x y)T Qy + T (x y)T Q(x y)+ cT x +(1 )c yy211 2 xT Qx + T(1 )yT Qy + cT x +(1 )c= y2= f (x)+(1 )f (y) , thus showing that f (x) is a convex function.

6 Corollary 2 f (x) is strictly convex if and only if Q 0. f (x) is concave if and only if Q 0. f (x) is strictly concave if and only if Q 0. f (x) is neither convex nor concave if and only if Q is indefinite. Theorem 3 Suppose that Q is SPSD. The function f (x):= 1 2x TT Qx + cx attains its minimum at x if andonlyif x solves the equation system: f (x)= Qx + c =0 . 7 Proof:Suppose thatx satisfiesQx +c= 0. Then for anyx,wehave:f(x)=f(x +(x x ))=12(x +(x x ))TQ(x +(x x )) +cT(x +(x x ))=12(x )TQx +(x x )TQx +12(x x )TQ(x x )+cTx +cT(x x )=12(x )TQx +(x x )T(Qx +c)+12(x x )TQ(x x )+cTx =12(x )TQx +cTx +12(x x )TQ(x x )=f(x )+12(x x )TQ(x x ) f(x ),thus showing thatx is a minimizer off(x).Next, suppose thatx is a minimizer off(x), but thatd:=Qx +c = :f(x + d)=12(x + d)TQ(x + d)+cT(x + d)=12(x )TQx + dTQx +12 2dTQd+cTx + cTd=f(x )+ dT(Qx +c)+12 2dTQd=f(x )+ dTd+12 2dTQd.

7 But notice that for <0 and sufficiently small, that the last expressionwill be strictly less thanf(x ), and sof(x + d)<f(x ). This contradictsthe supposition thatx is a minimizer off(x), and so it must be true thatd=Qx +c= are some examples of convex Quadratic Forms : f(x)=xTx8 f(x)=(x a)T(x a) f(x)=(x a)TD(x a), whereD= is a diagonal matrix withdj>0,j=1,..,n. f(x)=(x a)TMTDM(x a), whereMis a non-singular matrix andDis as Characteristics of Symmetric MatricesA matrixMis anorthonormal matrixifMT=M 1. Note that ifMisorthonormal andy=Mx, then y 2=yTy=xTMTMx=xTM 1Mx=xTx= x 2,and so y = x .Anumber is aneigenvalueofMif there exists a vector x =0such thatM x= x. xis called aneigenvectorofM(and is called aneigenvector corresponding to ). Note that is an eigenvalue ofMif andonly if (M I) x=0, x = 0 or, equivalently, if and only if det(M I)= ( )=det(M I).

8 Theng( ) is a polynomial of degreen,andsowill havenroots that will solve the equationg( ) = det(M I)=0,including multiplicities. These roots are the eigenvalues 4 IfQis a real symmetric matrix, all of its eigenvalues arereal :Ifs=a+biis a complex number, let s=a bi. Thens t= s t,sis real if and only ifs= s,ands s=a2+ is an eigenvalue ofQ,for somex = 0, we have the following chains of equations:Qx= xQx= x Q x= xxTQ x=xT Q x=xT( x)= xT xas well as the following chains of equations:Qx= x xTQx= xT( x)= xTxxTQ x=xTQT x= xTQx= xTx= xT xT x= xT x, and sincex = 0 impliesxT x =0, = ,andso 5 IfQis a real symmetric matrix, its eigenvectors correspond-ing to different eigenvalues are :SupposeQx1= 1x1andQx2= 2x2, 1 = 1xT1x2=( 1x1)Tx2=(Qx1)Tx2=xT1Qx2=xT1( 2x2)= 1 = 2, the above equality implies thatxT1x2= 6 IfQis a symmetric matrix, thenQhasn(distinct) eigen-vectors that form an orthonormal basis for.

9 If all of the eigenvalues ofQare distinct, then we are done, as theprevious proposition provides the proof. If not, we construct eigenvectors10iteratively, as follows. Letu1be a normalized ( , re-scaled so that its normis 1) eigenvector ofQwith corresponding eigenvalue 1. Suppose we havekmutually orthogonal normalized eigenvectorsu1,..,uk, with correspondingeigenvalues 1,.., k. We will now show how to construct a new eigenvectoruk+1with eigenvalue k+1, such thatuk+1is orthogonal to each of the vectorsu1,.., [u1,..,uk] n k. ThenQU=[ 1u1,.., kuk].LetV=[vk+1,..,vn] n (n k)be a matrix composed of anyn kmutually orthogonal vectors such that thenvectorsu1,..,uk,vk+1,..,vnconstitute an orthonormal basis for n. Then note thatUTV=0andVTQU=VT[ 1u1,.., kuk]= an eigenvector ofVTQV (n k) (n k)forsomeeigenvalue , so thatVTQV w= w,anduk+1=Vw(assumewis normalized so thatuk+1has norm 1).

10 We now claim the following two statements are true:(a)UTuk+1= 0, so thatuk+1is orthogonal to all of the columns ofU,and(b)uk+1is an eigenvector ofQ,and is the corresponding eigenvalue that if(a)and(b)are true, we can keep adding orthogonal vectorsuntilk=n, completing the proof of the prove(a), simply note thatUTuk+1=UTVw=0w=0. Toprove(b),letd=Quk+1 uk+1. We need to show thatd= 0. Note thatd=QV w V w,andsoVTd=VTQV w VTVw=VTQV w w= ,d=Urfor somer k,andsor=UTUr=UTd=UTQV w UTVw=0 0= ,d= 0, which completes the 7 IfQis SPSD, the eigenvalues ofQare :If is an eigenvalue ofQ,Qx= xfor somex = 0. Then 0 xTQx=xT( x)= xTx, whereby 8 IfQis symmetric, thenQ=RDRT, whereRis an or-thonormal matrix, the columns ofRare an orthonormal basis of eigenvec-tors ofQ,andDis a diagonal matrix of the corresponding eigenvalues :LetR=[u1.]