Geri Dön

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ı

  1. Tez No: 685059
  2. Yazar: SİMAY TEKGÜL
  3. Danışmanlar: DR. ÖĞR. ÜYESİ FİRDEVS ULUS, DR. ÖĞR. ÜYESİ ÇAĞIN ARARAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2020

    Fizik ve Fizik MühendisliğiAnkara Üniversitesi

    Fizik Mühendisliği Ana Bilim Dalı

    PROF. DR. ALİ ULVİ YILMAZER

  2. 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

    Türkçe

    2014

    Mekatronik Mühendisliğiİstanbul Teknik Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    PROF. DR. HAKAN TEMELTAŞ

  3. Ç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

    Doktora

    Türkçe

    Türkçe

    1990

    Matematikİstanbul Teknik Üniversitesi

    DOÇ.DR. AZİZ BENER

  4. 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

    Türkçe

    2015

    Mimarlıkİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    DOÇ. DR. YÜKSEL DEMİR

  5. Refined geometric transition and local P2

    Rafine geometrik geçiş ve lokal P2

    BİLAL ÇARK

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Fizik ve Fizik MühendisliğiBoğaziçi Üniversitesi

    Fizik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ CAN KOZÇAZ

    PROF. OSMAN TEOMAN TURGUT

    DOÇ. AYBİKE ÖZER