6
$\begingroup$

DISCLAIMER: I've edited the question repeatedly for clarity and to target the most relevant answer.

I have the following general problem $$ \min \|h_1\cdot h_2\|^2 $$ such that $$\|g_1\wedge g_2-h_1\wedge h_2\|^2 = 0,$$ where $h_i,g_i\in \mathbb{R}^n\wedge \mathbb{R}^n$ are skew-symmetric matrices, $A\cdot B$ denotes matrix multiplication of matrices $A$ and $B$, and $\lambda\in \mathbb{R}$. $A\wedge B$ is the geometric product of $A$ and $B$.

In order to make the problem solve nicer, i.e., no infeasibility trap at $h_1=0$, for instance, I've reformulated the problem with the following constraints. $$\|g_1\wedge g_2-\lambda h_1\wedge h_2\|^2 = 0,\\ \lambda\ge 0,\\ \|h_1\|^2=1,\\ \|h_2\|^2=1$$

My test case is $n=6$ and $g_1=g_2=e_{12}+e_{34}+e_{56}$ (a worst case scenario). Obviously, the problem is degenerate due to symmetry as well as unitarily invariant on $\mathbb{R}^6$. I've introduced $\lambda$ and constraints 2 and 3 in order to exclude some slack in the solution. My expected outcome is $h_1 =\frac{1}{\sqrt{12}}\left(2e_{12}+e_{34}+e_{56}\right)$ and $h_2=\frac{1}{\sqrt{2}}\left(e_{34}+e_{56}\right)$ with a minimum of 1/12 and $\lambda=\sqrt{24}$.

I've used IPOPT to implement the minimzation, but it fails to find this solution. Instead a solution is found that is slightly worse. I'm a little perplexed as all functions are convex in each variable, but I'm no expert in NLP.

EDIT: As per @Geoff Oxberry, the problem is not convex. As a matter of fact, the initial guess of $h_1=g_1$ and $h_2=g_2$ is a maximum of the objective function under the constraints.

So how do I improve my initial guess or change constraints to improve solutions?

$\endgroup$
  • $\begingroup$ I don't quite understand your notation. Specifically, I'm confused about what the wedge ($\wedge$) means, because it's not a logical "and" in this case. Almost everything else sort of makes sense. Also, the degeneracy of the problem isn't apparent to me (probably because of the notation issues). Could you explain the degeneracy in more detail? $\endgroup$ – Geoff Oxberry Mar 1 '12 at 18:13
  • $\begingroup$ $\wedge$ is the geometric product. $\endgroup$ – Deathbreath Mar 1 '12 at 18:25
  • $\begingroup$ Geometric product? $\endgroup$ – Geoff Oxberry Mar 1 '12 at 18:27
  • $\begingroup$ Let $V\wedge V = V\otimes V/\{v\otimes v|v\in V\}$. See here for annother take on it. $\endgroup$ – Deathbreath Mar 1 '12 at 18:34
  • $\begingroup$ I've amended the title to reduce the emphasis on convexity. The involved functions are convex in each single variable, but maybe not overall. $\endgroup$ – Deathbreath Mar 1 '12 at 19:06
2
$\begingroup$

Your problem is not convex.

First, $\|h_{1}\|^{2} = 1$ and $\|h_{2}\|^{2} = 1$ are not convex constraints, even though the functions on the left-hand sides are convex. The easiest way to picture this in a simpler case is to note that the unit circle (or sphere) is not a convex set because the line between any two points on the circle (or sphere) is not contained in the set.

Second, the function $\|h_{1} \cdot h_{2}\|^{2}$ is probably not convex because it contains bilinear terms. Bilinear terms are known not to be convex, and I doubt that composing them with a 2-norm changes the non-convexity.

Since IPOPT is a local optimization solver only guaranteed to find the global solution under convexity assumptions, it probably converged to the local minimum nearest your guess (though without knowing more about your guess and the problem iterations, I can't really say for sure).

$\endgroup$
  • $\begingroup$ I've thought about it, and have come to the conclusion that indeed the problem is not generally convex, but really the weirdness is that $(h_1,h_2)=(g_1,g_1)$ is actually a maximum. IPOPT fails in the restoration phase at a nearly feasible point. $\endgroup$ – Deathbreath Mar 1 '12 at 20:43
  • $\begingroup$ Yeah, that's the pain in the ass about nonconvex optimization problems -- they screw everything up. $\endgroup$ – Geoff Oxberry Mar 1 '12 at 23:07
  • $\begingroup$ I'm considering changing the constraints. 3 and 4 turn into $\le 1$ and I'll bound $\lambda$ as soon as I know a good upper bound. I'm thinking about adding $\mbox{tr } h_1 -\mbox{tr } h_2 \le 0$ and $\mbox{tr } (h_1\cdot h_2) \le 0$. $\endgroup$ – Deathbreath Mar 2 '12 at 1:09
  • $\begingroup$ The trace of $h_{1} \cdot h_{2}$ is almost certainly a nonconvex constraint. However, the difference of the two traces is linear and should be fine. $\endgroup$ – Geoff Oxberry Mar 3 '12 at 5:23
  • $\begingroup$ I've actually dropped both those constraints as they did nothing to improve the solution, but the bounds on $\lambda$ and 3/4 are good. I'm looking into ways to characterize the degeneracies and adding perturbations to lift them. $\endgroup$ – Deathbreath Mar 3 '12 at 13:16

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.