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

 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.

Approximation, reformulation and convex techniques for cardinality optimization problems

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.
Istanbul Business Research-Cover
  • Yayın Aralığı: Yılda 3 Sayı
  • Başlangıç: 2013
  • Yayıncı: İstanbul Üniversitesi Yayınevi
Sayıdaki Diğer Makaleler

Girişimci yönetim biçimi ve finansal performans ilişkisi: Çanakkale Bölgesi'nde faaliyet gösteren otel işletmelerinde bir araştırma

Gultekin ALTUNTAS, Dilek DONMEZ, Tarik BİRGOREN

Geleneksel ilan ve advertorial (tanıtıcı reklam) uygulamalarının reklam ve reklamı yapılan ürünün algısına ilişkin değerlemelerinin faktör analizi temelli incelenmesi

Abdullah OKUMUŞ, Naim ÇETİNTÜRK, Eyüp ÇETİN

Ülke imajı: Japonya ve Çin’in ülke imajları açısından karşılaştırılması

Kemal KURTULUŞ, Zehra BOZBAY

Hastanelerde iş sağlığı ve güvenliği uygulamalarının değerlendirilmesine yönelik bir araştırma

Vala TÜZÜNER, Burcu ÖZASLAN

Enflasyon etkisi altında ve kıtlık gösteren bozulabilir ürünlere yönelik ekonomik sipariş büyüklüğü modeli için optimum fiyatlandırma ve sipariş büyüklüğü belirleme politikaları için basit yaklaşım

M. VALLİATHAL, R. UTHAYAKUMAR

İstanbul Menkul Kıymetler Borsası'nda volatilitenin modellenmesi: Box-Jenkins modellerden ARCH ailesi modellere geçiş

Ümit GÜMRAH, Rasim GÖKBULUT, Sinem DERİNDERE KÖSEOĞLU

Vol 40, No 2 Issue Front Pages

Baris Kiremitci

Finansal tablolarda şerefiye ve maddi olmayan duran varlıkların değer ilişkisi ve güvenilirliği: İstanbul Menkul Kıymetler Borsası uygulaması

Ümit GÜMRAH, Burcu ADİLOĞLU

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

Mohammad Abdi, Yunbin ZHAO

AB ülkeleri ve aday ülkelerin kaynak kullanımında etkinliklerinin karşılaştırmalı analizi

Habib KOÇAK, Ahmet ÇİLİNGİRTÜRK