On Copositive Programming and Standard Quadratic Optimization Problems

A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF ^T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase.     

Global Escape Strategies for Maximizing Quadratic Forms over a Simplex

Consider the problem of maximizing a quadratic formover the standard simplex.Problems of this type occur, e.g., in the search for the maximum (weighted)clique in an undirected graph.In this paper, copositivity-based escape proceduresfrom inefficient local solutions are rephrased into lower-dimensionalsubproblems which are again of the same type. As a result, analgorithm is obtained which tries to exploit favourable data constellationsin a systematic way, and to avoid the worst-case behaviourof such NP-hard problems whenever possible. First results onfinding large cliques in DIMACS benchmark graphs are encouraging.     

A note on aspirations in non-transferable utility games

For an important class of non-transferable utility games it is shown by short proofs that the set of aspirations is not empty, and that aspirations are closely related to coalitionally rational payoff distributions.     

Novel superconducting semiconducting superlattices: dislocation-induced superconductivity?

Novel superconducting superlattices with transition temperature in the range 2.5-6.4 K consisting only of semiconducting materials are discovered. Among them there are multilayers, including a wide-gap semiconductor as one of the components. It is shown that superconductivity is connected with the interfaces between two semiconductors containing regular grids of the misfit dislocations. The possibility of the dislocation-induced superconductivity is discussed.     

Rounding on the standard simplex: regular grids for global optimization

Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all \(\ell ^p\) -norms for \(p\ge 1\) . We show that the minimal \(\ell ^p\) -distance to the regular grid on the standard simplex can exceed one, even for very fine mesh sizes in high dimensions. Furthermore, for \(p=1\) , the maximum minimal distance approaches the \(\ell ^1\) -diameter of the standard simplex. We also put our results into perspective with respect to the literature on approximating global optimization problems over the standard simplex by means of the regular grid.     

Quadratic factorization heuristics for copositive programming

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.