อัลกอริทึมสำหรับปัญหานูน

วิธีการโคตรชัน

วิธีนี้เรียกอีกอย่างว่าวิธีการไล่ระดับสีหรือวิธีของ Cauchy วิธีนี้เกี่ยวข้องกับคำศัพท์ต่อไปนี้ -

$$ x_ {k + 1} = x_k + \ alpha_kd_k $$

$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ หรือ $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $

ให้ $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

โดยการแยกความแตกต่างของ $ \ phi $ และเทียบเคียงเป็นศูนย์เราจะได้ $ \ alpha $

ดังนั้นอัลกอริทึมจะเป็นดังนี้ -

• เริ่มต้น $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ และตั้งค่า $ k = 0 $

• ตั้งค่า $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ หรือ $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.

• หา $ \ alpha_k $ เพื่อที่จะย่อ $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

• ตั้งค่า $ x_ {k + 1} = x_k + \ alpha_kd_k $

• ถ้า $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ หรือ $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $ ไปที่ขั้นตอนที่ 6 หรือตั้งค่า $ k = k + 1 $ แล้วไปที่ขั้นตอนที่ 2

• ทางออกที่ดีที่สุดคือ $ \ hat {x} = x_ {k + 1} $

วิธีนิวตัน

Newton Method ทำงานบนหลักการต่อไปนี้ -

$ f \ left (x \ right) = y \ left (x \ right) = f \ left (x_k \ right) + \ left (x-x_k \ right) ^ T \ bigtriangledown f \ left (x_k \ right) + \ frac {1} {2} \ left (x-x_k \ right) ^ TH \ left (x_k \ right) \ left (x-x_k \ right) $

$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x-x_k \ right) $

ที่ $ x_ {k + 1} \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ right) $

เพื่อให้ $ x_ {k + 1} $ เป็นทางออกที่ดีที่สุด $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

ดังนั้น $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $

ที่นี่ $ H \ left (x_k \ right) $ ควรไม่ใช่เอกพจน์

ดังนั้นอัลกอริทึมจึงเป็นดังนี้ -

Step 1 - เริ่มต้น $ x_0, \ varepsilon $ และตั้งค่า $ k = 0 $

Step 2 - หา $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $

Step 3 - แก้ระบบเชิงเส้น $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ สำหรับ $ h \ left (x_k \ right) $

Step 4 - หา $ x_ {k + 1} = x_k-h \ left (x_k \ right) $

Step 5- ถ้า $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ หรือ $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ จากนั้นไปที่ขั้นตอนที่ 6 จากนั้นตั้งค่า $ k = k + 1 $ แล้วไปที่ขั้นตอนที่ 2

Step 6 - ทางออกที่ดีที่สุดคือ $ \ hat {x} = x_ {k + 1} $

ผันวิธีการไล่ระดับสี

วิธีนี้ใช้สำหรับการแก้ปัญหาประเภทต่อไปนี้ -

$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $

โดยที่ Q คือเมทริกซ์ nXn ที่แน่นอนเป็นบวกและ b เป็นค่าคงที่

ให้ $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

ตั้ง $ d_0 = -g_0 $ สำหรับ $ k = 0,1,2, ... , $

กำหนด $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

คำนวณ $ x_ {k + 1} = x_k + \ alpha_kd_k $

ตั้งค่า $ g_ {k + 1} = g_k + \ alpha_kd_k $

คำนวณ $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $

คำนวณ $ x_ {k + 1} = x_k + \ alpha_kd_k $

ตั้งค่า $ g_ {k + 1} = x_k + \ alpha_kQd_k $

คำนวณ $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $

ตั้งค่า $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $