Minimal value to be determined

[senmeis]

Homework Statement

A and X: 6x1 vectors

A = [-0.39; -3.99; 1.01; 0.57; -0.70; -2.81]B: 6x6 symmetrical matrix

B = [1.1 -0.2 0.19 -1.03 0.69 -0.47

-0.2 0.17 -0.25 0.43 -0.06 -0.05

0.19 -0.25 0.88 -0.62 -0.21 0.29

-1.03 0.43 -0.62 1.59 -0.3 0.04

0.69 -0.06 -0.21 -0.3 0.97 -0.62

-0.47 -0.05 -0.29 0.04 -0.62 0.59]An integer X shall be determined so that f = (A - X)^t•B•(A - X) is minimal.

Homework Equations

The Attempt at a Solution

I think the critical condition is X must be integer so the conventional method grad(f) = 0 cannot be applied.

 

[Ray Vickson]

Homework Statement

A and X: 6x1 vectors

A = [-0.39; -3.99; 1.01; 0.57; -0.70; -2.81]B: 6x6 symmetrical matrix

B = [1.1 -0.2 0.19 -1.03 0.69 -0.47

-0.2 0.17 -0.25 0.43 -0.06 -0.05

0.19 -0.25 0.88 -0.62 -0.21 0.29

-1.03 0.43 -0.62 1.59 -0.3 0.04

0.69 -0.06 -0.21 -0.3 0.97 -0.62

-0.47 -0.05 -0.29 0.04 -0.62 0.59]An integer X shall be determined so that f = (A - X)^t•B•(A - X) is minimal.

Homework Equations

The Attempt at a Solution

I think the critical condition is X must be integer so the conventional method grad(f) = 0 cannot be applied.

Do you allow negative integers, or must all the elements of X be $\geq 0$ (or $> 0$)?

Anyway, the problem appears to be unbounded: we can find a sequence of integer $X > 0$ that have $(A-X)^T B (A-X)$ going to $-\infty$.

However, that may be due to a typo in your matrix: if you change your $b_{6,3}$ to $+0.29$ everything is OK. The matrix you wrote is not symmetric.

 

[senmeis]

Sorry, b6,3 is really +0.29.There are no limitations on elements in X, negative or positive.I think f cannot be negetive in any case. Maybe this statement can be proved with the characteristics that B is symmetric.Senmeis

 

[Ray Vickson]

Sorry, b6,3 is really +0.29.There are no limitations on elements in X, negative or positive.I think f cannot be negetive in any case. Maybe this statement can be proved with the characteristics that B is symmetric.Senmeis

With the corrected value $b_{6,3} =0.29$ the matrix $B$ is "positive-definite", which means that $f(w) = w^T B w > 0$ for any nonzero vector $w$. So, of course, the minimum of $f(a-x)$ is 0, obtained at $x = a = [-0.39; -3.99; 1.01; 0.57; -0.70; -2.81]$. I suspect (but cannot prove) that the best integer values of $x$ will be near those of $a$, so (probably) $x_1 = 0$ (or maybe $x_1 = -1$), $x_2 = -4$, $x_3 = 1$, $x_4 = 1$ (or maybe $x_4 = 0$), $x_5 = -1$ and $x_6 = -3$.

A type of "branch-and-bound" method could be used to get a provable integer solution, but it would be tedious and would require solutions of bound-constrained problems like $\min_{\{x_1 \leq -1, x_4 \geq 1\}} f(a-x)$ and $\min_{\{x_1 \geq 0, x_4 \leq 0\}} f(a-x)$, etc.

For more on positive-definiteness, see
https://en.wikipedia.org/wiki/Positive-definite_matrix.

 

[StoneTemplePython]

A couple thoughts:

1.) What course is this for? There are integer domain quadratic programming libraries out there that could be used (e.g. Gurobi but needs a license) though this is something of an exotic topic.

2.) I was a bit confused by this statement:

so the conventional method grad(f) = 0 cannot be applied.

In general, for optimizing quadratic forms (unless there are special constraints like memory usage or you have linear / constant terms to deal with), you wouldn't typically first look at the gradient... the eigenvalue argument (assuming we're in Reals and matrix is / has been 'symmetrized' ) is the standard argument that one looks to, and allows one to make claims about positive definiteness as @Ray Vickson mentioned. This is intimately tied in with the multi variable second derivative test (i.e. evaluating the Hessian Matrix of a scalar valued function) so it's worth spending some time thinking on it.

 

