-- 点Qの座標のリスト
qs = drop 1 [(x,y)|x<- [0..50], y<- [0..50]]

-- 点Q(x,y) /= (0,0) とが直角となるような点Pで範囲内のもの
ps (x,y) = takeWhile p [(x-k*dx, y+k*dy)| k<- [1..]]
           ++ 
           takeWhile p [(x+k*dx, y-k*dy)| k<- [1..]]
    where dx = y `quot` (gcd x y)
          dy = x `quot` (gcd x y)

-- 点(a,b)が範囲内にあるか?
p (a,b) = 0 <= a && a <= 50 && 0 <= b && b <= 50

-- 原点Oが直角になる場合とそうでない場合に分けて和をとる
p091 =  (+) (50*50)  $ sum $ map (length.ps) qs 

main = print p091

次のコードはHaskellWikiのもの。直角となる点が軸上にある場合とそうでない場合に分けて数え上げている。数え上げればいい問題だからいちいち座標を計算する必要はないことがわかる。
http://www.haskell.org/haskellwiki/Euler_problems/91_to_100

reduce x y = (quot x d, quot y d)
  where d = gcd x y
 
problem_91 n = 
    3*n*n + 2* sum others
    where
    others =[min xc yc|
        x1 <- [1..n],
        y1 <- [1..n],
        let (yi,xi) = reduce x1 y1,
        let yc = quot (n-y1) yi,
        let xc = quot x1 xi
        ]

2012-03-09

最適化の数学 1.4

メモ最適化

1.4 不等式制約問題の最適性条件

不等式制約問題

min: $f(x)$
s.t.:　 $g_{i}(x) \leq 0 (i=1,...,l)$
　　　 $g_{i}(x) = 0 (i=l+1,...,m)$
　　　 $x \in \mathbb{R}^{n}$

実行可能解xに対し不等式条件で等号が成り立つとき、この制約条件はxにおいて有効であるという。
有効制約条件の添え字集合を次のように記す。

$A(x) = \{i|g_{i}(x)=0 (i=1,...l)\}$

実行可能解xに対し有効である不等式制約条件の勾配ベクトルと等式制約条件の勾配ベクトルが互いに1次独立であるとき、xは正則であるという。

不等式制約問題の最適性必要条件（KKT条件）

2012-03-08

最適化の数学 1.3

メモ最適化

1.3 等式制約問題の最適性条件

等式制約問題

min: $f(x)$
s.t.:　 $g_{i}(x) = 0 (i=1,...,m)$
　　　 $x \in \mathbb{R}^{n}$

ラグランジュ関数

$L(x,u) = f(x) + u^{T}g(g)$

この $u$ はラグランジュ乗数ベクトルと呼ばれる。

ペナルティ関数

$F^{k}(x) = f(x) + \frac{k}{2}||g(x)||^{2} + \frac{\alpha}{2}||x-x^{*}||^{2}$

等式制約問題の最適性必要条件
1次の最適性必要条件の幾何学的解釈
- 制約が1つ g(x)=0 だけのときは、この範囲内で微小量移動させても目的関数 f(x) の値は変化しない。
局所最適解に対するラグランジュ乗数ベクトルの意味
- $g_{i}(x)=0$ を $g_{i}(x)=\delta w_{i}$ だけ変化させたときに、目的関数値が $f(x^{*})$ から $-u_{i}^{*}\delta w_{i}$ だけ変化する。
等式問題の最適性十分条件