Sum-Of-Rational-Functions Optimization

The sum-of-rational-functions optimization problem could be formulized as

\[\mathrm{inf}_{\mathbf{x}\in\mathbf{K}}\ \sum\_{i=1}^N\frac{p_i(\mathbf{x})}{q_i(\mathbf{x})},\]

where $p_i,q_i\in\mathbb{R}[\mathbf{x}]$ are polynomials and $\mathbf{K}$ is the basic semialgebraic set

\[\mathbf{K}\coloneqq\lbrace \mathbf{x}\in\mathbb{R}^n \mid g_i(\mathbf{x})\ge0, i=1,\ldots,m,\ h_j(\mathbf{x})=0, j=1,\ldots,\ell\rbrace,\]

for some polynomials $g_i,h_j\in\mathbb{R}[\mathbf{x}]$.

The following is a simple example.

@polyvar x y z
p = [x^2 + y^2 - y*z, y^2 + x^2*z, z^2 - x + y] # define the vector of denominators
q = [1 + 2x^2 + y^2 + z^2, 1 + x^2 + 2y^2 + z^2, 1 + x^2 + y^2 + 2z^2] # define the vector of numerator
g = [1 - x^2 - y^2 - z^2]
d = 2 # set the relaxation order
opt = SumOfRatios(p, q, g, [], [x;y;z], d, QUIET=true, SignSymmetry=true) # Without correlative sparsity
opt = SparseSumOfRatios(p, q, g, [], [x;y;z], d, QUIET=true, SignSymmetry=true) # With correlative sparsity

Keyword arguments

Argument	Description	Default value
SignSymmetry	Exploit sign symmetries	true
Groebnerbasis	Work in the quotient ring by computing a Gröbner basis	false

Methods

TSSOS.SumOfRatios — Function

optimum = SumOfRatios(p, q, g, h, x, d; QUIET=false, SignSymmetry=true, Groebnerbasis=false)

Minimizing the sum of ratios p1/q1 + ... + pN/qN on the set defined by g >= 0 and h == 0.

Input arguments

p: vector of denominators
q: vector of numerator
g: inequality constraints
h: equality constraints
x: vector of variables
d: relaxation order

Output arguments

SignSymmetry: exploit sign symmetries or not (true, false)
Groebnerbasis: exploit the quotient ring structure or not (true, false)

source

TSSOS.SparseSumOfRatios — Function

optimum = SparseSumOfRatios(p, q, g, h, x, d; QUIET=false, SignSymmetry=true, Groebnerbasis=false)

Minimizing the sum of sparse ratios p1/q1 + ... + pN/qN on the set defined by g >= 0 and h == 0.

Input arguments

p: vector of denominators
q: vector of numerator
g: inequality constraints
h: equality constraints
x: vector of variables
d: relaxation order

Output arguments

SignSymmetry: exploit sign symmetries or not (true, false)
Groebnerbasis: exploit the quotient ring structure or not (true, false)

source

References

Exploiting Sign Symmetries in Minimizing Sums of Rational Functions, Feng Guo, Jie Wang, and Jianhao Zheng, 2024.