### 2018 Q24

Hello, I don't understand why the function is convex. The distance is a minimum of a L2 norm, but the solution states that it is a maximum of convex functions. While I know that norms are convex, I don't see how their minimum, hence -max, can be convex.

I also don't know how to find the Lipschitz constant here, so any help would be appreciated. I tried to find a bound for the gradient, but didn't get far. Is there an easier way?

Top comment

The convexity of distance $$d(C, y)$$ can be proved using the definition, that is $$d(C, ty_1 + (1-t) y_2)\le t d(C, y_1) + (1-t) d(C, y_2)$$. Suppose $$w_1, w_2 \in C$$ such that $$d(C, y_1) = || w_1 - y_1 ||_2$$ and $$d(C, y_2) = || w_2 - y_2 ||_2$$, then $$d(C, ty_1 + (1-t) y_2) \le || tw_1+(1-t)w_2 - (ty_1+(1-t)y_2) ||_2 \le t || w_1 - y_1 ||_2 + (1-t) || w_2 - y_2 ||_2$$ where $$tw_1+(1-t)w_2\in C$$. Thus we have show $$d(C, y)$$ is convex. Then since $$g(x)$$ is the maximum of a set of convex functions, by hint it is also convex.

The Lipschitz constant L can be computed by the definition $$|d(C, y_1) - d(C, y_2)| \le L||y_1-y_2||_2$$. First without loss of generality we can assume $$d(C, y_1) \ge d(C, y_2)$$, then $$|d(C, y_1) - d(C, y_2)| = d(C, y_1) - d(C, y_2)= || w_1 - y_1 ||_2 - || w_2 - y_2 ||_2 \le || w_2 - y_1 ||_2 - || w_2 - y_2 ||_2$$. Then apply inequality $$|| w_2 - y_1 ||_2 - || w_2 - y_2 ||_2 \le || y_1 - y_2 ||_2$$ leads to L=1.

Thank you, that makes it clearer.

But how come we can ignore the min operator in the distance?

@Anonymous said:
Thank you, that makes it clearer.

But how come we can ignore the min operator in the distance?

The property of min operator is used in $$d(C, ty_1 + (1-t) y_2) \le || tw_1+(1-t)w_2 - (ty_1+(1-t)y_2) ||_2$$ where the right hand side $$tw_1+(1-t)w_2\in C$$ is no better than the minimizer of $$d(C, ty_1 + (1-t) y_2)$$.

Page 1 of 1