Let x ∈ R n and let P be a n × n positive definite symmetrix matrix. It is known that the maximum of maximize x T P x subject to x T x ≤ 1 is λ max ( P ), the largest eigenvalue of P. Now consider the following problem maximize x T P x subject to ( x − a ) T ( x − a ) ≤ 1 where a ∈ R n is known. What is the analytical solution?

Question

Let   x  ∈            R        n   and let   P be a   n  ×  n positive definite symmetrix matrix. It is known that the maximum of                    maximize                              x          T                P                x                            subject to                              x          T                x        ≤        1            is       λ          max        (  P  ), the largest eigenvalue of   P. Now consider the following problem                    maximize                              x          T                P                x                            subject to                    (        x        −        a                  )          T                (        x        −        a        )        ≤        1            where   a  ∈            R        n   is known. What is the analytical solution?

hospitaliapbury · Accepted Answer

This is (a variant of) the trust-region problem, and the solution can be computed rather easily, although not an analytical solutionI&#039;m reparameterizing your problem slightly, you can easily change your model to be   max      x    T    Q  x  +      c    T    x  +  b subject to       x    T    x  ≤  1. At optimality, you will be at the border of feasibility, and the constraint gradient will be pointing in the same direction as the objective gradient (draw this geometrically!), i.e., you have   2  Q  x  +  c  =  λ  2  x for some unknown   λ. Solve for   x to obtain   x  =  −  (  2  Q  −  λ  I      )          −      1        c. To find lambda, solve       x    T    x  =  1 which is an equation in   λ (possibly tricky, numerical methods required, line-search, bisection etc)

Let x ∈ <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="doub

Answered question

Answer & Explanation

New Questions in High school geometry