Bagaimana pemrograman geometrik berbeda dari pemrograman cembung?

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?

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.$x^{1/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.$\mathbb{R}^{n}$$x > 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.

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 , maka$f(x) \leq 1$$f(x)$$-x-y \leq 1$$-x-y$itu 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.$-x^2-y^2\leq 1$