# Ski Race

A skier begins at position and must ski through gates to position , where skiing downhill is in the direction of increasing position. The gates are parallel and run perpendicular to the direction. For each for there is a gate centered at with a width of .

Efficiently find the shortest path through all gates.

## Example

Consider the starting position and ending position and gates

Then the course looks like

## Solution

Let be the position of the skier at . Then for the skier to go through the gate at , our constraint on must be .

The length of the shortest path taken between adjacent gates and is . Then we can formulate our optimization problem as

For simplicity, we can define , , and to write

This isn’t efficiently solvable yet, however, because the objective isn’t convex in . But we can make the problem convex with the following reduction:

Let be , with ,
so , , and so on.
Rearranging, this means .
Then we can neatly relate and by ,
See `np.tril`

where is a lower triangular matrix with ones for entries.
Then our optimization problem becomes

Now the objective is the sum of the norms of , which is convex in . Also, the constraints are all affine, so this is a convex optimization problem.

We can apply our solution to the above values:

```
import numpy as np
from cvxpy import Variable, Minimize, Problem, norm, hstack
x = np.array([0, 4, 8, 12, 16, 20, 24])
y = np.array([4, 5, 4, 6, 5, 7, 4])
c = np.array([0, 3, 2, 2, 1, 2, 0])
L = np.tril(np.ones((7, 7)))
dy = Variable(7)
objective = sum(
norm(hstack((x[i] - x[i-1], dy[i])))
for i in range(1, 7)
)
constraints = [
L * dy >= y - c / 2,
L * dy <= y + c / 2,
]
problem = Problem(Minimize(objective), constraints)
problem.solve()
p = L @ dy.value
path = np.column_stack((x, p))
path_length = problem.value
print(f"Path length: {path_length}")
print("Path:")
print(path)
```

```
Path length: 24.573423483752443
Path:
[[ 0. 4. ]
[ 4. 4.37494654]
[ 8. 4.749936 ]
[12. 5.12493412]
[16. 5.49999986]
[20. 6. ]
[24. 4. ]]
```

which we can visualize