Solver compatibility starts with the algebraic representation
Task offloading across space, air, and ground tiers produces products between assignment, computing, and communication variables. These cubic couplings lead to non-convex signomial or polynomial programs. This preprint focuses on a practical obstacle that appears after the mathematical model is written: a useful approximation may still be unsuitable for an embedded code generator.
Sequential geometric programming can approximate the offloading problem through exponential-cone representations. The authors point out that this exceeds the second-order-cone programming ceiling of tools such as CVXPYgen. In other words, the formulation can be numerically tractable on a general solver while remaining difficult to turn into compact deployable solver code.
Exact structure opens an embedded solver path
The alternative is an exact difference-of-convex representation of the multi-tier product. The paper uses quantifier elimination to certify that representation over the reals, then applies the convex–concave procedure. Each iteration becomes a second-order-cone program, removing the structural mismatch with an SOCP-oriented generation pipeline. “Exact” here describes the algebraic decomposition, not a claim that the iterative convex–concave procedure always returns the global optimum.
The public abstract compares sequential geometric programming and the convex–concave procedure with the BARON global solver. Both approaches reach near-global solutions in the reported experiments. The convex–concave procedure reduces average solution time from 0.1012 seconds to 0.0113 seconds, an 8.9-fold speedup relative to the stated sequential-geometric-programming implementation. The result is specific to the evaluated instances and solver setup; it should not be treated as a universal speed ratio.
The broader lesson is valuable for edge optimization. Deployment constraints can dictate which mathematical representations are useful. By exposing an exact structure whose iterative subproblems fit a restricted cone family, an optimization method can move closer to generated embedded code without pretending the original non-convex problem disappeared.
Research notes
Exact DC Representation of Multi-Tier Offloading Product in SAGINs via Quantifier Elimination
- Authors: Minh-Tuong Nguyen, Vo Phi Son, Dinh Thai Hoang
- Public record: arXiv
- What is established: Quantifier elimination certifies an exact difference-of-convex representation, and the convex–concave procedure yields second-order-cone subproblems compatible with a narrower embedded-solver path.
- Read with care: The reported 8.9-fold speedup is an average over the evaluated setup, and exact decomposition does not mean the iterative procedure is a global solver.