Pertimbangkan masalah optimasi cembung dalam formulir
di mana adalah fungsi cembung. Tanpa kehilangan keumuman, kita dapat mengasumsikan bahwa adalah linear.
Nesterov dan Nemirovskii menyebutkan dalam buku mereka "Algoritma polinomial titik interior dalam pemrograman cembung" bahwa ada algoritma yang dapat menyelesaikan program cembung dalam waktu polinomial dalam arti berikut. Kami ingin memiliki solusi dalam akurasi relatif dengan biaya perhitungan nilai dan perhitungan dari subgradien. Kemudian, untuk metode ellipsoid, diklaim demikian
Pada pandangan pertama, ini tampaknya menyiratkan bahwa masalah optimisasi cembung dapat diselesaikan dalam waktu polinomial menggunakan metode ellipsoid (mari kita asumsikan untuk kesederhanaan bahwa nubuat untuk menghitung nilai-nilai dan subgradien membutuhkan waktu untuk kelas yang dipertimbangkan dari masalah optimisasi cembung).
Namun, saya benar-benar tidak mengerti, apakah ekspresi entah bagaimana tergantung pada fungsi , misalnya pada Hessians mereka, atau tidak. Dalam hal ini, kompleksitas mungkin memiliki ledakan eksponensial karena sifat kelengkungan fungsi. Selain itu, secara misterius diklaim bahwa "metode ellipsoid tidak bekerja dengan baik dalam praktik". Sepertinya tidak ada konsensus di internet apakah jawaban untuk pertanyaan saya adalah afirmatif atau negatif, lihat misalnya diskusi tentang MathOverflow ini.
Saya telah mencari di setiap buku tentang optimasi cembung yang dapat saya temukan, dan saya mendapat kesan bahwa memang tergantung pada masalahnya, tetapi tidak dapat menemukan konfirmasi yang jelas tentang dugaan ini. Jadi satu-satunya harapan saya adalah secara langsung bertanya kepada orang-orang yang melakukan penelitian di bidang ini.
Metode titik interior yang telah dikembangkan kemudian tampaknya secara eksplisit memperhitungkan kelengkungan menggunakan gagasan hambatan yang sesuai dengan diri sendiri. Tetapi ketika orang mengatakan bahwa metode ini efisien dalam praktiknya, mereka biasanya tidak menentukan ini pada tingkat kompleksitas.
sumber
Jawaban:
Pada tahun 1998, Michel X. Goemans memberikan ceramah ICM, di mana, ia membahas masalah ini: "Program semidefinit dapat diselesaikan (atau lebih tepatnya, didekati) dalam waktu polinomial dalam akurasi tertentu baik dengan algoritma ellipsoid atau lebih efisien melalui interior-point algoritme ... Algoritme di atas menghasilkan solusi yang sangat layak (atau sedikit tidak layak untuk beberapa versi dari algoritma ellipsoid) dan, pada kenyataannya, masalah memutuskan apakah program semidefinite layak (tepatnya) masih terbuka. kasus khusus kelayakan pemrograman semidefinite adalah masalah kuadrat-akar-jumlah. Kompleksitas masalah ini masih terbuka. " http://garden.irmacs.sfu.ca/op/complexity_of_square_root_sum
Pada tahun 1976, Ron Graham, Michael Garey, dan David Johnson tidak dapat menunjukkan beberapa masalah optimasi geometrik seperti apakah Euclidean Travelling Salesman Problem adalah NP-complete (mereka hanya bisa menunjukkan masalahnya NP-hard), alasannya adalah mereka tidak bisa perlihatkan apakah masalah kuadrat-akar-jumlah dapat dipecahkan waktu polinomial atau tidak. https://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/
Masalah kuadrat-akar-jumlah adalah masalah terbuka yang panjang yang membingungkan para sarjana dari geometri komputasi, optimisasi, kompleksitas komputasi, teori permainan, dan beberapa bidang lainnya karena mereka semua pada titik tertentu, mencari tahu kendala utama untuk masalah mereka adalah untuk menangani masalah kuadrat-akar-jumlah.
Kemajuan yang paling luar biasa terhadap masalah ini adalah oleh Eric Allender dan rekan penulisnya, pada tahun 2003, mereka menunjukkan masalah ini terletak pada tingkat ke-4 dari Hirarki Penghitungan. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf
Jadi berdasarkan fakta di atas, seseorang tidak dapat memecahkan masalah optimasi cembung dalam waktu polinomial (benar) dengan metode Ellipsoid dan metode Interior Point.
Notasi O besar adalah untuk mengukur waktu berjalan algoritma dalam kasus terburuk. Namun, dalam praktiknya, kasus terburuk mungkin merupakan peristiwa yang sangat langka, itu sebabnya Anda tidak dapat menggunakannya untuk mengukur kinerja praktis.
sumber