# Separation and Support Theorems for Convex Sets

1. Nov 8, 2009

### hsong9

1. The problem statement, all variables and given/known data
Let C be a closed convex subset of Rn. If y is not in C, show x* in C is the closest vector to y in C if and only if (x-y)(x*-y) >= ||x* - y||2 for all x in C.

2. Relevant equations
Theorem. Suppose that C is a convex set in Rn and that y is a vextor in Rn that is not in C. Then x* in C is the closest vecotr in C to y (that is, ||y-x*|| <= ||y-x|| for all x in C) if and only if (y-x*)(x-x*)<= 0 for all x in C.

3. The attempt at a solution
(<=) Let f(x) = ||x-y||2 = (x-y)(x-y)
f'(x) = 2(x-y)
f''(x) = 2 ==> f(x) is convex function.
f(x) > f(x*) + f'(x*)(x-y) = f(x*) + 2(x*-y)(x-y) >= f(x*) since (x-y)(x*-y) >= 0.
Thus x* is the closest vector to y in C.
I am not sure the inequality 'f(x) > f(x*) + f'(x*)(x-y)' is fine. Is it right?

(=>) by Thm, ||y-x*|| <= ||y-x|| for all x in C
||y-x*||2 = (y-x*)(y-x*) <= (y-x)(y-x*)
Complete.
This seems fine, but I am not sure.