Abstract A real symmetric matrix A is copositive if $$x^\top Ax\ge 0$$ x ⊤ A x ≥ 0 for all $$x\ge 0$$ x ≥ 0 . As A is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015), are based upon the creation of increasingly fine simplicial partitions of simplices, testing for copositivity on each. We present a variant that decomposes a simplex $$\bigtriangleup $$ △ , say with n vertices, into a simplex $$\bigtriangleup _1$$ △ 1 and a polyhedron $$\varOmega _1$$ Ω 1 ; and then partitions $$\varOmega _1$$ Ω 1 into a set of at most $$(n-1)$$ ( n - 1 ) simplices. We show that if A is copositive on $$\varOmega _1$$ Ω 1 then A is copositive on $$\bigtriangleup _1$$ △ 1 , allowing us to remove $$\bigtriangleup _1$$ △ 1 from further consideration. Numerical results from examples that arise from the maximum clique problem show a significant reduction in the time needed to establish copositivity of matrices.

In representation learning, sparse representation is a parsimonious principle that a sample can be approximated by a sparse superposition of dictionary atoms. Sparse coding is the core of this technique. Since the dictionary is often redundant, the dictionary size can be very large. Many optimization methods have been proposed in the literature for sparse coding. However, the efficiency of the optimization for a tremendous number of dictionary atoms is still a bottleneck. In this paper, we propose to use decomposition method for large-scale sparse coding models. Our experimental results show that our method is very efficient.

We present a constraint analysis methodology for linear matrix inequality constraints. If the constraint set is found to be feasible, we search for a minimal representation; otherwise, we search for an irreducible infeasible system. The work is based on the solution of a set-covering problem where each row corresponds to a sample point and is determined by constraint satisfaction at the sampled point. Thus, an implementation requires a method to collect points in the ambient space and a constraint oracle. Much of this paper will be devoted to the development of a hit-and-run sampling methodology. Test results confirm that our approach not only provides information required for constraint analysis but will also, if the feasible region has a nonvoid interior, with probability one, find a feasible point.