- #1
kingwinner
- 1,270
- 0
Homework Statement
Homework Equations
Constrined optimzation
The Attempt at a Solution
("o" means dot product)
Let M={x|Ax=c} and f(x)=(1/2)x o Qx - b o x
Suppose x0 is a local min point.
Suppose, on the contrary, that x0 is NOT a global min point. Then there must exist a point x1 s.t. f(x1)<f(X0).
Let x(s) = (1-s)x0 + s x1, s is any real number.
x(0)=x0, x(1)=x1
Let φ(s)=f(x(s)), s is any real number. Then φ has a local min at s=0.
=> φ'(0)=0 and φ''(0)≥0 (1st and 2nd order necessary conditions for a local min)
By chain rule, 0 = φ'(0) = x1 o Qx0 - x0 o Qx0 - b o (x1-x0)
and 0 ≤ φ''(0) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0
and I'm stuck here...how can I arrive at a contradiction from here? I tried adding them to get φ'(0)+φ''(0)≥0, but it doesn't seem to help.
Any help would be much appreciated!