TL;DR
This paper introduces a novel semidefinite programming (SDP) relaxation method to efficiently compute lower bounds for a class of fractional semi-infinite polynomial programming problems involving SOS-convex polynomials. This new approach complements existing methods by providing convergent lower bounds and enabling the extraction of approximate solutions, which is crucial for tackling complex optimization challenges.
What Problem Does This Paper Address?
The paper tackles the challenge of solving fractional semi-infinite polynomial programming (FSIPP) problems, which are notoriously difficult due to their infinite number of constraints and the complexity of the objective function (a ratio of polynomials). Specifically, the authors focus on FSIPP problems where the objective functions and constraints involve SOS-convex polynomials. While previous work established methods for obtaining upper bounds on the optimal solution using SDP relaxations, there was a need for methods that could reliably compute lower bounds. This is essential for establishing convergence and for practical applications where a tight range for the optimal solution is required. The problem can be formulated as:
$$ \begin{aligned} r^* := \min_{x \in \mathbb{R}^m} \frac{f(x)}{g(x)} \\ \text{s.t. } & \phi_i(x) \leq 0, \dots, \phi_s(x) \leq 0, \\ & p(x, y) \leq 0, \forall y \in Y \subset \mathbb{R}^n \end{aligned} $$
where $f, g, \phi_i$ are polynomials in $x$, and $p$ is a polynomial in $x$ and $y$. The set $Y$ is a compact set, and the functions $f, -g, \phi_i$, and $p(\cdot, y)$ are assumed to be SOS-convex.
Methods
The core contribution is a new SDP relaxation method that leverages Lasserre's measure-based representation of nonnegative polynomials. The authors build upon a previously established conic reformulation of the FSIPP problem. Instead of using quadratic modules (which yield upper bounds), they employ outer approximations of the set of polynomials that are nonnegative over $Y$, denoted as $P_k(Y)$.
The key steps involve:
- Conic Reformulation: The original FSIPP is reformulated into a conic optimization problem.
- Outer Approximations: The set $P(Y)$ (polynomials nonnegative on $Y$) is approximated by a sequence of tractable sets $P_k(Y)$.
- SDP Relaxation: The conic reformulation is combined with these outer approximations $P_k(Y)$ to construct a hierarchy of SDP problems, denoted as $(P_k)$ and $(D_k)$ (primal and dual forms).
- Lower Bounds: The dual SDP problems $(D_k)$ provide convergent lower bounds for the optimal value $r^*$.
- Outer SDr Approximations: The SDP relaxations also allow for the construction of a convergent sequence of outer semidefinite representation (SDr) approximations of the feasible set $K$.
The paper also explores alternative relaxations using diagonally dominant sum-of-squares (dsos) and scaled diagonally dominant sum-of-squares (sdsos) structures to potentially reduce computational complexity for large-scale problems.
Datasets
Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on constructed problems.
Key Insights and Ideas
- Bridging the Gap for Lower Bounds: The paper successfully extends existing SDP relaxation techniques to compute lower bounds for FSIPP problems, complementing previous work that focused on upper bounds. This is crucial for establishing convergence and bounding the optimal solution.
- Lasserre's Measure-Based Approach: The novel application of Lasserre's measure-based representation of nonnegative polynomials is key to deriving these lower bounds and outer approximations.
- Outer SDr Approximations of Feasible Sets: The method provides a systematic way to construct convergent outer approximations of the feasible set $K$, which is defined by infinitely many polynomial inequalities. This is valuable for understanding and characterizing the solution space.
- Trade-off between Accuracy and Computation: The exploration of dsos and sdsos relaxations highlights a practical trade-off: these approximations can significantly reduce computation time for large problems, albeit with potentially less accurate lower bounds compared to the full SOS relaxations.
Key Results
- The paper establishes a hierarchy of SDP relaxations $(P_k)$ and $(D_k)$ that yield convergent lower bounds $r_k^{\text{dual}}$ for the optimal value $r^*$.
- The authors prove that $\lim_{k \to \infty} r_k^{\text{dual}} = r^*$.
- They demonstrate that approximate minimizers of the FSIPP can be extracted from the solutions of the SDP relaxations.
- A convergent sequence of outer SDr approximations $A_k$ for the feasible set $K$ is constructed, with $\lim_{k \to \infty} A_k = K$.
- Numerical experiments on four example problems show that the lower bounds converge to the true optimal values as the relaxation order $k$ increases. The computational time for the SDP relaxations is also reported, demonstrating their tractability for moderate problem sizes.
Limitations and Future Work
- Computational Complexity: While the method provides convergent bounds, the computational cost of solving the SDP relaxations can still be significant, especially for high-order relaxations or problems with many variables. The paper notes that the size of the semidefinite matrix grows rapidly with the order $k$.
- Convergence Rate: The paper analyzes the convergence rate of the lower bounds and outer approximations, showing it is typically logarithmic in $k$. While this is theoretically sound, practical acceleration techniques could be explored.
- Future Work: The authors suggest applying acceleration techniques (from [26, 29, 30]) to improve the convergence rate of their new SDP method. They also propose investigating the scalability of the dsos and sdsos alternatives for larger problems. The paper also mentions that for certain cases of $Y$, the convergence rate can be improved.
Summary updated