Consider the vectors $\mathbf{a} \in \mathbb{R}^N$ and $\mathbf{b} \in \mathbb{R}^N$ with $N>1$ and $\mathbf{a} \neq \mathbf{b}$. The product $\mathbf{C}=\mathbf{a} \mathbf{b}^T \in \mathbb{R}^{N \times N}$ will yield a square, non-symmetric matrix $\mathbf{C}$ with rank=1.

How do I formulate an optimization problem on $\mathbf{a}$, given a specific $\mathbf{b}$, such that $\mathbf{C} = \mathbf{a} \mathbf{b}^T$ is negative definite? How do I specify this constraint?

$$ \min_{\mathbf{a}} \text{a user-specified objective} \\ \text{subject to} \ldots ?$$

I know, a square, nonsymmetric matrix $\mathbf{D}$ is negative definite if and only if its symmetric part $(\mathbf{D} + \mathbf{D}^T)/2$ is negative definite. However, in my case, the symmetric part $(\mathbf{C} + \mathbf{C}^T)/2$ will have a maximum rank of 2, and it may have zero eigenvalues... See also this wiki-link.

  • 1
    $\begingroup$ As you noted, if $N > 2$ then your matrix $C$ is never negative definite (e.g., if $\mathbf{v}$ is orthogonal to $\mathbf{a}$ and $\mathbf{b}$ then $\mathbf{v}^TC\mathbf{v} = 0$). Is it not enough for your $C$ to be negative semidefinite? If semidefiniteness is OK, then this type of problem can be solved via semidefinite programming solvers (SeDuMi etc, or frameworks like CVX for MATLAB). $\endgroup$ Feb 3 at 15:31
  • $\begingroup$ ok, thanks, I thought so. But what do I need to do for $N=2$? $\endgroup$
    – Beram
    Feb 4 at 21:30
  • 1
    $\begingroup$ For $N = 2$, you can basically type the problem as-is into CVX in MATLAB. Just tell it what your objective function is and then specify the constraint $\mathbf{a}\mathbf{b}^T + \mathbf{b}\mathbf{a}^T \leq 0$, where $\leq 0$ here means negative semidefinite. $\endgroup$ Feb 5 at 0:36
  • $\begingroup$ thanks, didn't know about CVX yet! Seems powerful $\endgroup$
    – Beram
    Feb 5 at 9:44

Your Answer

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

Browse other questions tagged or ask your own question.