Bagaimana pemrograman geometrik berbeda dari pemrograman cembung?

10

Bagaimana pemrograman geometris (umum) berbeda dari pemrograman cembung umum?

Program geometrik dapat ditransformasikan menjadi program cembung, dan biasanya diselesaikan dengan metode titik interior. Tetapi apa keuntungan dari merumuskan secara langsung masalah sebagai program cembung dan menyelesaikannya dengan metode titik interior?

Apakah kelas program geometrik hanya merupakan subset dari kelas program cembung yang dapat diselesaikan terutama efisien dengan metode titik interior? Atau keuntungannya hanya karena program geometris umum dapat dengan mudah ditentukan dalam bentuk yang dapat dibaca komputer.

Di sisi lain, apakah ada program cembung yang tidak dapat didekati dengan cukup baik oleh program geometris?

Thomas Klimpel
sumber

Jawaban:

5

Saya sebenarnya belum pernah mendengar tentang pemrograman geometris sampai pertanyaan ini. Berikut ini adalah makalah ulasan oleh Stephen Boyd, et al (Vandenberghe adalah rekan penulis juga) yang merupakan tutorial tentang pemrograman geometris.

Program-program geometris seperti yang awalnya dinyatakan tidak cembung. Sebagai contoh, adalah posinomial, dan itu bukan cembung, jadi program geometris bukan subset ketat pemrograman cembung.x1/2

Keuntungan mengubah program geometrik menjadi program cembung adalah bahwa program geometris asli tidak harus cembung. Jika Anda menyelesaikan program geometrik sebagai program nonlinear (NLP), Anda perlu menggunakan metode dari optimasi non-cembung untuk menjamin solusi optimal global. Metode ini lebih mahal daripada metode optimisasi cembung, membutuhkan penyetelan algoritmik lebih banyak, dan memerlukan tebakan awal.

Selain itu, jika Anda menggunakan algoritme dari NLP non-cembung, Anda perlu menentukan set yang layak sebagai set kompak di ; dalam program geometris, adalah batasan yang valid.Rnx>0

Tidak jelas apakah set program geometris memetakan (melalui transformasi log-eksponensial) ke set program cembung yang memecahkan terutama secara efisien. Saya tidak melihat keuntungan dari pemrograman geometris di luar transformasi ke program cembung.

Adapun pertanyaan terakhir Anda, saya tidak berpikir set program geometrik adalah isomorfik dengan set program cembung, jadi saya menduga bahwa ada program cembung yang tidak dapat dinyatakan sebagai program geometris, dan dari program ini, saya menduga ada adalah beberapa yang tidak dapat didekati dengan cukup baik oleh program geometris. Namun, saya tidak punya bukti atau contoh tandingan.

Geoff Oxberry
sumber
Sepertinya bab 8 makalah ulasan Anda yang terhubung mencoba menjawab pertanyaan saya. Namun, setelah melihat sepintas lalu, saya mendapat kesan bahwa sebenarnya setiap program cembung dapat didekati dengan program geometris (tentu saja diubah secara logaritma ...). Namun, karena setiap program linear "jelas" juga merupakan program geometris, ini juga bisa menjadi varian pernyataan bahwa program cembung apa pun dapat didekati dengan program linier, tetapi itu tidak akan menjadi apa yang saya maksudkan dengan "didekati secara wajar". baik".
Thomas Klimpel
Ketika istilah pemrograman geometris muncul, tidaklah mudah untuk menyelesaikan program cembung umum, dan struktur khusus dapat dieksploitasi. Sekarang, tentu saja, sekali orang mengakui bahwa suatu program adalah geometris, seseorang mengubahnya menjadi program cembung dan memecahkan yang terakhir dengan metode titik interior.
Arnold Neumaier
3

Pemrograman geometri dapat ditransformasikan menjadi kelas program cembung yang merupakan himpunan bagian yang ketat dari semua program cembung. Namun program cembung yang sewenang-wenang tidak dapat dinyatakan sebagai program geometris. Batasan dalam Pemrograman Geometris dibatasi dari bentuk mana adalah posinomial (yaitu polinomial dengan koefisien positif). Posinomial ditutup dengan penambahan, perkalian, dan penskalaan positif . Sekarang jika Anda mempertimbangkan kendala , makaf(x)1f(x)xy1xyitu sendiri bukan posinomial. Itu tidak dapat direpresentasikan sebagai penambahan / penggandaan posinomial dan tidak bisa menjadi penskalaan positif dari posinomial lain. Dengan demikian itu tidak dapat menjadi bagian dari program geometris. Tetapi kendala di atas adalah linier dan dengan demikian programnya cembung. Memang ada pemrograman geometris linier campuran di mana seseorang dapat menambahkan kendala linear sewenang-wenang yang juga dapat dikonversi menjadi program cembung dan diselesaikan secara efisien. Sekali lagi kendala yang lebih rumit seperti tidak dapat ditangani bahkan oleh pemrograman geometris linier campuran untuk alasan yang sama seperti yang diberikan di atas.x2y21

Memilih
sumber
Pemrograman geometris bukanlah subset ketat dari pemrograman cembung; Namun, di bawah transformasi log-eksponensial, program geometri yang ditransformasikan adalah program cembung.
Geoff Oxberry
Ya, itulah yang ingin saya katakan. Jawaban yang diedit untuk kejelasan.
Memilih