| Popis: |
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ınsonlu bir seviyede en iyi değere eşitlendiği ve alt ve/veya üst sınırın en iyi değere ancaklimitte 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. Copositive optimization is the minimization or maximization of a linear objective function subject to linear equality constraints over the cone of copositive or completely positive matrices. It has been an intriguing area for researchers since the term `copositive programming` was coined in 2000 in the context of standard quadratic optimization. Later, in the seminal work of Burer, it has been shown that mixed-binary quadratic optimization problems can be reformulated as a conic optimization problem over the convex cone of completely positive matrices.This class of optimization problems draws attention of researchers since it provides a new perspective on various NP-hard problems. As expected, copositive reformulations are also computationally intractable. Therefore, the completely positive cone can be approximated from the inside and from the outside by two sequences of nested polyhedral cones of increasing accuracy each of which converges to the original intractable cone in the limit. Such a sequence of approximating cones is called an approximation hierarchy. Therefore, replacing the intractable conic constraint in a copositive optimization problem by an inner and an outer approximation hierarchy yields two sequences of increasingly tighter upper and lower bounds on the optimal value of the original problems. We study the sequences of upper and lower bounds on the optimal value arising from these two hierarchies of inner and outer polyhedral approximations.We focus on two different classes of quadratic optimization problem that can be reformulated as copositive optimization problems. We first consider standard quadratic optimization problems (StQPs). For this class of problems, we focus on the issues of finite convergence of upper and lower bounds as well as convergence of these bounds only in the limit. We give complete algebraic descriptions of the sets of instances on which upper and lower bounds are exact at any given finite level of the hierarchy. We identify the structural properties of the sets of instances on which upper and lower bounds converge to the optimal value only in the limit. We present several geometric and topological properties of these sets.Second, we study box constrained quadratic optimization problems (BoxQPs). We consider two alternative copositive reformulations. We study the sequences of upper and lower bounds arising from the aforementioned polyhedral approximation hierarchies on the optimal value of a (BoxQP) for both of these formulations. We compare two formulations in terms of both inner and outer polyhedral approximations. We give a characterization of the feasibility of inner polyhedral approximation problems. We present conditions under which outer approximations have a finite or unbounded optimal value. Furthermore, we study error bounds for both approximation hierarchies.Our results reveal that polyhedral approximation hierarchies can be useful in theory for standard quadratic optimization problems. On the other hand, these hierarchies yield considerably weaker upper and lower bounds for box constrained quadratic optimization problems. 128 |
