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.

2 A symmetric matrix is a square matrix Q n n with the property that Qij = Qji for all i, j =1,..,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.

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

4 (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. 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].

5 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 . Q is symmetric and positive definite (abbreviated SPD and denoted by Q 0) if T x Qx > 0 for all x n ,x =0.

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

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

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

9 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). 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.

10 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 :If all of the eigenvalues ofQare distinct, then we are done, as theprevious proposition provides the proof.