# Linear Algebra Simplification Query

Apologies in advance; my linear algebra is not exactly up to scratch, but a program optimisation problem I've come across just feels like theres a better way mathematically rather than programatically.

In essence, its an optimisation problem; finding the highest values of a function for a three variable problem set; bitloading combination, k, and line.

The current way its done is, for each value k in a range, find the combination of bitloads (an array length N, value range 0-B) that gives the highest value L_k(bitloads,k).

L_k is at its core, a N*N matrix multiplication, but since N is generally significantly smaller than K, I feel like optimisation at that point isn't very useful if its still having to be done K*(B^N) times.

Given the audience and my poor explanation skills, this might make more sense.

For k=1...K

$b_{k,max}=\mathrm{argmax}(L_k(b,k))$

Such that

$L_k(b,k)=\sum_i^N(b_i*x_i)-\sum_i^N(P_i*y_i)$

Where x and y are run-time constant arrays and P is the result of a matrix solution (P for AP=X).

EDIT: I guess the structure of AP=X should really be stated; where g is a constant value, and M is a runtime constant 3D array:

$A_{ij} = 1\ \mathrm{if}\ i=j, \mathrm{otherwise} \frac{-g*(2^{b_i}-1)}{M_{i,j,k}}$

$X_{i} = \frac{-g*(2^{b_i}-1)}{M_{i,i,k}}$

I know this is a long shot but if anyone recognises a manipulation I'm missing to make life easier, I'd be very interested to be educated!

-
There seems to be something missing: your definition of $L_k(b,k)$ doesn't depend on $k$. Perhaps it is $p$ which depends on $k$, in which case its definition does need to be filled in here. –  Rahul Narain Mar 22 '11 at 7:46
You should be a bit more careful with uppercase and lowercase letters. I take it that $l_k$ and $L_k$ denote the same function and that "$B$" in "$AP=B$" refers to the argument $b$ of $L_k$ and not to the limit $B$ of the value range. Then $L_k$ is a linear of function of $b$, and there's no need to try out all values of $b$. You only need to evaluate the gradient of $L_k$ with respect to $b$, which is $g=x-A^{-1\mathrm{T}}y$, and choose $b_i\in\{0,B\}$ according to the sign of $g_i$. Also the "nonlinear-optimization" tag seems to be misplaced? –  joriki Mar 22 '11 at 9:05
joriki: An update not from 6am will be more useful. Thank you for your method about the gradient, I think that still applies in the expanded case, but b is going to have to be evaluated anyway in the AP=X solution. –  Andrew Bolster Mar 22 '11 at 13:27
Five things: a) pinging only works if you precede the name with a '@'; I only came across your response to me by chance. b) if you want the entire $b_i$ in the exponent (I assume you do?), you need to enclose it in braces. (I fixed that.) c) to set words like "if" or "otherwise" as words (as opposed to strings of italicized variables), you can use "\mathrm{}" or "\text{}". d) There are still uppercase and lowercase 'p's -- I presume these refer to the same quantity? e) I reinstated the "nonlinear-optimization" tag, since your update clarified that the problem is in fact nonlinear. –  joriki Mar 22 '11 at 13:35