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ı: Belirtilmemiş.
Ö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
- 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
- Görsel sanatlar öğretmen adaylarının duygusal zekâ düzeylerinin öğrenme stillerine ve akademik başarılarına etkisi
The effect of visual arts teacher candidates' emotional intelligence levels on their learning styles and academic achievement
ECE KORKMAZ
Yüksek Lisans
Türkçe
2025
Eğitim ve ÖğretimTrabzon ÜniversitesiGüzel Sanatlar Eğitimi Ana Bilim Dalı
DOÇ. DR. SEDA LİMAN TURAN
- Makine öğrenmesi yöntemleri kullanılarak akıllı telefon tabanlı stres tespit sistemi geliştirilmesi
Developing smartphone based stress detection system using machine learning methods
ENSAR ARİF SAĞBAŞ
Doktora
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA SERDAR KORUKOĞLU
DOÇ. DR. SERKAN BALLI
- Evde eğitime ilişkin öğretmen, öğrenci ve veli görüşleri
Opinions of teachers, students and parents relating to home education
EMİNE IŞIK
Yüksek Lisans
Türkçe
2019
Eğitim ve ÖğretimFırat ÜniversitesiTemel Eğitim Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BİRSEN SERHATLIOĞLU
- Özel öğrenme güçlüğü yaşayan bireylerin görsel algı becerilerinin geliştirilmesinde görsel sanatlar eğitiminin önemi
The importance of visual arts education in developing the visual perceptive skills of individuals with specific learning disabilities
SÜMEYYE ÖZTÜRK
Yüksek Lisans
Türkçe
2024
Eğitim ve ÖğretimGazi ÜniversitesiGüzel Sanatlar Eğitimi Ana Bilim Dalı
DOÇ. GONCA HÜLYA YAYAN