On polyhedral approximations of copositive formulations of certain quadratic optimization problems

Kopozitif eniyileme, doğrusal bir amaç fonksiyonunun doğrusal eşitlik kısıtları altında kopozitif veya tamamen pozitif matrisler konisi üzerinde enküçükleme ya da enbüyükleme problemidir. Kopozitif eniyileme problemleri, "kopozitif programlama" terimi 2000 yılında standart ikinci dereceden eniyileme problemleri bağlamında ilk kez kullanıldığından beri araştırmacılar için ilgi çekici bir alan olmuştur. Daha sonra, Burer son derece önemli bir çalışmasında karışık-ikili ikinci dereceden eniyileme problemlerinin tamamen pozitif matrisler konisi üzerine konik eniyileme problemi olarak formule edilebileceğini göstermiştir. Kopozitif eniyileme problem sınıfının araştırmacıların ilgisini çekmesinin nedeni NP-zor problemler için yeni bir bakış açısı sağlamasıdır. Beklenildiği üzere, kopozitif formulasyonlar da hesaplama açısından zorludur. Bu yüzden, tamamen pozitif matrisler konisine, her biri yaklaşıklama doğruluğu giderek artan ve limitte asıl koniye yakınsayan iki çok yüzlü koni dizisi ile içten ve dıştan yaklaşılabilir. Bu şekilde yakınsayan koni dizisi, yaklaşıklama hiyerarşisi olarak adlandırılır. Bu yüzden, kopozitif eniyileme problemindeki zorlu konik kısıtının içten ve dıştan yaklaşıklama hiyerarşisi ile değiştirilmesi asıl problemin eniyi değeri için gittikçe sıkılaşan alt ve üst sınır dizileri vermektedir. Bu tezde içten ve dıştan çok yüzlü yaklaşımlarının sağladığı alt ve üst sınırlar ele alınmıştır. Bu tezde, iki farklı ikinci dereceden eniyileme problem sınıarının kopozitif formulasyonları incelenmiştir. İlk olarak standart ikinci dereceden eniyileme problemleri (StQP) ele alınmıştır. Bu problem sınıfı için alt ve üst sınırların sonlu yakınsama koşulları ve bu sınırların yakınsamadığı durumlar sunulmuştur. Alt ve/veya üst sınırın sonlu bir seviyede en iyi değere eşitlendiği ve alt ve/veya üst sınırın en iyi değere ancak limitte yakınsadığı problemlerin bulunduğu kümelerin bütünlüklü tanımları verilmiştir. Ayrıca, bu kümelerin bazı geometrik ve topolojik özellikleri de sunulmuştur. İkinci olarak, kutu kısıtlı ikinci dereceden problemler (BoxQP) çalışılmıştır. Bu problem sınıfı için detaylı olarak iki farklı kopozitif yeniden formulasyon incelenmiştir. (BoxQP) probleminin eniyi değeri için bu iki farklı formulasyonun çok yüzlü koniler kullanılarak elde edilen alt ve üst sınırlar dizisi çalışılmıştır. Bu iki farklı formulasyonun içten ve dıştan çok yüzlü yaklaşımları karşılaştırılmıştır. İçten çok yüzlü yaklaşımların olurluluk koşulları verilmiştir. Ayrıca, dıştan çok yüzlü yaklaşımların en iyi değerlerinin sınırlı veya sınırsız olduğu durumlar ortaya konulmuştur. İncelediğimiz konular arasında her iki yaklaşım için hata payları da yer almaktadır. Bu sonuçlar, çok yüzlü yaklaşıklama hiyerarşilerinin standart ikinci dereceden enyileme problemleri için teoride yararlı olabileceğini göstermiştir. Bunun yanında, bu yaklaşıklama hiyerarşileri kutu kısıtlı ikinci dereceden eniyileme problemleri için göreceli olarak daha zayıf alt ve üst sınırlar vermektedir.