Learning to relax nonconvex quadratically constrainedquadratic programs
Dışbükey olmayan kuadratik kısıtlı kuadratik programlarıgevşetmeyi öğrenmek
- Tez No: 898289
- Danışmanlar: DOÇ. BURAK KOCUK
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 79
Özet
Kuadratik kısıtlı kuadratik programlar (QCQP), yöneylem araştırması, makine öğrenimi, güç sistemleri ve portföy optimizasyonu gibi çeşitli alanlarda sıkça karşımıza çıkar. Bu dışbükey olmayan problemlerin çözülmesi, NP-zor doğaları nedeniyle oldukça zordur. Geleneksel yaklaşımlar ya Yarı Tanımlı Programlama (SDP) ya da Doğrusal Programlama (LP) gevşetmeleri kullanır; her biri belirli problem türleri için güçlü yönler sergiler ancak çeşitli örnekler arasında kapsamlı bir anlayıştan yoksundur. Bu çalışmada, dışbükey olmayan QCQP'ler için problem örneğinin yapısını göz önünde bulundurarak SDP veya LP tabanlı yaklaşımlardan hangisinin daha başarılı olacağını tahmin eden \textit{yapıya duyarlı} bir gevşetme seçim yöntemi üretmeyi amaçlıyoruz. QCQP örneklerindeki veri matrislerinin negatif özdeğerlerinin sayısı, özdeğerlerinin büyüklükleri, bu matrislerin seyreklik örüntüsü gibi bir takım özniteliklerini inceleyerek yapısal özelliklerini ortaya çıkarıyoruz. Araştırmamız, QCQP örnekleri oluşturmayı, keşifsel veri analizleri yapmayı ve bu örnekleri SDP-lehine veya LP-lehine olarak sınıflandırmak için makine öğrenimi tekniklerini uygulamayı içerir. Bu tezin katkıları arasında, yeni QCQP örnekleri için SDP veya LP gevşetmesinin daha güçlü bir sınır sağlayacağını doğru bir şekilde tahmin eden makine öğrenimi modellerinin geliştirilmesi bulunmaktadır. Bu modeller, veri matrislerinin spektral özellikleri ve seyreklik örüntülerinden türetilen özniteliklerle eğitilmiştir. Bu tahmin yeteneği, en uygun gevşetme yönteminin seçimini yönlendirerek dışbükey olmayan QCQP'lerin çözüm verimliliğini artırmaktadır.
Özet (Çeviri)
Quadratically constrained quadratic programs (QCQPs) are commonly encountered in diverse disciplines like operations research, machine learning, power systems, and portfolio optimization. The solution of these non-convex problems is difficult since they are characterized by their NP-hard nature. Conventional methods employ either Semidefinite Programming (SDP) or Linear Programming (LP) relaxations; each of these methods is highly effective for certain subsets of problems and exhibits poor performance for others. However, there is a lack of comprehensive understanding. This thesis seeks to create a relaxation selection procedure for QCQPs that takes into account the structure of the problem. It intends to determine if an SDP- or LP-based strategy is more beneficial based on the instance structure. We explore the spectral properties and sparsity patterns of data matrices to unravel the structural properties of a QCQP instance. Our study is based on the generation of QCQP samples, along with an exploratory analysis of the dataset, and applying machine learning to classify the obtained instances by the most favorable relaxation technique. The main contribution of this work is to develop machine learning models that can accurately predict ex-ante whether an SDP or LP relaxation will yield a tighter bound on new QCQP instances. These models are trained on features created from the spectral properties and sparsity patterns of the data matrices. This predictive capability increases the efficiency of solving non-convex QCQPs by guiding the selection of the most suitable relaxation method.
Benzer Tezler
- İhtiyaç odaklı Kur'an kursu öğrencilerinin tercih sebepleri ve beklentileri
Reasons for preference and expectations of need-based Qur'an course students
FATMA CANDEMİR
Yüksek Lisans
Türkçe
2023
DinHitit ÜniversitesiFelsefe ve Din Bilimleri Ana Bilim Dalı
DOÇ. DR. AHMET KOÇ
- A heuristic temporal difference approach with adaptive grid discretization
Adaptif ızgara ayrıklaştırması ile sezgisel zamansal fark yaklaşımı
OZAN BORA FİKİR
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
PROF. DR. FARUK POLAT
- Toplu dil öğrenme yöntemi ve Türkiye'de uygulanabilirliği
Başlık çevirisi yok
AYBARS ERÖZDEN
Yüksek Lisans
Türkçe
1986
Eğitim ve Öğretimİstanbul ÜniversitesiYabancı Diller Eğitimi Ana Bilim Dalı
DR. ÖMER DEMİRCAN
- A new approach to satellite communication: Harnessing the power of reconfigurable intelligent surfaces
Uydu iletisimine yeni bir yaklaşım: Yeniden yapılandırılabı̇lı̇r akıllı yüzeylerden faydalanma
KÜRŞAT TEKBIYIK
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNEŞ ZEYNEP KARABULUT KURT
- Sanat temelli sosyal bilgiler öğretimi: Bir eylem araştırması
Art-based social studies teaching: An action research
CANAN AKYOL
Doktora
Türkçe
2022
Eğitim ve ÖğretimGazi ÜniversitesiTürkçe ve Sosyal Bilimler Eğitimi Ana Bilim Dalı
PROF. DR. CENGİZ DÖNMEZ