کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4602731 1336936 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithmic copositivity detection by simplicial partition
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Algorithmic copositivity detection by simplicial partition
چکیده انگلیسی

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 428, Issue 7, 1 April 2008, Pages 1511-1523