Orthogonal vector variables

1

As part of a larger optimization, I would like to enforce an orthogonality constraint on two vector variables. The two vectors correspond to the rows of X, such that G = XX’ and G is diagonal. If the equality is held, the rows are orthogonal. What I’ve done so far is to formulate the constraint as an SDP. This seems to work “most of the time” - but not always! In particular, in the code below, orthogonality is only enforced when “sum_a_lower_bound” is less than about 16.5, AND with the choice of objective: minimize trace(G). My questions are:

  1. Under what conditions would the equality of G=X*X’ be effectively enforced to thereby enforce orthogonality?
  2. Why is “minimize trace(G)” needed? Any way to drop this?
  3. Is there a simpler way to enforce orthogonality of two vector variables in a convex framework (preferably a constraint that is independent of the objective). There is another approach that I can think of which basically amounts to: ||a+v|| <= t, AND ||a-v|| <= t, then minimize t. Which works, but becomes problematic when there are other quantities to be minimized simultaneously in the objective.

Here’s my working code snippet. Thanks in advance!

n=2;
sum_a_lower_bound = 16.5; % seems to work only when <= 16.5 in this example.
cvx_begin sdp 
    variable G(n, n) diagonal;  % gram matrix
    variable X(n, 3);    
    expressions  v(1,3)  a(1,3);
    v = X(1,:);
    a = X(2,:);
    minimize trace(G)   % minimize nuclear norm to encourage low-rank  
    subject to
        [G, X; X', eye(3)] >= 0;  % using Schur complement  to relax G = X*X' with G >= X*X'
        v == [8,-2,3];  % place-holder for more complex constraints on v 
        sum_a_lower_bound <= sum(a);    % place-holder for more complex constraints on a         
cvx_end
2

In order for the semidefinite constraint to be tight, i.e., the desired equality to be satisfied, a rank one solution is needed.

Encouraging a low rank solution might (or might not) help achieve that. But If the “encouragement” is at the expense of your true objective, what have you accomplished, even if you get a rank one solution?

3

Thanks so much for the response. In the example, G is 2x2 and X is 2x3. G and XX’ should both be rank 2 in order for the rows of X to be linearly independent, let alone orthogonal. With G diagonal and diag(G) non-zero, G is rank 2 by design. So, I’m still fuzzy as to the critical conditions under which the equality is guaranteed. To be honest, although I used “minimize trace(G)”, and this does seem to achieve the desired solution most of the time, I’m not really sure why it’s helping! I’m aware that the nuclear norm is the convex envelope of rank - just don’t see how that relates here. Any help on discovering conditions when G=X*X’ would be super useful. Thanks!

4

It sounds like what you want is a rank 2 solution. If G is higher rank than 2, it can’t be of the form X*X’, with X 2 by 2; therefore, equality can’t hold. Minimizing trace drives toward low rank solution, so maybe that’s why the semidefinite relaxation works out as often as it does.

But perhaps your procedure could sometimes produce a rank one solution, which then would not have independent rows of X?

I will defer to others for any additional assessment.