0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Jean Marie Sep 24 '16 at 19:42
  • $\begingroup$ I've update the question to include a more concrete example. $\endgroup$ – Xuezhou Zhang Sep 24 '16 at 20:30
  • $\begingroup$ 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 ? $\endgroup$ – user354674 Sep 24 '16 at 20:37
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 24 '16 at 20:40
  • $\begingroup$ 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 ) $\endgroup$ – user354674 Sep 24 '16 at 20:47
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I now see that the two dimensional setting is a bit useless. Clearly we should travel along the diagonal. And I realized that the f function is a bit wrong, as there should be a parameter determining how much the earlier steps affects the current step. But these doesn't matter much. What you suggest is interesting. So you want to do this in sort of a greedy way. Could you explain to me a bit how you come up with the "constant first, greedy afterwards" strategy? $\endgroup$ – Xuezhou Zhang Sep 24 '16 at 23:21
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 24 '16 at 23:26
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 24 '16 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.