Return to Answer

1. If $x_1=0,1,4,5$, then $u_0=-5, -4, -1, 0$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2\ge x_0^2+(u_0^2+x_1^2)\ge 5^2 + 17$$
2. If $x_1=3, x_1=2$, then $u_0=-2, -3$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2= 5^2 + 4 + 9 + (u_1^2+x_2^2 + u_2^2 + x_3^2+u_3^2)\\=5^2 + 13 + (u_1^2+x_2^2 + u_2^2 + x_3^2)\ge 5^2 + 13 + 3=5^2+16,$$ where the last inequality holds as among the numbers $u_1, x_2, u_2$, either all of them are $1$ or $-1$, or one of them is bigger than $1$ or smaller than $-1$, i.e., a number whose square is no less than $2^2=4$. $\checkmark$

Tracing the proof above, we can see that the optimal control sequence is $u_0^*=-3$, $u_1^*=-1$, $u_2^*=-1$, $u_3^*=0$.

min_cost = 999999999999999999  # a number too big
x0 = 5
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
print(min_cost)  # 41

# or an expanded one-liner.
import from itertools import product

min_cost = min(
    sum(x[k] ** 2 + (x[k + 1] - x[k]) ** 2
        for k in range(4))
    for x in product([5], range(6), range(6), range(6), range(6)))
print(min_cost)  # 41 again

1. If $x_1=0,1,4,5$, then $u_0=-5, -4, -1, 0$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2\ge x_0^2+(u_0^2+x_1^2)\ge 5^2 + 17$$
2. If $x_1=3, x_1=2$, then $u_0=-2, -3$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2= 5^2 + 4 + 9 + (u_1^2+x_2^2 + u_2^2 + x_3^2+u_3^2)\\=5^2 + 13 + (u_1^2+x_2^2 + u_2^2 + x_3^2)\ge 5^2 + 13 + 3=5^2+16.$$

Why does the last inequality hold? We know $x_1\ge2$. Among the numbers $u_1, x_2, u_2, x_3$, there are at least 3 numbers that are either $1$ or $-1$, or one of them is bigger than $1$ or smaller than $-1$, i.e., a number whose square is no less than $2^2=4$. $\checkmark$

Tracing the proof above, we can see that the optimal control sequences are

• $u_0^*=-3$, $u_1^*=-1$, $u_2^*=-1$, $u_3^*=0$ (as shown above).
• $u_0^*=-3$, $u_1^*=-1$, $u_2^*=0$, $u_3^*=0$.

min_cost = 999999999999999999  # a number too big
x0 = 5
control_sequence = []
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
                    control_sequence = [[x1 - x0, x2 - x1, x3 - x2, x4 - x3]]
                elif min_cost == cost3:
                    control_sequence.append([x1 - x0, x2 - x1, x3 - x2, x4 - x3]) 

print(min_cost)   
# 41

print("Optimal Control sequences: ", control_sequence)  
# [[-3, -1, -1, 0], [-3, -1, 0, 0]]

To find the optimal control sequence, keep track of the choices of the variables made for each $f(s,t,x)$ in the loop.

min_cost = 999999999999999999  # a number too big
x0 = 5
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
print(min_cost)  # 41

# or an expanded one-liner.
min_cost = min(
    sum(x[k] ** 2 + (x[k + 1] - x[k]) ** 2
        for k in range(4))
    for x in product([5], range(6), range(6), range(6), range(6)))
print(min_cost)  # 41 again

How can we compute the function of minimum cost below? $$f(s, t, x_0)=\min_{0\le x_{k+1}=x_k+u_k\le s\text{ for all }k}\sum_{k=0}^t x_k^2 + u_k^2$$ where all variables are integers. $s\ge0$ and $t\ge0$.

The above recurrent relation enables us to use a nested loop to compute $f$, assume all $x_i\le s$ for some fixed limit $s$.

1. For $t=0$, $f(s, t, x)=x^2$ for all $x$
2. Suppose for some $t$, we have computed $f(s, t-1, x)$ for all $x$. Use the above recurrence relation to computed $f(s, t, x)$ for all $x$.

min_cost = 999999999999999999  # a number too big
x0 = 5
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
print(min_cost)  # 41

# or an expanded one-liner.
import from itertools import product

min_cost = min(
    sum(x[k] ** 2 + (x[k + 1] - x[k]) ** 2
        for k in range(4))
    for x in product([5], range(6), range(6), range(6), range(6)))
print(min_cost)  # 41 again

How can we compute the function of minimum cost below? $$f(s, t, x_0)=\min_{0\le x_{k+1}=x_k+u_k\le s\text{ for all }k}\sum_{k=0}^t x_k^2 + u_k^2$$ where all variables are integers, $0\le x_0\le s$, $0\le t$.

The above recurrent relation enables us to use a nested loop to compute $f$.

1. For $t=0$, $f(s, t, x)=x^2$ for all $x$, $0\le x\le s$.
2. Suppose for some $t$, we have computed $f(s, t-1, x)$ for all $x$, $0\le x\le s$. Use the above recurrence relation to computed $f(s, t, x)$ for all $x$, $0\le x\le s$.

Tracing the proof above, we can see that the optimal control sequence is $u_0^*=-3$, $u_1^*=-1$, $u_2^*=-1$, $u_3^*=0$.

Problem Restated

Simple Arithmetic

Tracing the proof above, we can see that the optimal control sequence is $u_0^*=-3$, $u_1^*=-1$, $u_2^*=-1$, $u_3^*=0$.

Brute-Force Programming

As Yuval observed, it is a short programming exercise to brute-force the $6^4=1296$ possible feasible solutions. For example, here it is in Python.

min_cost = 999999999999999999  # a number too big
x0 = 5
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
print(min_cost)  # 41

# or an expanded one-liner.
min_cost = min(
    sum(x[k] ** 2 + (x[k + 1] - x[k]) ** 2
        for k in range(4))
    for x in product([5], range(6), range(6), range(6), range(6)))
print(min_cost)  # 41 again

Dynamic Programming

To use dynamic programming, we need to find many overlapping problems, with optimal structure that will lead to recurrent relations. Here we have the natural general problems in the form of the following.

How can we compute the function of minimum cost below? $$f(s, t, x_0)=\min_{0\le x_{k+1}=x_k+u_k\le s\text{ for all }k}\sum_{k=0}^t x_k^2 + u_k^2$$ where all variables are integers. $s\ge0$ and $t\ge0$.

The original problem is the case when $s$ = 5, $x_0=5$ and $t=3$.

$$f(s, t, x_0) =\min_{0\le x_1\le s}\ \left((x_0^2 + (x_1-x_0)^2) + f(s, t-1, x_1)\right)$$

The above recurrent relation enables us to use a nested loop to compute $f$, assume all $x_i\le s$ for some fixed limit $s$.

1. For $t=0$, $f(s, t, x)=x^2$ for all $x$
2. Suppose for some $t$, we have computed $f(s, t-1, x)$ for all $x$. Use the above recurrence relation to computed $f(s, t, x)$ for all $x$.