1
$\begingroup$

I was reading this paper where the define an optimization problem as

enter image description here

where K and L are kernel matrices and $\pi$ is the permutation matrix. They have explained that the function is convex because

enter image description here

I didn't get how they said convex non-decreasing square function. Where is the square function. The square is because of the Frobenius norm isn't it? and how come the function is non decreasing. Any clarification will be much appreciated.

$\endgroup$
3
$\begingroup$

A remark: $\pi$ is no longer a permutation matrix here; the constraints on $\pi$ were relaxed to make the set of admissible $\pi$ convex.

The objective function is of the form $\|A\|_F^2$, where $A$ is a matrix that linearly depends on $\pi$. Here $A\mapsto \|A\|$ is a convex function, which is a part of norm properties. This convex function is then composed with the function $x\mapsto x^2$ which is increasing and convex on $[0,\infty)$. We only consider this function on $[0,\infty)$ because the norm is nonnegative. Thus, $A\mapsto \|A\|_F^2$ is the composition of a convex function with a convex increasing function, which makes it convex as well.

$\endgroup$
  • $\begingroup$ What can be said about the convexity of forbenius norm ? $\endgroup$ – mcjoshi Feb 18 '18 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.