Search
Complicated functions generally have more local minima. Even if the gradient method converges, it will find only one of these minima. But this minimum can be local and can be far from the global minimum. For this reason, the gradient method is often started from different starting points and then the best point to which the method has converged is selected. In this task, we will consider the function $f:\mathbb R^n\to\mathbb R$, an admissible set of the form of the multidimensional interval (box) $[x_{\rm min},x_{\rm max}]\subset \mathbb R ^n$ and the optimization problem \begin{align} \text{minimize}\qquad &f(x) \\ \text{under conditions}\qquad &x\in[x_{\rm min}, x_{\rm max}]. \end{align} Recall that $x\in[x_{\rm min}, x_{\rm max}]$ is satisfied if it holds for all components. As one of the test functions we will consider the Griewank function $$ f_{\rm griewank}(x) = 1 + \frac{1}{4000}\sum_{i=1}^n x_i^2 - \prod_{i=1}^n \cos \frac{x_i}{ \sqrt i}. $$
Implement a generate_solutions function that finds all local minima of a function on a given interval. The generate_solutions function must have the following input arguments (in the order listed):
generate_solutions
f
g
x_min
x_max
The generate_solutions function somehow generates a larger number of admissible points in the admissible set and then runs the gradient method with projection for each of them. Use the (slightly modified) code from the lecture.
function optim(f, g, P, x; α=0.01, max_iter=10000) for _ in 1:max_iter y = x - α*g(x) x = P(y) end return x end P(x, x_min, x_max) = min.(max.(x, x_min), x_max)
optim
The generate_solutions function must also meet the following properties:
f(0)
generate_solutions(f,g,-1,1)
f([0])
generate_solutions(f,g,[-1],[1])
Next, implement the function f_griewank described above and its derivative g_griewank. Remember that this function depends on the length $n$ of its argument. If $n=1$, this function must be called by both f_griewank(0) and f_griewank([0]), as well as its derivative.
f_griewank
g_griewank
f_griewank(0)
f_griewank([0])