Approximation, reformulation and convex techniques for cardinality optimization problems

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

Özet

Küme eleman sayılarının minimizasyon problemi, belirli doğrusal (veya doğrusalolmayan) kısıtları karşılayan minimum küme eleman sayısını içeren bir vektör bulmaklailgilidir. 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 minimizasyonproblemleri için çeşitli yakınsak, yeniden formüle etme ve dışbükey gevşetmeler yeralmakta ve yalnızca rank kısıtını dışlamaktan çok orijinal problemin yeniden formüleedilmesi/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 problemlerinedönüştürülebilir. Küme eleman sayısı fonksiyonlarının sürekli yakınsanması, l1algoritmalarının (yeniden) ağırlıklandırılarak uygun ağırlıklarının belirlenmesi amacıylamajorlaştırma yönteminin uygulanmasına izin verir.

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 tothe so-called compressive sensing problems. In this paper we survey and study differentapproximation, reformulation and convex relaxations for both cardinality constraintproblems and cardinality minimization problems, and discuss how to add a penaltyfunction to the objective in order to get a reformulation/approximation model of theoriginal problems, instead of simply dropping the rank constraint. By reformulationtechniques, under some mild condition we may either transform the problem to a mixedinteger linear program (MILP) or the so-called bilevel SDP problems. We also point outthat a continuous approximation of cardinality functions can enable us to applymajorization method to extract proper weights for the (re)weighted l1 algorithms.