Separation and Support Theorems for Convex Sets

[hsong9]

Homework Statement

Let C be a closed convex subset of Rⁿ. 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||² for all x in C.

Homework Equations

Theorem. Suppose that C is a convex set in Rⁿ and that y is a vextor in Rⁿ 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.

The Attempt at a Solution

(<=) Let f(x) = ||x-y||² = (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*||² = (y-x*)(y-x*) <= (y-x)(y-x*)
Complete.
This seems fine, but I am not sure.

 

[mighty2000]

Could you please give some comments or suggestions?

Your solution looks correct to me. Here are some additional explanations and tips that may help you understand the problem better:

1. First, let's define the distance between two points x and y in Rn as ||x-y||2, which is the Euclidean distance or the length of the vector connecting x and y.

2. The problem statement is asking us to show that x* is the closest point to y in C if and only if (x-y)(x*-y) >= ||x* - y||2 for all x in C. This means that x* is the closest point to y if and only if the dot product of the vectors (x-y) and (x*-y) is greater than or equal to the squared distance between x* and y.

3. The theorem given in the problem is a useful tool to prove the statement. It states that the closest point to y in C is the one that minimizes the function f(x) = ||x-y||2. This means that the point x* is the closest point to y if and only if f(x*) <= f(x) for all x in C.

4. Now, let's use the definition of f(x) and the given theorem to prove the statement. First, we can rewrite the inequality in the problem statement as (x-y)(x*-y) >= (x*-y)(x*-y). This is equivalent to (x-y)(x*-y) >= ||x* - y||2.

5. Next, we can use the given theorem to rewrite f(x*) <= f(x) as (x-y)(x*-y) <= 0. This means that for x* to be the closest point to y, (x-y)(x*-y) must be less than or equal to 0 for all x in C.

6. Finally, we can combine the two inequalities to show that (x-y)(x*-y) >= ||x* - y||2 if and only if (x-y)(x*-y) <= 0 for all x in C. This completes the proof.

7. Some tips for solving convex optimization problems like this one: always start by understanding the problem and defining the relevant variables and concepts. Then, use the given information and theorems to rewrite the problem in a more manageable form. Finally, use algebraic manipulations and logical reasoning to arrive at