Bazı ikinci dereceden eniyileme problemlerinin kopozitif formulasyonlarının doğrusal yaklaşımlarının incelenmesi

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.