# Optimize the number of iteration to accomplish a task

0 down vote favorite I'm trying to solve something like this:

find the smallest n, s.t. $x_1 + f(x_1)\times x_2 + f(x_1,x_2)\times x_3 + ... + f(x_1,...,x_n-1)\times x_n > 100$, under the constraint that $|x_i| < 1$, for all $i = 1, 2, ..., n$.

The actual problem is about some iterative algorithm. I want to find the appropriate parameter s.t. the algorithm terminates in minimal iterations.

I want to know if there is a name for this kind of problem. Pointing to any fields, papers, theorems, or any thoughts would be helpful.

Ok, it's hard to come up with a concrete example because they are either too hard or too trivial, but here is one:

I want to travel from (0,0) to (100, 100). For each step I'm allowed to move along a vector of length determined by the function f. But each step size has to be <= 1.

Suppose I'm at step t. Then $f(x_1, x_2, ..., ) = (1-\eta x_1^2)(1-\eta x_2^2)...(1-\eta x_{t-1}^2)$ is the longest distance I can travel at step t, where $x_1,x_2,...,x_{t-1}$ are the distance I moved at step $1$ to $t-1$, and $\eta$ is some parameter, say here we set $\eta = 0.05$.

Question is how to design the move of each step (direction and length), s.t. the number of steps to reach $(100,100)$ is minimized.

Does that help clarify what I mean?

• I think you have no answers because you don't give any idea of what kind of $f$ you are working on, its domain and range (does it maps reals to integers, quaternions to reals ?). et. ... An example would be welcome... – Jean Marie Sep 24 '16 at 19:42
• I've update the question to include a more concrete example. – Xuezhou Zhang Sep 24 '16 at 20:30
• surely some interesting thing but this last clarification id not enough for me... is $f$ a free family function parameter ( not same number of arguments ) or there is some implicit iteration to compute it ? – user354674 Sep 24 '16 at 20:37
• You might as well travel along the diagonal, so you are really just asking to cover a distance of $100\sqrt 2$. The definition of $f$ is important. – Ross Millikan Sep 24 '16 at 20:40
• by implicit I mean something like that : $f(x_1,...,x_{n-1},x_n) = x_1 + f(x_1)\times x_2 + f(x_1,x_2)\times x_3 + ... + f(x_1,...,x_{n-1})\times x_n$ ( put braces around n-1 in the question ) – user354674 Sep 24 '16 at 20:47

You clearly should travel along the diagonal, so you are asking to cover a distance of $100 \sqrt 2$. I can do it in $4993$ steps, but I do not know if it is minimal. A little playing suggested I should start with a constant step until $f$ forced the step smaller, then take the maximum allowed step. I made an Excel spreadsheet to implement this, then used Goal Seek trying to set the distance to $141.421\approx 100 \sqrt 2$. I got there with a starting step of $0.031498243$ but could not get there at all with $4992$ steps.
• I started by looking how far you could get in small numbers of steps. That s often productive for getting a handle on large problems. In two steps you go $x_1+(1-x_1)^2$ because you always want the second step as large as possible. The derivative is zero at $x_1=\frac 12$. Then in three steps you go $x_1+x_2+(1-x_1^2)(1-x_2)^2$ and I ignored the cross term in the derivative and thought of taking steps of $\frac 12$,but realized I couldn't after the third step. Then I made the spreadsheet and asked it to get me to $141$ after $1000$ steps. It couldn't, but reduced the initial step. – Ross Millikan Sep 24 '16 at 23:26
• I lengthened the spreadsheet to 7000 steps and asked it to find an initial step that got to $141.421$ and it did. I kept trying for fewer and fewer steps and got the $4992$ result. Now we have a target for others to beat. – Ross Millikan Sep 24 '16 at 23:28