Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all,

I recently encounter a difficult problem.

I wish to minimize in $ \mathbf{x} $ the sum $\min \sum_{i=1..n} (\mathbf{x}^T \mathbf{A}_i \mathbf{x})^2$ given the constraints on the norms of all $\mathbf{x}$'s subcomponents (let's say three 3-by-1 vectors) $|\mathbf{x}_1| = 1, |\mathbf{x}_2| = 1, |\mathbf{x}_3| = 1$. $\mathbf{A}_i$ may not be positive-definite.

Yes, it's quartic expression that we want to minimize. I'm not sure if any one has worked on this or similar problem in the math community. I search the literature for sometimes but no use. My question may be similar but actually much more difficult than this Least square given constraint on subcomponents

The 4th-order and constraints on all subcomponents makes it really hard for me to handle.

Any idea to a numerical/analytical solution, is greatly appreciated. Thanks for reading.

p/s: $\mathbf{x} = [\mathbf{x}_1^T , \mathbf{x}_2^T, \mathbf{x}_3^T]^T$. By "subcomponents", I mean the subvectors, as shown in the equation.

share|improve this question
    
May I ask what the motivation is for making the quadratic expression a quartic one? Is it to avoid concave curvature? (at the expense of introducing multiple solutions) –  Gilead Feb 19 '11 at 4:16
    
I want the quadratic expressions as close to 0 as possible, and since A is not positive-definite, I have to minimize the sum of squares. I'm not sure if it's a good idea. –  Tony Feb 19 '11 at 5:51
    
@Tony: I'm having a little trouble understanding your question. Are the "subcomponents" orthogonal projections of $x$ onto a set of three (for example) mutually orthogonal, complementary subspaces whose sum is $R^{k}$, the space in which $x$ lives? That's my guess, but if you could clarify it might help folks to answer your question. –  drbobmeister Feb 19 '11 at 8:14
    
It is a subvector. My bad word usage. I added a p.s. to clarify. Thanks for your suggestion, drbobmeister. –  Tony Feb 19 '11 at 8:30
    
OK, so it looks like I was right. Thanks for clarifying, Tony. –  drbobmeister Feb 19 '11 at 8:40
add comment

1 Answer

As a practical matter, a lot depends on $n$ and the dimension of $x$. If the problem is small enough then you might not be in deep trouble. If the problem is large (e.g. $x$ might have thousands of components), then it could be very hard.

If the problem is quite small, then you might consider using an approach that exploits the polynomial structure of your optimization problem. There are convex relaxations of such polynomial optimization problems that provide very tight lower bounds and software can often use these lower bounds to find a globally optimal solution. See for example the Gloptipoly2 software:

http://homepages.laas.fr/henrion/software/gloptipoly2/

share|improve this answer
    
Thanks for your reply. x is a small vector, about 9 to 15, divided into 3-5 subcomponents. And n is small too, about 9 to 20. I think it is feasible. I hope there's a closed-form solution. But I'll look into your suggested software. –  Tony Feb 19 '11 at 5:48
    
@Tony, there is a closed form solution if you write out the KKT conditions. There are no inequality constraints, so you don't have to worry about the complementarity conditions. That said, your equality constraints are either non-smooth or nonlinear (depending on how you formulate them), so your problem is definitely nonconvex. You will need to use global optimization software if you desire the global minimum; local methods will not be able to guarantee true optimality. –  Gilead Feb 19 '11 at 22:42
    
@Gilead, if you write out the KKT conditions, you'll get a polynomial system of equations which also can't be solved by local numerical methods. I'd hardly call a system of polynomial equations a "closed form" solution to the problem. You could apply Groebner basis methods to that system of equations, but in my opinion you'd be better off using the polynomial optimization approach of Gloptipoly or one of its competitors to solve the minimization problem. –  Brian Borchers Feb 20 '11 at 2:48
    
@Brian, you're right, a high-order multivariate system of polynomials doesn't always have necessarily closed form solution, and if you understand "closed-form" in an engineering sense (i.e. "analytical solution"), then it definitely isn't that, even if it is decomposed into its Groebner basis. As for the second part of your assertion, my comment is in fact agreeing with yours in that I believe global optimization software is necessary at some level for solving this problem because it is inherently nonconvex owing to the equality constraints. –  Gilead Feb 20 '11 at 4:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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