On outer approximations of copositive formulations of various nonconvex optimization problems
Çeşitli konveks olmayan problemlerin kopozitif formulasyonlarının dıştan yaklaşımları üzerine
- Tez No: 611295
- Danışmanlar: DR. EMRE ALPER YILDIRIM
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği ve Operasyon Yönetimi
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Kopozitif eniyileme, dışbükey kopozitif veya tamamen pozitif koni üzerinde tanımlanan doğrusal eniyileme problemidir.“Kopozitif programlama”terimi ilk defa 2000 yılında ortaya atılmıştır. Daha sonra, Burer 2009 yılında kombinatoryal ve konveks olmayan problemlerin olduça geniş bir sınıfı olan karma ikili ikinci dereceden eniyileme problemlerinin bir kopozitif eniyileme problemi olarak formule edilebileceğini göstermiştir. Bu önemli çalışma, kopozitif programlama problemlerine olan ilgiyi önemli ölçüde arttırmıştır. Ne var ki, kombinatoryal ve konveks olmayan birçok problemin bir kopozitif eniyileme problemine denk olması sebebiyle kopozitif formulasyonların da genel itibarıyla NP-zor olması şaşırtıcı değildir. Buradaki zorluk tam olarak konik kısıttan kaynaklanmaktadır. Bu sebeple birçok araştırmacı zorlu olan tamamen pozitif koniye kolay konilerden oluşan dıştan yaklaşıklama hiyerarşileri önermiştir. Bu yaklaşıklama hiyerarşilerinin temel prensibi, hiyerarşi seviyesi arttıkça tamamen pozitif koniyi daha iyi yaklaşıklayan ve limitte ona eşit olan bir koni dizisi üretmeye dayanmaktadır. Konveks olmayan ve NP-zor birçok enküçükleme (enbüyükleme) probleminin kopozitif formulasyonundaki zorlu konik kısıt dıştan yaklaşımlar ile değiştirilerek problem için gittikçe sıkılaşan alt (üst) sınırlar elde edilebilmektedir. Bu durum, asıl problem için en iyi çözüme yakın çözümler elde etmek ve problemi çözmeye çalışan algoritmalar geliştirmek açısından fırsatlar sunmaktadır. Bu tezde, üç farklı konveks olmayan ve NP-zor problem sınıfının kopozitif formulasyonlarının dış yaklaşıklamaları incelenmiştir. Öncelikle karma ikili tamsayı problemleri (MBP) ele alınmıştır. Bu problemde dış yaklaşımlardan elde edilen alt sınırlar, problemin doğrusal programlama (LP) gevşetmesinden elde edilen alt sınır ile karşılaştırılmış ve bu alt sınırların en az LP gevşetmeden elde edilen alt sınır kadar iyi olacağı ortaya konmuştur. Bu sonuç olumlu gözükmekle birlikte, çok yüzlü dış yaklaşımlardan elde edilen alt sınırların belli bir seviyeye kadar iyileşmeyeceğini gösteren yeterli ya da gerekli koşullar ortaya konmuştur. Diğer yandan iki kat negatif olmayan (DNN) gevşetmelerin daha iyi alt sınırlar verdiğine yönelik bulgular elde edilmiştir. İkinci olarak (MBP) sınıfındaki özel bir problem olan 0-1 sırt çantası problemi (KP) incelenmiştir. Sırt çantası probleminin iki farklı kopozitif formulasyonu çalışılmış ve çok yüzlü dış yaklaşımlardan elde edilen üst sınırlar LP gevşetmeden elde edilen üst sınırlar ile kıyaslanmıştır. Çok yüzlü dış yaklaşımlardan elde edilen üst sınırların LP gevşetmeden elde edilen üst sınır ile en azından belirli ve oldukça yüksek bir seviyeye kadar aynı alt sınırı vereceği kanıtlanmıştır. Diğer yandan, problemin LP gevşetmesinin tek ve tam sayı olmayan bir en iyi çözümü olması durumunda, DNN gevşetmenin LP gevşetmeden kesinlikle daha iyi alt sınır verdiği ortaya konmuştur. Son olarak standart ikinci dereceden eniyileme probleminin (StQP) DNN gevşetmesinin tam (exact) olduğu örnekler incelenmiştir. DNN gevşetmenin tam olduğu örnekler için cebirsel bir karakterizasyon verilmiştir. DNN gevşetmenin tam olduğu örneklerin kümesi için üç farklı alt küme belirlenmiştir. Bu alt kümelerin her birindeki üyelik problemi polinom zamanda çözülebilmektedir. Ek olarak, DNN gevşetmenin tam olduğu (StQP) örneklerini inşa edebilmek için bir reçete sunulmaktadır. Özetle, sonuçlarımız genel itibariyle çok yüzlü yaklaşımların (MBP) problemi ve 0-1 sırt çantası problemi için zayıf alt sınırlar verdiğine işaret etmekle birlikte, iki kat negatif olmayan gevşetmenin daha sıkı alt sınırlar verdiğine işaret etmektedir.
Özet (Çeviri)
Copositive optimization is linear optimization over the convex cone of copositive or completely positive matrices.“The term copositive programming”was first introduced in 2000. In 2009, Burer showed that mixed binary quadratic optimization problems (MBQP), which comprises a rather large class of nonconvex and combinatorial problems, can be equivalently reformulated as a copositive optimization problem. This seminal work has greatly increased the interest in copositive optimization. It is not surprising, however, that since many combinatorial and nonconvex optimization problems can be reformulated as a copositive optimization problem, copositive programs are also NP-hard in general. The difficulty in the reformulation is entirely due to the conic constraint. For this reason, many researchers have proposed outer approximation hierarchies to the intractable completely positive cone. These approximation hierarchies are composed of a sequence of tractable cones that yield increasingly better approximations of the completely positive cone and are exact in the limit. By replacing the intractable cone by outer approximations in the copositive formulation of nonconvex and NP-hard minimization (resp. maximization) problems, a sequence of increasingly tighter lower (upper) bounds can be obtained for the original problem. This provides opportunities to obtain near-optimal solutions and improve the effectiveness of the algorithms for solving the original problem. In this thesis, we study outer approximations of the copositive reformulations of three classes of nonconvex and NP-hard optimization problems. We first study the class of mixed binary programs (MBPs). We compare the lower bounds arising from outer polyhedral approximations to the lower bound provided by the linear programming (LP) relaxation and establish that the lower bounds due to outer approximations are at least as good as that of LP relaxation. We establish various necessary or sufficient conditions under which the lower bound arising from the outer approximations matches that from the LP relaxation. Our results illustrate the weaknesses of polyhedral approximations. On the other hand, we show that the non-polyhedral doubly nonnegative (DNN) approximations, in general, yield tighter lower bounds. Secondly, we focus on the specific 0-1 knapsack problem (KP) in the class of MBPs. We study two different copositive formulations of the knapsack and compare the upper bounds arising from outer polyhedral approximations to the upper bound provided by the LP relaxation of (KP). We prove that upper bounds obtained from outer polyhedral approximations actually coincide with the upper bound provided by the LP relaxation until at least a certain and fairly large level of the hierarchy. On the other hand, we establish that if the LP relaxation has a non-integer unique solution, then the DNN relaxation gives a strictly better upper bound than the LP relaxation. Finally, we consider the standard quadratic programs (StQP) and investigate the instances of (StQP) for which the DNN relaxation is exact. We establish a complete algebraic characterization of the (StQP) instances that admit an exact DNN relaxation. We explicitly identify three different subsets of such (StQP) instances. Furthermore, we propose a recipe for constructing instances of (StQP) with an exact DNN relaxation. In summary, our results reveal that outer polyhedral approximations, in general, yield weak bounds for (MBP) and for the specific 0-1 knapsack problem, whereas doubly nonnegative relaxations usually give rise to tighter lower bounds.
Benzer Tezler
- Ulaş Sağlık Ocağı merkezinde nüfusun bazı niteliklerine ve konutların durumuna ilişkin bir çalışma
An Investigation carried out at the Ulaş Public Health Centre concerning some characteristics of the population and housing conditions in the district of Ulaş
EROL ŞANLI
Doktora
Türkçe
1985
Halk SağlığıCumhuriyet ÜniversitesiHalk Sağlığı Ana Bilim Dalı
DOÇ. DR. SERVET ÖZGÜR
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
- Diyabetus mellitus'da gözlenen mikrovasküler komplikasyonların prostaglandinler ile olan ilişkisi
The Relation of microvaskular complications observed in diabetes mellitus with prostoglandins
CANAN NEBİGİL
Doktora
Türkçe
1985
Eczacılık ve FarmakolojiCumhuriyet ÜniversitesiFarmakoloji Ana Bilim Dalı
YRD. DOÇ. DR. YUSUF SARIOĞLU
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM