- İstanbul Üniversitesi İşletme Fakültesi Dergisi
- Vol: 40 Issue: 2
- Approximation, reformulation and convex techniques for cardinality optimization problems
Approximation, reformulation and convex techniques for cardinality optimization problems
Authors : Mohammad Abdi, Yunbin Zhao
Pages : 124-137
View : 8 | Download : 5
Publication Date : 2010-12-11
Article Type : Research
Abstract : Küme eleman sayılarının minimizasyon problemi, belirli doğrusal (veya doğrusal olmayan) kısıtları karşılayan minimum küme eleman sayısını içeren bir vektör bulmakla ilgilidir. Problem, başınç algılama problemi olarak da anılan problemle yakından ilişkilidir. Bu çalışmada, küme eleman kısıt problemleri ve küme eleman sayılarının minimizasyon problemleri için çeşitli yakınsak, yeniden formüle etme ve dışbükey gevşetmeler yer almakta ve yalnızca rank kısıtını dışlamaktan çok orijinal problemin yeniden formüle edilmesi/yakınsanması için amaca nasıl bir ceza fonksiyonu ekleneceğini tartışılmaktadır. Yeniden formüle etme teknikleri ile bazı hafif koşullarda, problem, ya karma tam sayılı doğrusal programlama ya da iki kademeli yarı tanımlı programlama problemlerine dönüştürülebilir. Küme eleman sayısı fonksiyonlarının sürekli yakınsanması, l1 algoritmalarının (yeniden) ağırlıklandırılarak uygun ağırlıklarının belirlenmesi amacıyla majorlaştırma yönteminin uygulanmasına izin verir.Keywords : Küme eleman sayılarının (cardinality) optimizasyon problemi, l1 - minimizasyonu, basınçlı algılama, dışbükey optimizasyon, (yeniden) ağırlıklandırılmış l 1 - minimizasyonu, Lagrangian gevşetme