POJ 2420 A Star not a Tree? - Area1のif(memo[i][j])

問題

二次元座標上に点がN個与えられる。この座標上から一点を指定し、N個の点との距離の総和を最小化せよ。

やりかた

解析的に答えが求まりそうにないので、数理最適化。自分は最急降下法でやった。
選んだ座標を $(X, Y)$ とし、与えられたN個の点の座標を $(a_i, b_i)$ すると距離の総和は $L = \sum \sqrt{(X - a_i)^2 + (Y - b_i)^2}$ となる。

なのでこの関数の勾配方向は
$\left( \frac{\partial L}{\partial X}, \frac{\partial L}{\partial Y} \right) = \left( \sum \frac{X-a_i}{\sqrt{(X - a_i)^2 + (Y - b_i)^2}}, \sum \frac{Y-b_i}{\sqrt{(X - a_i)^2 + (Y - b_i)^2}} \right)$ となるので、ここから更新式 $X \leftarrow X - \alpha * {\partial L}/{\partial X}, \quad Y \leftarrow Y - \alpha * {\partial L}/{\partial Y}$ に従って予め決めた回数だけX, Yを更新する。

関数が凸関数でないような気がしたため、局所最小値に入ってしまうかもしれないと思ったが、初期値を重心にすれば大丈夫だろとたかをくくって出した。

以下ソース。

int x[100], y[100];

int main(){
  int N; cin >> N;

  double sumX = 0, sumY = 0;
  for(int i = 0; i < N; i++){
    cin >> x[i] >> y[i];
    sumX += x[i], sumY += y[i];
  }
  
  double X = sumX / N;
  double Y = sumY / N;

  for(int i = 0; i < 100000; i++){
    double alpha = 1e-2;

    double dx = 0, dy = 0;
    for(int j = 0; j < N; j++){
      dx += (X - x[j]) / sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
      dy += (Y - y[j]) / sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
    }
    
    X = X - alpha * dx;
    Y = Y - alpha * dy;
  }

  double L = 0;
  for(int j = 0; j < N; j++)
    L += sqrt(pow(X - x[j], 2.0) + pow(Y - y[j], 2.0));
  printf("%d\n", (int)(L + 0.5));
  return 0;
}

最初、学習率が小さすぎて最小値までたどりつかずWA。提出する前は収束するかきちんと確かめた上で、制限時間内で収束するような学習率にするべきだとわかった。（あたりまえだが）