2

Given two orthogonal matrices ${\bf{M}} \in {{\Bbb{R}}^{m \times n}}$ and ${\bf{N}} \in {{\Bbb{R}}^{m \times n}}$, there is an orthogonal transformation matrix ${\bf{T}} \in {{\Bbb{R}}^{n \times n}}$ which closely maps ${\bf{M}}$ and ${\bf{N}}$:

$$\begin{array}{ll} \text{minimize} & {\left\| {{\bf{M}} - {\bf{NT}}} \right\|_F}\\ \text{subject to} & {{\bf{T}}^T}{\bf{T}} = {\bf{I}}\end{array}$$

Is this a convex optimization problem?

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
ar_k
  • 51
  • 6

1 Answers1

6

It is not convex because the feasible set (the set of matrices $T$ satisfying $T^TT = I$) is not a convex set.

For instance, $I$ and $-I$ are both orthogonal matrices, but their non-trivial convex combinations (that is, every $T = (1 - \theta) I + \theta(-I)$ with $\theta \in (0,1)$) fail to be orthogonal.

Ben Grossmann
  • 216,163
  • 12
  • 149
  • 305
  • Thank you for the answer. I am aware that there is a method to solve this problem for a unique answer through SVD. Does it mean that this method gives only a local minimum? – ar_k Dec 13 '19 at 10:19
  • 2
    @ar_k Actually, the SVD method gives a global minimum. Also the SVD method is not iterative (i.e. not a descent method), so there is no need to worry about getting "trapped" at a particular minimum. It is well known that a unique solution exists if and only if the matrix $BA^T$ is invertible. – Ben Grossmann Dec 13 '19 at 10:43
  • Thanks! It is clear and useful. – ar_k Dec 13 '19 at 10:46
  • 1
    @Omnomnomnom Thank you for your response. shouldn't we say the constraint $X^tX=I$ is not a `convex function` instead of being a `convex set`? More accurately, shouldn't we say it is not an affine function due to the fact that in convex problems the equality should just be an affine function. – Green Falcon Apr 10 '20 at 18:55
  • @Media the constraint is an equation, not a function, so I have no idea what you're talking about. – Ben Grossmann Apr 10 '20 at 20:50
  • @Omnomnomnom YES :) my mistake about function. Please consider the latter part of my question. Shouldn't we say, it should be affine set? – Green Falcon Apr 10 '20 at 20:56
  • @Media I don't understand your question – Ben Grossmann Apr 10 '20 at 21:06
  • You've referred *It is not convex because the feasible set (the set of matrices T satisfying $T^TT=I$) is not a convex set*. I guess the last part should be **affine set** and not *convex set*. Because equality constraints should be affine. – Green Falcon Apr 10 '20 at 21:07
  • 2
    @Media I don't know what you mean by an affine set; perhaps you mean an [affine subspace](https://en.wikipedia.org/wiki/Affine_space). In any case, the feasible set for a convex optimization problem is a convex set and conversely any convex set can be the feasible set to a convex optimization problem, so my statement is correct. – Ben Grossmann Apr 10 '20 at 21:11