A new geometric duality and approximation algorithms for convex vector optimization problems
Dışbükey vektör eniyileme problemleri için yeni bir geometrik çifteşlik teorisi ve dış yaklaşıklama algoritmaları
- Tez No: 685059
- Danışmanlar: DR. ÖĞR. ÜYESİ FİRDEVS ULUS, DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- 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ı: 82
Özet
Literatürde, dışbükey vektör eniyileme problemlerinin çözümü için farklı yöntemler geliştirilmiştir. Yaklaşıklama algoritmaları da bu yöntemlerden bir tanesidir. Yaklaşıklama algoritmaları, karar uzayındaki bütün verimli çözümlerin kümesini elde etmek yerine amaç uzayındaki Pareto kümeyi yaklaşıklamayı hedefler. Yaklaşıklama algoritmalarının temel yöntemlerinden bir tanesi, skalerizasyon modelleri çözerek, yaklaşık kümeyi her adımda iyileştirmektir. Temel algoritma olarak adlandırılan dış yaklaşıklama algoritmalarına ek olarak, geometrik çifteş algoritma olarak adlandırılan ve geometrik çifteş problemi yaklaşıklayan, çifteş uzayda tanımlı algoritmalar vardır. Literatürdeki pek çok temel ve çifteş algoritmanın skalerizasyon yöntemleri, çözüm tanımları ve yapıları, belirli bir yön vektörüne bağlı olarak tasarlanmıştır. Yakın zamanda, yön vektörü parametresine bağlı olmayan bir temel algoritma geliştirildi. Temel ve geometrik çifteş kümeler arasındaki geometrik çifteşlik ilişkisini kullanarak, geliştirilen bu temel algoritmaya yeni bir geometrik çifteş algoritma oluşturduk. Geometrik çifteşlik teorisi, çifteş problemin küme değerli eniyi değeri (alt görüntü kümesi) ile üst görüntü kümesi arasında, çokyüzlülerin arasındaki geometrik çifteşlik ilişkisine dayanmaktadır. Bu tezde sunulan temel ve geometrik çifteş algoritmalar bir yön vektörüne bağlı olmadıklarından, alt görüntü kümesi ve üst görüntü kümesi arasında geometrik çifteşlik ilişkisi kurabilmek için yeni bir yöntem geliştirdik. Bunun sonucunda, amaç uzayı boyutu q olan bir temel problem için q+1 boyutlu amaç uzayına sahip bir geometrik çifteş problem geliştirdik. Geliştirilen bu geometrik çifteş problemin alt görüntü kümesini ise dışbükey bir koni olarak belirledik. Temel algoritmayı bu yeni geometrik çifteş probleme de sonlu bir epsilon-çözüm verecek şekilde değiştirdik. Geliştirdigimiz geometrik çifteş algoritmayı ise temel probleme sonlu zayıf delta-çözüm ve geometrik çifteş probleme sonlu epsilon-çözüm verecek şekilde geliştirdik. Temel ve geometrik çifteş algoritmaları MATLAB programı kullanarak hayata geçirdik ve algoritmaların performanslarını kıyaslamak için rastgele dışbükey vektör eniyileme problemleri yarattık. Testler sırasında farklı amaç ve karar uzayı boyutları, farklı sıralama konileri, farklı ell-p-norm değerleri ve farklı durma koşulları kullandık. Geometrik çifteş algoritmanın verilen hata payı durma koşulunun çok altında bir hata sonucu ile durduğunu gözlemledik. Bu durum algoritmanın temel algoritmaya kıyasla çok daha uzun bir çözüm süresine sahip olmasına neden oldu. Durma koşulu çözüm süresi olarak belirlendiğinde, geometrik çifteş algoritmanın özellikle büyük amaç uzayı boyutuna sahip problemlerde daha iyi bir yaklaşıklama sonucu verdiğini gözlemledik.
Özet (Çeviri)
In the literature, there are different algorithms for solving convex vector optimization problems, in the sense of approximating the set of all minimal points in the objective space. One of the main approaches is to provide outer approximations to this set and improve the approximation iteratively by solving scalarization models. In addition to the outer approximation algorithms, which are referred to as primal algorithms, there are also geometric dual algorithms which work on a dual space and approximate the set of all maximal elements of a geometric dual problem. In most of the primal and dual algorithms in the literature, the scalarization methods, the solution concepts and the design of the algorithms depend on a fixed direction vector from the ordering cone. Recently, a primal algorithm that does not depend on a direction parameter is proposed in (Ararat et al., 2021). Using the primal algorithm in (Ararat et al., 2021), we construct a new geometric dual algorithm based on a new geometric duality relation between the primal and dual images. This relation is shown by providing an inclusion reversing one-to-one correspondence between weakly minimal proper faces of the primal image and maximal proper faces of the dual image. For a primal problem with a q-dimensional objective space, we present a dual problem with a q+1-dimensional objective space. Consequently, the resulting dual image is a convex cone. The primal algorithm in (Ararat et al., 2021) is modified to give a finite epsilon-solution to the dual problem as well as a finite weak epsilon-solution to the primal problem. The constructed geometric dual algorithm gives a finite epsilon-solution to the dual problem; moreover, it gives a finite weak delta-solution to the primal problem, where delta is determined by epsilon and the structure of the underlying ordering cone. We implement primal and dual algorithms using MATLAB and test the performance of the algorithms for randomly generated convex vector optimization problems. The tests are performed with different dimensions of the objective and decision spaces, different ordering cones, different ell-p-norms, and different stopping criteria. It is observed that the dual algorithm gives a fraction of the allowed approximation error, epsilon, resulting in a longer runtime with epsilon stopping criterion. When runtime is used as stopping criterion, the dual algorithm returns a closer approximation for higher dimensions of the objective space.
Benzer Tezler
- Geometrik ve topolojik fazın dolanık kuantum durumları için incelenmesi
Investigation of geometric and topological phase for entangled quantum state
HASAN ÖZGÜR ÇILDIROĞLU
Doktora
Türkçe
2020
Fizik ve Fizik MühendisliğiAnkara ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ ULVİ YILMAZER
- Konformal geometrik cebir ile robotlarda ters kinematik problem çözümü
Solution of inverse kinematics problem in robotics using conformal geometric algebra
CEREN AKCAN
Yüksek Lisans
Türkçe
2014
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN TEMELTAŞ
- Çok gruplu ayırma analizinin bazı yeni kriterler yardımıyla gerçekleştirilmesi ve bir uygulama
Discriminant analysis between two or more groups with respect to the some new criteria and an application
HALİL BAYRAKÇI
- Performans tabanlı tasarıma bütünleşik yaklaşım
Integrated design approach to performance based design
BENAN ŞAHİN KARAGÖZ
Yüksek Lisans
Türkçe
2015
Mimarlıkİstanbul Teknik ÜniversitesiBilişim Ana Bilim Dalı
DOÇ. DR. YÜKSEL DEMİR
- Refined geometric transition and local P2
Rafine geometrik geçiş ve lokal P2
BİLAL ÇARK
Yüksek Lisans
İngilizce
2022
Fizik ve Fizik MühendisliğiBoğaziçi ÜniversitesiFizik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CAN KOZÇAZ
PROF. OSMAN TEOMAN TURGUT
DOÇ. AYBİKE ÖZER