Approximation, reformulation and convex techniques for cardinality optimization problems

Mohammad Abdi; Yunbin ZHAO

Makale detayları

Approximation, reformulation and convex techniques for cardinality optimization problems

Yazarlar:

Mohammad Abdi | Yunbin ZHAO

Yayıncı:

Istanbul University

Ana Başlıklar:

Sosyoloji & antropoloji

Dergi:

İstanbul Üniversitesi İşletme Fakültesi Dergisi 2011 Vol.40 Issue 2, pp.124-137

Belge Tipi:

Makale

Yayın Tarihi:

12/2010

Belge Dili:

İngilizce

Document ID (Org No.):

2000480670

Sıklık:

İki Yıllık

eISSN:

2630-5488

Özet:

 


The cardinality minimization problem (CMP) is finding a vector with minimum cardinality, which satisfies certain linear (or non-linear) constraints. This problem is closely related to the so-called compressive sensing problems. In this paper we survey and study different approximation, reformulation and convex relaxations for both cardinality constraint problems and cardinality minimization problems, and discuss how to add a penalty function to the objective in order to get a reformulation/approximation model of the original problems, instead of simply dropping the rank constraint. By reformulation techniques, under some mild condition we may either transform the problem to a mixed integer linear program (MILP) or the so-called bilevel SDP problems. We also point out that a continuous approximation of cardinality functions can enable us to apply majorization method to extract proper weights for the (re)weighted l1 algorithms.

.

 


 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.

.

Makale detayları

Approximation, reformulation and convex techniques for cardinality optimization problems

Yazarlar: Mohammad Abdi | Yunbin ZHAO

Yayıncı: Istanbul University

Ana Başlıklar: Sosyoloji & antropoloji

Dergi: İstanbul Üniversitesi İşletme Fakültesi Dergisi 2011 Vol.40 Issue 2, pp.124-137

Belge Tipi: Makale

Yayın Tarihi: 12/2010

Belge Dili: İngilizce

Document ID (Org No.): 2000480670

Sıklık: İki Yıllık

eISSN: 2630-5488

Sayı

Yazarlar:

Mohammad Abdi | Yunbin ZHAO

Yayıncı:

Istanbul University

Ana Başlıklar:

Sosyoloji & antropoloji

Dergi:

İstanbul Üniversitesi İşletme Fakültesi Dergisi 2011 Vol.40 Issue 2, pp.124-137

Belge Tipi:

Makale

Yayın Tarihi:

12/2010

Belge Dili:

İngilizce

Document ID (Org No.):

2000480670

Sıklık:

İki Yıllık

eISSN:

2630-5488