Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got to solve an optimisation problem and don't know how to approach this (I'm thinking of writing a script to solve the problem recursively but wonder if there's another approach).

The target is given by $n$ real numbers, e. g. $a_{1t} = 10$, $a_{2t} = 20$, $a_{3t}=30$.

I've got the current value of the $n$ numbers, e. g. $a_{11}=1$, $a_{21}=1$, $a_{31}=5$.

I can change these numbers as follows:

$a_{12} = a_{11} + \eta · \mu_1 $

$a_{22} = a_{21} + \eta · \mu_2 $

$a_{32} = a_{31} + \eta · \mu_3 $

I need to find $\eta$ so that the mean square root between the two sequences is minimal when changing the $n$ numbers according to this rules where $\mu_1$, $\mu_2$ and $\mu_3$ are fixed factors (e. g. $1$, $2$ and $3$).

share|improve this question
    
If $\mu_1, \mu_2, \mu_3$ do not depend on $t$, your problem is way more simple ; iterating will only "change the value of $\eta$ in the first iteration". Do you see what I mean? For instance, $$a_{13} = a_{12} + \eta_2 (\mu_1) = (a_{11} + \eta_1(\mu_1)) + \eta_2 (\mu_1) = a_{11} + (\eta_1 + \eta_2) \mu_1,$$ so that anything you could do in $t$ iterations you can do in one. –  Patrick Da Silva Apr 6 '12 at 18:40
    
Yes, $\mu_1, \mu_2, \mu_3$ do not depend on $t$. –  meinzlein Apr 6 '12 at 18:43
    
Your problem only has two steps then, the beginning step and the least square solution. Adding multiple steps in between is meaningless, unless you're trying to use a numerical algorithm to converge to the solution, but in this case analytical solutions exist. Would that be what you would be looking for? –  Patrick Da Silva Apr 6 '12 at 18:46
    
I guess it is. My problem is I don't exactly know how to "understand" this problem. I also thought about taking it as a vector problem - a n-dimensional target vector is given and another vector is given which should be altered to be closer to the target vector, but only certain components following certain rules (depending on the $\mu$s) can be altered. –  meinzlein Apr 6 '12 at 19:28
    
If what you're saying means your problem is a one-step problem, then you know that there is a solution to the minimal distance between a line and a point in $\mathbb R^n$, do you? –  Patrick Da Silva Apr 6 '12 at 21:05

1 Answer 1

You are given a vector $a \in \mathbb R^n$, a direction $v \in \mathbb R_n \backslash \{ 0 \}$, and a point $p \in \mathbb R^n$. Write $$ (p-a) = \left( \frac{(p-a) \cdot v}{v \cdot v} \right) v + \left( (p-a) - \left( \frac{(p-a) \cdot v}{v \cdot v} \right) v \right). $$ The two vectors in the sum are orthogonal, the factor $\eta$ you are looking for is $\left( \frac{(p-a) \cdot v }{v \cdot v} \right)$ and the norm of the vector on the right of the sum is the minimal distance you can acheive.

All of this is elementary linear algebra : I projected the vector $p-a$ along the line passing through $a$ in the direction of $v \neq 0$, and the scaling factor of the length of $v$ versus the length of the projection is the factor $\eta$. If you compute $p-a$ minus the projection vector you get the vector that starts at the minimal point on the line and goes to the point, so computing its norm gives you the minimal distance.

Hope that helps,

share|improve this answer

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.