Non-convex function: Rastrigin

Convex optimization (凸最佳化)是最佳化理論中一個重要的分支， convex optimization 有一個很好的特性， 亦即如果 local minimum 存在的話則它必定是 global minimum。 一般的最佳化問題不一定可以被寫成凸最佳的問題， 所以會遇到存在很多 local minimum 的問題。 以下的 Rastrigin function 是一個例子

上面看起來像波浪狀海綿的圖形，越紅的部分數值越大，越藍的部分數值越小， 看得出來這個函式有很多 local minimum (也有很多 local maximum)， 而最小的 local minimum 即 global minimum 落在原點。這個函式被故意設計成有很多個 local minimum，讓演算法一不小心就會落到 local minimum，所以這個函式很適合拿來當作最佳化演算法的 benchmark，演算法如果沒有仔細設計就會找不到 global minimum。

Rastrigin funtion 的定義如下

其中 x_i 是變數，n 是變數的個數。 以下是我寫的 matlab 程式碼(matlab 的 global optimization toolbox 也提供了一個 gui demo)，有興趣的人可以玩玩

grids = linspace(-5.12, 5.12, 1000);
[X, Y] = meshgrid(grids, grids);
A = 10.0;
Z = 2*A+ X.^2 + Y.^2 - A * (cos(2*pi*X) + cos(2*pi*Y));
mesh(Z);
zlim([0 80]); axis tight
set(gca,'XTickLabel',{'-5.12'; '-2.56'; '0'; '2.56'; '5.12'})
set(gca,'YTickLabel',{'-5.12'; '-2.56'; '0'; '2.56'; '5.12'})