5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – Gilead
    Commented Feb 19, 2011 at 4:16
  • $\begingroup$ 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. $\endgroup$
    – Tony
    Commented Feb 19, 2011 at 5:51
  • $\begingroup$ @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. $\endgroup$
    – drbobmeister
    Commented Feb 19, 2011 at 8:14
  • $\begingroup$ It is a subvector. My bad word usage. I added a p.s. to clarify. Thanks for your suggestion, drbobmeister. $\endgroup$
    – Tony
    Commented Feb 19, 2011 at 8:30
  • $\begingroup$ OK, so it looks like I was right. Thanks for clarifying, Tony. $\endgroup$
    – drbobmeister
    Commented Feb 19, 2011 at 8:40

1 Answer 1

Reset to default
3
$\begingroup$

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/

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Tony
    Commented Feb 19, 2011 at 5:48
  • $\begingroup$ @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. $\endgroup$
    – Gilead
    Commented Feb 19, 2011 at 22:42
  • $\begingroup$ @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. $\endgroup$
    – Brian Borchers
    Commented Feb 20, 2011 at 2:48
  • $\begingroup$ @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. $\endgroup$
    – Gilead
    Commented Feb 20, 2011 at 4:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .