Memaksimalkan fungsi cembung (meminimalkan fungsi cekung) dengan batasan linier

10

Masalahnya adalah

maxf(x) subject to Ax=b

di mana f(x)=i=1N1+xi4(i=1Nxi2)2 ,
x=[x1,x2,...,xN]TRN×1 , dan
ARM×N

Kita dapat melihat bahwa f(.) Dalam bentuk 1+y2 dan merupakan fungsi cembung.
Dapat juga ditunjukkan bahwa f (.) Dibatasi dalam [2,2] .

Ini adalah masalah minimisasi cembung dengan kendala linier.

Manakah standar algoritma yang digunakan untuk memecahkan masalah semacam ini?

Dengan menggunakan sifat spesifik masalah, apakah mungkin untuk menyelesaikannya menggunakan perangkat lunak / paket optimasi standar?

Sooraj
sumber
Sudahkah Anda mencoba menggunakan pengganda Lagrange untuk melihat apakah itu mengubahnya menjadi sesuatu yang lebih mudah ditelusur?
Nathaniel

Jawaban:

7

Anda dapat mengambil keuntungan dari struktur masalah, meskipun saya tahu tidak ada pemecah masalah yang akan melakukannya untuk Anda.

Pada dasarnya, yang Anda cari adalah meminimalkan fungsi cekung di atas cembung polytope (atau cembung polihedron). Pencarian cepat menarik beberapa sumber yang relevan (saya samar-samar ingat salah satu dari ini disebutkan ketika saya mengambil kelas pada pemrograman nonlinier lebih dari empat tahun yang lalu):

Falk, JE, dan Hoffman, minimalisasi Cekung KL melalui poltop runtuh , Riset Operasi, 1986, Vol. 34, No. 6, hal. 919-929.

Hoffman, KL Sebuah metode untuk meminimalkan fungsi cembung secara global dari set cembung , Pemrograman Matematika, 1981, Vol. 20, hlm. 22-31.

Benson, HP Algoritma terbatas untuk minimalisasi cekung melalui polyhedron , Naval Research Logistics, 1985, Vol. 32, No. 1, hal. 165-177.

Banyak referensi di situs web Christophe Meyer .

Ada lebih banyak sumber jika Anda Google "meminimalkan fungsi cekung di atas polytope" (atau ganti "polytope" dengan "polyhedron").

Geoff Oxberry
sumber
2

Saya menghadiri beberapa tahun lalu sebuah kuliah tentang optimasi. Saat itu kami menggunakan Matlab dalam kombinasi dengan YALMIP.

Wiki YALMIP

Dohn Joe
sumber
1

Masalah ini dapat dilihat sebagai perbedaan dari masalah pemrograman fungsi cembung (DC). Ada banyak literatur tentang pemrograman DC, Anda dapat mencari studi terkait di sana. Salah satu metode yang paling terkenal adalah metode DCA, lihat misalnya: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Makalah baru-baru ini yang mensurvei literatur DC sampai batas tertentu dan mungkin berguna adalah: https://arxiv.org/pdf/1511.01796.pdf

Anda juga dapat menggunakan beberapa metode yang lebih umum untuk masalah nonsmooth, misalnya metode berbasis prox yang diberikan dalam: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

nvhk
sumber
0

Saya akan menawarkan algoritma Frank Wolfe dan metode terkait untuk pertimbangan Anda. Pada dasarnya, Anda membuat linierisasi fungsi objektif dan menyelesaikan LP yang dihasilkan pada setiap iterasi. Saya pikir, bagaimanapun, bahwa Anda perlu menambahkan batas pada untuk membuat pendekatan ini efektif.x

Michael Grant
sumber