Pertimbangkan masalah optimisasi cembung yang tidak dibatasi ketatBiarkan x_ \ text {opt} menunjukkan minima uniknya dan x_0 menjadi perkiraan awal yang diberikan kepada x_ \ text {opt}. Kami akan memanggil vektor x solusi \ epsilon- close dari \ mathcal {O} jika \ begin {persamaan} \ frac {|| x - x _ {\ text {opt}} || _2} {|| x_0 - x_ \ text {opt} || _2} \ leq \ epsilon. \ end {persamaan}x opt x 0 x opt . x ϵ -
Misalkan terdapat dua algoritma iteratif dan untuk menemukan solusi close dari dengan properti berikut:
- Untuk setiap upaya komputasi total, yaitu upaya yang diperlukan per iterasi jumlah total iterasi, untuk menemukan solusi close sama untuk kedua algoritma.
- Upaya per iteration untuk adalah katakanlah, sementara itu dari adalah
Apakah ada situasi, di mana satu lebih suka satu algoritma daripada yang lain? Mengapa?
sumber