Standard bi-quadratic optimization problems and unconstrained polynomial reformulations

A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, in order to get rid of the sign constraints. We study the first- and second-order optimality conditions of the original StBQP and the reformulated bi-quartic problem over the product of two Euclidean spheres. Furthermore, we discuss the one-to-one correspondence between the global/local solutions of StBQP and the global/local solutions of the reformulation. We introduce a continuously differentiable penalty function. Based upon this, the original problem is converted into the problem of locating an unconstrained global minimizer of a (specially structured) polynomial of degree eight.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.      

Buchbesprechungen

Ohne Zusammenfassung

---

Book reviews

     

A dynamical characterization of evolutionarily stable states

Evolutionary stability, the central solution concept in evolutionary game theory, is closely related to local asymptotic stability in a certain nonlinear dynamical system operating on the state space, the so-called "replicator dynamics". However, a purely dynamical characterization of evolutionary stability is not available in an elementary manner. This characterization can be achieved by investigating so-called "derived games" which consist of mixed strategies corresponding to successful states in the original game. Using well-known facts, several characterization results are obtained within this context. These also may shed light on the extremality properties of evolutionary stability.     

Using copositivity for global optimality criteria in concave quadratic programming problems

In this note we specify a necessary and sufficient condition for global optimality in concave quadratic minimization problems. Using this condition, it follows that, from the perspective of worst-case complexity of concave quadratic problems, the difference between local and global optimality conditions is not as large as in general. As an essential ingredient, we here use the-subdifferential calculus via an approach of Hiriart-Urruty and Lemarechal (1990).     

Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches

Computational Management Science - By now, many copositive reformulations of mixed-binary QPs have been discussed, triggered by Burer’s seminal characterization from 2009. In conic...     

Building a completely positive factorization

A symmetric matrix of order n is called completely positive if it has a symmetric factorization by means of a rectangular matrix with n columns and no negative entries (a so-called cp factorization), i.e., if it can be interpreted as a Gram matrix of n directions in the positive orthant of another Euclidean space of possibly different dimension. Finding this factor therefore amounts to angle packing and finding an appropriate embedding dimension. Neither the embedding dimension nor the directions may be unique, and so many cp factorizations of the same given matrix may coexist. Using a bordering approach, and building upon an already known cp factorization of a principal block, we establish sufficient conditions under which we can extend this cp factorization to the full matrix. Simulations show that the approach is promising also in higher dimensions.

     

Switching currents limited by single phase slips in one-dimensional superconducting Al nanowires

An aluminum nanowire switches from superconducting to normal as the current is increased in an upsweep. The switching current (I(s)) averaged over upsweeps approximately follows the depairing critical current (I(c)) but falls below it. Fluctuations in I(s) exhibit three distinct regions of behaviors and are nonmonotonic in temperature: saturation well below the critical temperature T(c), an increase as T(2/3) at intermediate temperatures, and a rapid decrease close to T(c). Heat dissipation analysis indicates that a single phase slip is able to trigger switching at low and intermediate temperatures, whereby the T(2/3) dependence arises from the thermal activation of a phase slip, while saturation at low temperatures provides striking evidence that the phase slips by macroscopic quantum tunneling.     

Detecting all evolutionarily stable strategies

In evolutionary game theory, the central solution concept is the evolutionarily stable state, which also can be interpreted as an evolutionarily stable population strategy (ESS). As such, this notion is a refinement of the Nash equilibrium concept in that it requires an additional stability property. In the present paper, an algorithm for detectingall ESSs of a given evolutionary game consisting of pairwise conflicts is presented which both is efficient and complete, since it involves a procedure avoiding the search for unstable equilibria to a considerable extent, and also has a finite, exact routine to check evolutionary stability of a given equilibrium. The article also contains the generalization of these results to the playing-the-field setting, where the payoff is nonlinear.     

Unconstrained formulation of standard quadratic optimization problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. We propose unconstrained reformulations of StQPs, by using different approaches. We test our method on clique problems from the DIMACS challenge.