Approximation algorithms for difference of convex (DC) programming problems
Dışbükey farkı (DC) programlama problemleri için yaklaşıklama algoritmaları
- Tez No: 828262
- Danışmanlar: DR. ÖĞR. ÜYESİ FİRDEVS ULUS
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 90
Özet
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.
Özet (Çeviri)
This thesis is concerned with Difference of Convex (DC) programming problems and approximation algorithms to solve them. There is an existing exact algorithm that solves DC programming problems if one component of the DC function is polyhedral convex [1]. Motivated by this, first, we propose an algorithm (Algorithm 1) for generating an ϵ-polyhedral underestimator of a convex function g. The algorithm starts with a polyhedral underestimator of g and the epigraph of the current underestimator is intersected with a single halfspace in each iteration to obtain a better approximation. We prove the correctness and establish the convergence rate of Algorithm 1. We also propose a modified variant (Algorithm 2) in which multiple halfspaces are used to update the epigraph of current approximation in each iteration. In addition to its correctness, we prove that Algorithm 2 terminates after finitely many iterations. We show that after obtaining an ϵ-polyhedral underestimator of the first component of a DC function, the algorithm from [1] can be applied to compute an ϵ-solution of the DC programming problem. We also propose an algorithm (Algorithm 3) for solving DC programming problems directly. In each iteration, Algorithm 3 updates the polyhedral underestimator of g locally while searching for an ϵ solution to the DC problem directly. We prove that the algorithm stops after finitely many iterations and it returns an ϵ-solution to the DC programming problem. Moreover, the sequence {x_k}_{k≥0} outputted by Algorithm 3 converges to a global minimizer of the DC problem when ϵ is set to zero. The computational results, obtained using some test examples from [2], show comparable performance of Algorithms 1, 2 and 3 with respect to two DC programming algorithms from the literature.
Benzer Tezler
- Inventory optimization under process flexibility assumptions using approximate dynamic programming approaches
Süreç esnekliği varsayımları altında benzetimsel dinamik programlama yaklaşımlarıyla envanter optimizasyonu
MUSTAFA ÇİMEN
Doktora
İngilizce
2014
İşletmeLancaster Universityİşletme Ana Bilim Dalı
PROF. DR. KEVIN GLAZEBROOK
DR. CHRISTOPHER KIRKBRIDE
- Kablolu taşıyıcı sistemlerin nonlineer statik analizi için bir yöntem
A Method for nonlinear static analysis of cable nets
FİLİZ PİROĞLU
- Signal and image processing algorithms using interval convex programming and sparsity
Aralık dışbükey programlama ve seyreklik kullanan imge ve sinyal işleme algoritmaları
KIVANÇ KÖSE
Doktora
İngilizce
2012
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. AHMET ENİS ÇETİN
- Matrix representation of quantum B-spline functions
Kuantum B-spline fonksiyonlarının matris temsilleri
MERVE KAPLAN
Yüksek Lisans
İngilizce
2023
MatematikDokuz Eylül ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜLTER BUDAKÇI
- Compressive sensing of cyclostationary propeller noise
Çevrimsel durağan pervane gürültüsü için sıkıştırmalı algılama
UMUT FIRAT
Doktora
İngilizce
2023
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAYFUN AKGÜL
