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

Add comment

Post as Anonymous Dont send out notification