# Prove that a local min is also a global min

Let Q $\in \mathbb{R}^{d \times d}$ and A $\in$ $\mathbb{R}^{d' \times d}$ be two matrices. Let b $\in \mathbb{R}^d$ and c $\in \mathbb{R}^{d'}$ be two vectors. Suppose that d' < d.

I want to consider the quadratic programming problem for x $\in \mathbb{R}^d$:
minimize f(x):= $\frac{1}{2}x\cdot Qx -b\cdot x \ \$ subject to Ax = c

Prove that a local min is also a global min, by as follows:

Let $x_0$ be a local min of f(x). Argue by contradiction and suppose that there exists a point $x_1$ such that f($x_1$) < f($x_0$)

a) Consider the function $\phi$(s):= $\frac{1}{2}x(s)\cdot Qx(s) -b\cdot x(s) \ \$ where x(s):=(1-s)$x_0$ +s$x_1$. Prove that $\phi'$(0)=0 and $\phi''$(0) $\geq$ 0

b) Compute $\phi$'(0) and $\phi''$(0), and show that $\phi(s)$=$\phi(0)$ + s$\phi$'(0) + $\frac{s^2}{2} \phi''(0)$

c) Prove that $\phi(s) \geq f(x_0)$ for all s $\geq$ 0

How does this conclude that a local min is also a global min?

..................................................................................................

So for a) x(0)= $x_0$ which implies that $\phi(0)$ = f($x_0$). Since $x_0$ is a local minimum, f'(0) = 0 and f''(0) $\geq$ 0.

for c) the statement is just a result from b).

I just dont know how to find the derivatives of $\phi(s)$ for b). Need some help.

-

So we want to take derivative of the following quadratic form with respect to $s$: $$\phi(s) = \frac{1}{2} \big((1-s)x_0 + sx_1\big)^T Q \big((1-s)x_0 + sx_1\big) - b\cdot \big((1-s)x_0 + sx_1\big).$$ Back to $f(x)$, we know that: $$\frac{d}{dx} f(x) = \frac{d}{dx} (\frac{1}{2} x^T Qx - b\cdot x)= \frac{1}{2}(Q+Q^T)x + b,$$ hence by chain rule: \begin{aligned} \phi'(s) &= \left(\frac{1}{2}(Q+Q^T)x + b\right)\Bigg|_{x = (1-s)x_0 + sx_1} \cdot ((1-s)x_0 + sx_1)' \\ &= \frac{1}{2}(Q+Q^T)((1-s)x_0 + sx_1)\cdot (x_1 - x_0) + b\cdot (x_1 - x_0) \\ &=\frac{1}{2}(x_1 - x_0)^T(Q+Q^T)((1-s)x_0 + sx_1) + (x_1 - x_0)^T\, b . \end{aligned} Then we can see that if $Q = Q^T$, and $x_0$ solves $Q x_0 =b$, then $\phi'(0) = 0$.
Hint: Use the chain rule and the product rule and also that $x'(s) = x_1 - x_0$.