Geri Dön

Learning to relax nonconvex quadratically constrainedquadratic programs

Dışbükey olmayan kuadratik kısıtlı kuadratik programlarıgevşetmeyi öğrenmek

  1. Tez No: 898289
  2. Yazar: MEBRURE BUKET ÖZEN
  3. Danışmanlar: DOÇ. BURAK KOCUK
  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: 2024
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    Türkçe

    2023

    DinHitit Üniversitesi

    Felsefe ve Din Bilimleri Ana Bilim Dalı

    DOÇ. DR. AHMET KOÇ

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

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    PROF. DR. FARUK POLAT

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

    Türkçe

    1986

    Eğitim ve Öğretimİstanbul Üniversitesi

    Yabancı Diller Eğitimi Ana Bilim Dalı

    DR. ÖMER DEMİRCAN

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

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. GÜNEŞ ZEYNEP KARABULUT KURT

  5. Sanat temelli sosyal bilgiler öğretimi: Bir eylem araştırması

    Art-based social studies teaching: An action research

    CANAN AKYOL

    Doktora

    Türkçe

    Türkçe

    2022

    Eğitim ve ÖğretimGazi Üniversitesi

    Türkçe ve Sosyal Bilimler Eğitimi Ana Bilim Dalı

    PROF. DR. CENGİZ DÖNMEZ