[Ray Vickson]

A couple thoughts:

1.) What course is this for? There are integer domain quadratic programming libraries out there that could be used (e.g. Gurobi but needs a license) though this is something of an exotic topic.

2.) I was a bit confused by this statement:
In general, for optimizing quadratic forms (unless there are special constraints like memory usage or you have linear / constant terms to deal with), you wouldn't typically first look at the gradient... the eigenvalue argument (assuming we're in Reals and matrix is / has been 'symmetrized' ) is the standard argument that one looks to, and allows one to make claims about positive definiteness as @Ray Vickson mentioned. This is intimately tied in with the multi variable second derivative test (i.e. evaluating the Hessian Matrix of a scalar valued function) so it's worth spending some time thinking on it.

Although most of the web pages devoted to "positive-definiteness" emphasize eigenvalue tests, etc., by far the easiest and efficient way to test a matrix is to compute its Cholesky decomposition. For an $n \times n$ matrix you get in $O(n^2)$ simple arithmetical steps the Cholesky factor, or else prove it does not exist, so that the matrix is indefinite (assuming you have looked at the diagonal elements and found them to all be > 0---so the matrix is not negative-definite!). I once wrote a routine for a programmable HP calculator that could test matrices up to about $10 \times 10$.

 

[StoneTemplePython]

Although most of the web pages devoted to "positive-definiteness" emphasize eigenvalue tests, etc., by far the easiest and efficient way to test a matrix is to compute its Cholesky decomposition. For an $n \times n$ matrix you get in $O(n^2)$ simple arithmetical steps the Cholesky factor, or else prove it does not exist, so that the matrix is indefinite (assuming you have looked at the diagonal elements and found them to all be > 0---so the matrix is not negative-definite!). I once wrote a routine for a programmable HP calculator that could test matrices up to about $10 \times 10$.

This is true and something that I forget about from time to time. I seem to recall it also has the benefit that, symbolically, it (or $LDL^T$ ) can be done using exact arithmetic over rationals which in many cases means stronger / more exact claims than using numerical eigenvalue estimates.

I thought Cholesky was $O(n^3)$, though, just with a very low coefficient? I suppose you're suggesting that there's an option of early stopping that is tucked in the weeds of the algorithm...

 

[Ray Vickson]

This is true and something that I forget about from time to time. I seem to recall it also has the benefit that, symbolically, it (or $LDL^T$ ) can be done using exact arithmetic over rationals which in many cases means stronger / more exact claims than using numerical eigenvalue estimates.

I thought Cholesky was $O(n^3)$, though, just with a very low coefficient? I suppose you're suggesting that there's an option of early stopping that is tucked in the weeds of the algorithm...

You're right: it is $O(n^3)$.

 

[senmeis]

With the corrected value $b_{6,3} =0.29$ the matrix $B$ is "positive-definite", which means that $f(w) = w^T B w > 0$ for any nonzero vector $w$. So, of course, the minimum of $f(a-x)$ is 0, obtained at $x = a = [-0.39; -3.99; 1.01; 0.57; -0.70; -2.81]$. I suspect (but cannot prove) that the best integer values of $x$ will be near those of $a$, so (probably) $x_1 = 0$ (or maybe $x_1 = -1$), $x_2 = -4$, $x_3 = 1$, $x_4 = 1$ (or maybe $x_4 = 0$), $x_5 = -1$ and $x_6 = -3$.

A type of "branch-and-bound" method could be used to get a provable integer solution, but it would be tedious and would require solutions of bound-constrained problems like $\min_{\{x_1 \leq -1, x_4 \geq 1\}} f(a-x)$ and $\min_{\{x_1 \geq 0, x_4 \leq 0\}} f(a-x)$, etc.

For more on positive-definiteness, see
https://en.wikipedia.org/wiki/Positive-definite_matrix.

I’ve guessed the answer the same way as you did, butX1 = [0, -4, 1, 1, -1, -3]

X2 = [0, -5, 1, 1, -1, -3]f(X2) < f(X1)so it’s not so straightforward as it looks.Senmeis

 

[Ray Vickson]

I’ve guessed the answer the same way as you did, butX1 = [0, -4, 1, 1, -1, -3]

X2 = [0, -5, 1, 1, -1, -3]f(X2) < f(X1)so it’s not so straightforward as it looks.Senmeis

No, indeed: combinatorial optimization problems are often far from straightforward, and some of them can be downright nasty (NP-hard).