Küme eleman sayılarının (cardinality) optimizasyon problemlerine yönelik yakınsak, yeniden formüle etmeli ve dışbükey teknikler

Year 2011, Volume: 40 Issue: 2, 124 - 137, 11.12.2010

Mohammad Abdi Yunbin Zhao

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

Approximation, reformulation and convex techniques for cardinality optimization problems

Abstract

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.

Keywords

Cardinality optimization problem, l1 -minimization, compressive sensing, convex optimization, (re)weighted l 1 - minimization, Lagrangian relaxation