Quadratic Functions, Optimization, and Quadratic Forms

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

is a diagonal matrix with d j > 0, j =1,...,n. • f(x)=(x−a)TMTDM(x−a), where M is a non-singular matrix and D is as above. 3 Characteristics of Symmetric Matrices A matrix M is an orthonormal matrix if MT = M−1. Note that if M is orthonormal and y = Mx, then y 2 = yTy = xTMTMx= xTM−1Mx= xTx = x 2, and so y = x. Anumberγ ∈ is an ...

Loading..

Tags:

  Quadratic, Diagonal, A diagonal

Information

Related search queries