A new geometric duality and approximation algorithms for convex vector optimization problems

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.