China
Africa
Explore chapters and articles related to this topic
Computational Complexity
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
NP-complete problems are not the same as co-NP-complete problems, though both are NP-hard. If you are lucky, you can solve an NP-complete problem quickly by guessing the answer, and verifying quickly that the answer is correct. For example, to solve the NP-complete IP feasibility problem just defined, you could luckily guess a feasible vector v, and quickly verify that Av≤b, and that v is integer.
Optimality conditions for linear copositive programming problems with isolated immobile indices
Published in Optimization, 2020
O. I. Kostyukova, T. V. Tchemisova
Copositive models arise in quadratic programming (QP) with linear and binary constraints [8,9], fractional QP [3,10], Graph Theory and Combinatorics [2,11], among others. The diversity of copositive formulations in different domains of optimization (continuous and discrete, deterministic and stochastic, robust optimization with uncertain objective and others) is described in [9,12]. According to Dür [9], CP is ‘a powerful modeling tool which interlinks the quadratic and binary worlds’. Being formally very similar to that of SDP, the copositive programmes are NP-hard since testing copositivity of matrices is co-NP-complete [13]. Different algorithms for copositivity detection are described, for example, in [12,14–16]. A clustered bibliography on copositive optimization can be found in [17].
Optimally robust H∞ polynomial fuzzy controller design using quantum-inspired evolutionary algorithm
Published in International Journal of Systems Science, 2018
Gwo-Ruey Yu, Yu-Chia Huang, Chih-Yung Cheng
Lemma 3.1 presents the definition of copositivity. However, checking the copositivity of the matrix is a co-NP problem. To reduce the difficulty, a relaxed approach is utilized to guarantee the copositivity of the matrix, which is described in Lemma 3.2. Then, Lemma 3.2 and Lemma 3.3 are used to derive the relaxed SOS-based optimally robust H∞ stability conditions, which are stated in Theorem 3.2.
Tolerances, robustness and parametrization of matrix properties related to optimization problems
Published in Optimization, 2018
The problem of checking whether a given matrix is a P-matrix is known to be co-NP-hard [9,27]. There are, however, efficiently recognizable subclasses such as positive definite matrices (discussed in Section 3), M-matrices (Section 5), H-matrices with positive diagonal entries (Section 6) or totally positive matrices (Section 7).