Çeşitli konveks olmayan problemlerin kopozitif formulasyonlarının dıştan yaklaşımları üzerine

Copositive optimization is linear optimization over the convex cone of copositive or completely positive matrices. "The term copositive programming" was first introduced in 2000. In 2009, Burer showed that mixed binary quadratic optimization problems (MBQP), which comprises a rather large class of nonconvex and combinatorial problems, can be equivalently reformulated as a copositive optimization problem. This seminal work has greatly increased the interest in copositive optimization. It is not surprising, however, that since many combinatorial and nonconvex optimization problems can be reformulated as a copositive optimization problem, copositive programs are also NP-hard in general. The difficulty in the reformulation is entirely due to the conic constraint. For this reason, many researchers have proposed outer approximation hierarchies to the intractable completely positive cone. These approximation hierarchies are composed of a sequence of tractable cones that yield increasingly better approximations of the completely positive cone and are exact in the limit. By replacing the intractable cone by outer approximations in the copositive formulation of nonconvex and NP-hard minimization (resp. maximization) problems, a sequence of increasingly tighter lower (upper) bounds can be obtained for the original problem. This provides opportunities to obtain near-optimal solutions and improve the effectiveness of the algorithms for solving the original problem. In this thesis, we study outer approximations of the copositive reformulations of three classes of nonconvex and NP-hard optimization problems. We first study the class of mixed binary programs (MBPs). We compare the lower bounds arising from outer polyhedral approximations to the lower bound provided by the linear programming (LP) relaxation and establish that the lower bounds due to outer approximations are at least as good as that of LP relaxation. We establish various necessary or sufficient conditions under which the lower bound arising from the outer approximations matches that from the LP relaxation. Our results illustrate the weaknesses of polyhedral approximations. On the other hand, we show that the non-polyhedral doubly nonnegative (DNN) approximations, in general, yield tighter lower bounds. Secondly, we focus on the specific 0-1 knapsack problem (KP) in the class of MBPs. We study two different copositive formulations of the knapsack and compare the upper bounds arising from outer polyhedral approximations to the upper bound provided by the LP relaxation of (KP). We prove that upper bounds obtained from outer polyhedral approximations actually coincide with the upper bound provided by the LP relaxation until at least a certain and fairly large level of the hierarchy. On the other hand, we establish that if the LP relaxation has a non-integer unique solution, then the DNN relaxation gives a strictly better upper bound than the LP relaxation. Finally, we consider the standard quadratic programs (StQP) and investigate the instances of (StQP) for which the DNN relaxation is exact. We establish a complete algebraic characterization of the (StQP) instances that admit an exact DNN relaxation. We explicitly identify three different subsets of such (StQP) instances. Furthermore, we propose a recipe for constructing instances of (StQP) with an exact DNN relaxation. In summary, our results reveal that outer polyhedral approximations, in general, yield weak bounds for (MBP) and for the specific 0-1 knapsack problem, whereas doubly nonnegative relaxations usually give rise to tighter lower bounds.