Re: quadratic minimization: analytical solutions

From: Peter Spellucci (spellucci_at_fb04373.mathematik.tu-darmstadt.de)
Date: 12/31/04 

Date: Fri, 31 Dec 2004 13:20:03 +0000 (UTC)

In article <1104478990.210548.7520@z14g2000cwz.googlegroups.com>,
 y_granik@yahoo.com writes:
>Consider quadratic non-convex optimization
>problems with simple bounds:
>
>f(x) = xQx+bx -> min
>0 <= x <= 1
>
>When x has only one component, we get
>
>f(x) = a*x*x+b*x -> min
>0 <= x <= 1
>
>This is pretty simple problem
>and can be solved analytically.
>If a > 0, then problem is convex and we just have to
>compare 2 or 3 values
>
>f(0), f(1), and f(-b/2a), if 0 < = -b/2a <= 1
>
>and identify the smallest one.
>If a < 0, then the problem is convcave
>and we have to compare
>
>f(0) and f(1)
>
>to find min.
>
>The question: does this problem
>have analytical solutions in dimensions
>high than 1? In particular,
>for 2 dimensions, when x = (x1, x2),
>can we solve this analytically?
>
>
>This feels like a fundamental
>problem of quadratic programing,
>but I cannot find it in the books I
>have.
>
>Please help.
>
>Happy New Year!
>
>Yuri Granik
>

no. nonconvex quadratic optimization is np hard.
even in case n=2 you could have any situation concerning the minimizer.
make a little sketch e.g. with Q=[-1 0 ; 0 -1 ] and any b, with the maximum now
at -b/2. depending on the position of -b/2 realtive to the unit box
you could have several local (nonglobal ) minimizer, with b=[-1,-1] four
global minimizer exactly at the four vertices etc etc
hth
peter