Approximation algorithms for difference of convex (DC) programming problems

Bu tezde dışbükey farkı (DC) programlama problemleri ve yaklaşıklama algoritmaları çalışılmıştır. DC fonksiyonunun bir bileşeni dışbükey çokyüzlü olduğunda DC programlama problemlerini çözen mevcut bir kesin algoritma bulunmaktadır [1]. Bundan yola çıkarak bu tezde, öncelikle bir dışbükey g fonksiyonunun ϵ-çokyüzlü azımsayıcısını oluşturmak için bir dış yaklaşıklama algoritması (Algoritma 1) önerilmiştir. Algoritma 1, g'nin bir çokyüzlü azımsayıcısı ile başlar ve her tekrarda, daha iyi bir yaklaşık elde etmek için mevcut yaklaşık çokyüzlü fonksiyonun epigrafını tek bir yarıuzay ile keser. Algoritma 1'in doğruluğu kanıtlanmış ve yaklaşıklama oranı hesaplanmıştır. Buna ek olarak Algoritma 1'in değiştirilmiş bir varyantı (Algoritma 2) önerilmiştir. Algoritma 2'nin temel farkı her tekrarda mevcut çokyüzlü fonksiyonu güncellerken bir değil birden fazla yarıuzayın tek seferde epigraf ile kesiştirilmesidir. Doğruluğuna ek olarak, Algoritma 2'nin sonlu tekrardan sonra sona erdiği kanıtlanmıştır. DC fonksiyonunun ilk bileşeninin ϵ-çokyüzlü azımsayıcısı elde edildikten sonra, [1]'deki algoritmanın DC programlama problemine bir ϵ-çözüm bulmak için uygulanabildiği gösterilmiştir. Tezde ayrıca DC programlarını doğrudan çözmek için üçüncü bir algoritma (Algoritma 3) önerilmiştir. Algoritma 3, diğer iki algoritma gibi g'ye çokyüzlü azımsayıcı oluşturarak ilerler. Ancak bu algoritma her tekrarda doğrudan DC programlama probleminin bir ϵ-çözümünü arar ve bunu yaparken g'nin çokyüzlü azımsayıcısını yerel olarak günceller. Algoritmanın sonlu sayıda yinelemeden sonra durduğunu ve DC programlama problemine bir ϵ-çözüm bulduğu kanıtlanmıştır. Buna ek olarak, ϵ sıfıra eşitlendiğinde, Algoritma 3'ün çıktısı olan {x_k}_{k≥0} dizisinin DC probleminin evrensel azımsayıcısına yakınsadığı kanıtlanmıştır. Bazı test problemleri kullanılarak elde edilen deneysel sonuçlar, bu tezde önerilen algoritmaların mevcut iki DC programlama algoritmasına göre karşılaştırılabilir performansa sahip olduğunu göstermektedir.