Doğrusal Olmayan Programlama İçin İkinci Derece Aktif Küme Yöntemleri : Büyük Boyutlu Veri İşleme Problemleri Üzerinde Uygulamalar

Abstract

Bu projede veri işleme uygulamalarında karşılaşılan ve iki bileşenli bir fonksiyonun –konveks türevlenebilir bir fonksiyon ile türevlenemeyen bir regülarizasyon fonksiyonunun toplamı– minimizasyonundan ibaret olan bir grup doğrusal olmayan matematiksel programlama problemi üzerinde çalıştık. Ses tanıma, görüntü işleme, yazılı metin verilerinin etiketlenmesi gibi pek çok uygulamada bu şekilde ifade edilebilecek matematiksel programlama problemleri karşımıza çıkmaktadır. Projede, temel olarak regülarizasyon teriminin değişkenlerin l1-normuna eşit olduğu ve seyrek eniyileme olarak da anılan problemlere odaklandık. Uygulamada, anılan problemlerin boyutları oldukça büyüktür; bu sebeple, yakınsama hızlarının yüksek olduğu bilindiği halde ikinci derece yöntemler pratik uygulamalarda tercih edilmemektedir. Çünkü her ne kadar daha az adımda çözüme ulaşmaları beklense de, ikinci derece yöntemlerin her bir adımının hesaplama maliyeti oldukça yüksektir. Bu yüzden, sıkça kullanılan yöntemlerin çoğu sadece birinci derece problem bilgisi kullanmaktadır. Biz bu proje kapsamında, ikinci derece aktif küme yöntemleri üzerinde çalıştık. İki temel ?kirden hareketle, hem pratik performansı yüksek ve hem de teorik olarak güçlü özelliklere sahip yeni algoritmalar geliştirdik: (1) problemin matematiksel yapısından istifade etmek, (2) yaklaşık (inexact) hesaplamalar yapmak. Projede iki grup aktif küme yöntemi üzerine çalışmalar yaptık: Blok-Aktif-Newton ve Sınırlı-Altuzay-Newton. Bunlardan ilki, parçalı kuadratik bir altproblemin çözümünü gerektirdiği için yöntemin pratik olabilmesi bu alt problemin yaklaşık çözülmesiyle mümkündür; bu bağlamda, global ve hızlı yerel yakınsama garantileri sağlayan bir yaklaşık çözüm kriteri geliştirdik. İkinci grup için ise en kritik olan konu altuzay seçimidir; dolayısıyla, yine yakınsama garantisi sağlayan seçim mekanizmaları geliştirmeye çalıştık. Her iki grupta da büyük boyutlu seyrek eniyileme problemlerini dahi etkinlikle çözebilecek yeni algoritmalar tasarladık. Bu algoritmaların teorik özelliklerinin yanı sıra numerik performanslarını da analiz ettik.