Optimisation Problems Simplified with New Linear Approach

Researchers are tackling the complex challenges presented by max-min bilinear optimization, a foundational framework with applications spanning game theory, robust optimisation, and adversarial machine learning. Sarah Yini Gao, Xindong Tang, and Yancheng Yuan present a novel approach to solving this class of problems when variables are constrained to lie within the completely positive (CP) cone. Their work details a new semidefinite relaxation hierarchy, offering guaranteed tightness under specific conditions, and extends existing methods for distributionally robust optimisation and polynomial games. This advancement is significant because it provides a pathway to efficiently address NP-hard problems arising from completely positive programming, demonstrated through successful application to the cyclic Colonel Blotto game where the relaxation accurately determines mixed-strategy equilibria.

This method provides a powerful approach to finding guaranteed solutions where traditional methods often fail, with potential applications spanning finance and artificial intelligence. Researchers have demonstrated a way to reformulate problems centring on max-min bilinear programs, where one agent maximizes an outcome while an adversary minimizes it.

They demonstrated a way to reformulate these problems, specifically those involving “completely positive” variables, as a single, more manageable linear program operating over a combined “COP-CP” cone. This advancement addresses a significant computational challenge, as determining whether a solution belongs to the copositive cone is known to be computationally difficult.

The researchers introduce a hierarchy of semidefinite relaxations, a technique for approximating solutions to complex problems, built upon moment and sum-of-squares representations of the underlying cones. Crucially, they incorporate “flat truncation conditions” to rigorously prove when these approximations become exact, guaranteeing the reliability of the solutions obtained.

This framework builds upon and extends existing approaches used in distributionally robust optimisation and polynomial games, offering a more general and powerful tool for tackling these types of problems. The team validated their method by applying it to the cyclic Colonel Blotto game, a strategic allocation contest representing an extension of a classic problem in game theory.

Across multiple instances, the semidefinite relaxation satisfied the established flat-truncation conditions, successfully determining the precise mixed-strategy equilibrium. This achievement demonstrates the practical effectiveness of the new approach and its potential to unlock solutions for previously intractable problems. The ability to accurately model and solve max-min bilinear programs with completely positive constraints opens avenues for advancements in areas requiring robust decision-making under uncertainty, including adversarial machine learning and resource allocation. The framework’s theoretical guarantees and demonstrated performance suggest a promising path towards more efficient and reliable optimisation algorithms.

Moment and sum-of-squares relaxations for intractable bilinear optimisation

A hierarchy of semidefinite relaxations, grounded in moment and sum-of-squares representations, forms the core of this work’s methodological approach. The study addresses challenges inherent in optimising over the completely positive (CP) cone, essential for modelling mixed-binary quadratic problems. The research establishes an equivalence between the original max-min bilinear optimisation problem and a single-stage linear program defined over the Cartesian product of the copositive (COP) and CP cones, referred to as the COP-CP program.

Membership testing within the COP cone is known to be computationally difficult, rendering the COP-CP program generally NP-hard. To circumvent this intractability, the researchers developed a novel relaxation technique leveraging moment and sum-of-squares (SOS) methods, transforming the original non-convex problem into a semidefinite program (SDP) that can be solved more efficiently.

The key innovation lies in the application of ‘flat truncation conditions’ which rigorously certify the tightness of these relaxations, ensuring that the solution obtained from the SDP closely approximates the true optimal solution. This approach builds upon existing methods for CP and COP approximations, but crucially avoids their limitations by employing a unified framework.

Previous techniques often provided either inner or outer approximations of the respective cones, hindering the establishment of clear bounds. By combining moment and SOS representations with flat truncation, the study guarantees convergence of the relaxation hierarchy under relatively mild conditions. The efficacy of this methodology is demonstrated through its application to the Cyclic Colonel Blotto game, a complex allocation contest with known computational challenges, solving multiple instances exactly and verifying the effectiveness of the flat truncation conditions.

Semidefinite relaxation solves cyclic Colonel Blotto and reformulates max-min bilinear programs

Across multiple instances of the cyclic Colonel Blotto game, the semidefinite relaxation met the flat-truncation conditions and successfully solved for the exact mixed-strategy equilibrium, indicating a precise alignment between the relaxation and the true solution. The framework extends existing approaches for distributionally robust optimisation and polynomial games, demonstrating its versatility and broad applicability.

The research establishes that max-min bilinear programs with variables constrained to the completely positive (CP) cone can be reformulated as a single-stage linear program over the combined COP-CP cone. This reformulation, while theoretically elegant, inherits the NP-hardness associated with membership testing in the copositive (COP) cone. To overcome this computational challenge, a hierarchy of semidefinite relaxations was constructed, leveraging moment and sum-of-squares representations of both the COP and CP cones.

These relaxations provide increasingly tighter approximations to the original non-convex problem, with tightness guaranteed under mild conditions, ensuring the reliability of the approximations. Specifically, the study demonstrates that truncated multi-sequences of degree d can be accurately represented, allowing for efficient computation of solutions.

A key component of this representation involves characterising the cone of degree 2 homogeneous truncated multi-sequences supported on the simplex, denoted as R[∆n]hom 2, with its dual cone, P[∆n]hom 2, representing quadratic forms that are nonnegative on the simplex. The sum-of-squares (SOS) approximation is used to approximate P[∆n]hom 2, defining a convex cone, IQ[∆n]2k, constructed from SOS polynomials and polynomial constraints specifying the standard simplex.

For any k belonging to the natural numbers, IQ[∆n]2k serves as an inner approximation to P[∆n]hom 2, meaning any polynomial within IQ[∆n]2k is guaranteed to be nonnegative on the simplex. Conversely, if a polynomial is strictly positive on the simplex, it will be contained within IQ[∆n]2k for sufficiently large k, establishing a strong connection between SOS relaxations and the accurate representation of nonnegative quadratic forms.

Reformulating bilinear optimisation via completely positive extensions and relaxation hierarchies

The pursuit of efficient optimisation algorithms has long been hampered by the curse of dimensionality, particularly when dealing with complex, real-world scenarios involving competing interests. This work offers a significant advance in tackling max-min bilinear optimisation by providing a way to reformulate them as a more manageable program. The innovation lies in extending existing techniques to the completely positive (CP) cone, allowing for a broader range of mixed-binary quadratic problems to be addressed.

What distinguishes this approach is not simply the mathematical reformulation itself, but the development of a hierarchy of relaxations designed to certify the tightness of the solution. This is crucial because directly solving these problems is often intractable. The successful application to the cyclic Colonel Blotto game demonstrates the potential for finding exact mixed-strategy equilibria where previous methods faltered.

However, the inherent NP-hardness of the reformulated program remains a considerable obstacle. The framework’s reliance on semidefinite relaxations introduces computational demands that scale rapidly with problem size. While the flat truncation conditions offer a means of verifying solution quality, they do not eliminate the need for substantial computational resources. Future work will likely focus on refining these relaxations, exploring alternative decomposition strategies, and developing more efficient algorithms for tackling the associated semidefinite programs, ultimately aiming to bridge the gap between theoretical elegance and practical applicability.