On outer approximations of copositive formulations of various nonconvex optimization problems

Kopozitif eniyileme, dışbükey kopozitif veya tamamen pozitif koni üzerinde tanımlanan doğrusal eniyileme problemidir. "Kopozitif programlama" terimi ilk defa 2000 yılında ortaya atılmıştır. Daha sonra, Burer 2009 yılında kombinatoryal ve konveks olmayan problemlerin olduça geniş bir sınıfı olan karma ikili ikinci dereceden eniyileme problemlerinin bir kopozitif eniyileme problemi olarak formule edilebileceğini göstermiştir. Bu önemli çalışma, kopozitif programlama problemlerine olan ilgiyi önemli ölçüde arttırmıştır. Ne var ki, kombinatoryal ve konveks olmayan birçok problemin bir kopozitif eniyileme problemine denk olması sebebiyle kopozitif formulasyonların da genel itibarıyla NP-zor olması şaşırtıcı değildir. Buradaki zorluk tam olarak konik kısıttan kaynaklanmaktadır. Bu sebeple birçok araştırmacı zorlu olan tamamen pozitif koniye kolay konilerden oluşan dıştan yaklaşıklama hiyerarşileri önermiştir. Bu yaklaşıklama hiyerarşilerinin temel prensibi, hiyerarşi seviyesi arttıkça tamamen pozitif koniyi daha iyi yaklaşıklayan ve limitte ona eşit olan bir koni dizisi üretmeye dayanmaktadır. Konveks olmayan ve NP-zor birçok enküçükleme (enbüyükleme) probleminin kopozitif formulasyonundaki zorlu konik kısıt dıştan yaklaşımlar ile değiştirilerek problem için gittikçe sıkılaşan alt (üst) sınırlar elde edilebilmektedir. Bu durum, asıl problem için en iyi çözüme yakın çözümler elde etmek ve problemi çözmeye çalışan algoritmalar geliştirmek açısından fırsatlar sunmaktadır. Bu tezde, üç farklı konveks olmayan ve NP-zor problem sınıfının kopozitif formulasyonlarının dış yaklaşıklamaları incelenmiştir. Öncelikle karma ikili tamsayı problemleri (MBP) ele alınmıştır. Bu problemde dış yaklaşımlardan elde edilen alt sınırlar, problemin doğrusal programlama (LP) gevşetmesinden elde edilen alt sınır ile karşılaştırılmış ve bu alt sınırların en az LP gevşetmeden elde edilen alt sınır kadar iyi olacağı ortaya konmuştur. Bu sonuç olumlu gözükmekle birlikte, çok yüzlü dış yaklaşımlardan elde edilen alt sınırların belli bir seviyeye kadar iyileşmeyeceğini gösteren yeterli ya da gerekli koşullar ortaya konmuştur. Diğer yandan iki kat negatif olmayan (DNN) gevşetmelerin daha iyi alt sınırlar verdiğine yönelik bulgular elde edilmiştir. İkinci olarak (MBP) sınıfındaki özel bir problem olan 0-1 sırt çantası problemi (KP) incelenmiştir. Sırt çantası probleminin iki farklı kopozitif formulasyonu çalışılmış ve çok yüzlü dış yaklaşımlardan elde edilen üst sınırlar LP gevşetmeden elde edilen üst sınırlar ile kıyaslanmıştır. Çok yüzlü dış yaklaşımlardan elde edilen üst sınırların LP gevşetmeden elde edilen üst sınır ile en azından belirli ve oldukça yüksek bir seviyeye kadar aynı alt sınırı vereceği kanıtlanmıştır. Diğer yandan, problemin LP gevşetmesinin tek ve tam sayı olmayan bir en iyi çözümü olması durumunda, DNN gevşetmenin LP gevşetmeden kesinlikle daha iyi alt sınır verdiği ortaya konmuştur. Son olarak standart ikinci dereceden eniyileme probleminin (StQP) DNN gevşetmesinin tam (exact) olduğu örnekler incelenmiştir. DNN gevşetmenin tam olduğu örnekler için cebirsel bir karakterizasyon verilmiştir. DNN gevşetmenin tam olduğu örneklerin kümesi için üç farklı alt küme belirlenmiştir. Bu alt kümelerin her birindeki üyelik problemi polinom zamanda çözülebilmektedir. Ek olarak, DNN gevşetmenin tam olduğu (StQP) örneklerini inşa edebilmek için bir reçete sunulmaktadır. Özetle, sonuçlarımız genel itibariyle çok yüzlü yaklaşımların (MBP) problemi ve 0-1 sırt çantası problemi için zayıf alt sınırlar verdiğine işaret etmekle birlikte, iki kat negatif olmayan gevşetmenin daha sıkı alt sınırlar verdiğine işaret etmektedir.