分式二次规划问题的线性时间算法

We present a linear-time approximate algorithm for the problem(RQ)of minimizing the ratio of quadratic functions over an ellipsoid. The algorithmfrstly utilizes the bisection search to fnd a solution of Lagrange dual problemof (RQ), and then the global mimimum of (RQ) can be attained. Moreover,we prove the strong duality between primary problem and dual problem as well as give the interval of optimal Lagrange multiplier.

we study the problem of minimizing the ratio of two quadratic functions subject to a single quadratic constraint:
$$
begin{equation}
(text{RQ}): quad
begin{array}{c l}
min &f(x) = displaystyle frac{ f_1(x)}{1+ | x|^2},
text{s.t.} & c(x) leq 0,
end{array}
end{equation}
$$
where $f_1(x) = x^TA_1x + 2b_1^Tx+ c_1, c(x)=x^TA_2x - c_2$ ,$A_1$ is symmetric and $A_2$ is positive semidefinite, $ b_1 in R^n, c_1 in R~ text{and}~ c_2 >0 .$ In particular, the problem (RQ) includes the regularized total least squares problem (RTLS)
begin{equation}
(text{RTLS}): quad
begin{array}{c l}
min & displaystyle frac{| Ax - b |^2}{1+ | x|^2},
text{s.t.} & | Lx | ^2 leq rho.
end{array}
end{equation}

Here $rho > 0$ is a regularization parameter and $L in R^{rtimes n}$. The (RTLS) approach was extensively used in a variety of scientiflc disciplines such as signal processing, statistics, etc. Therefore, it is of great practical significance to study this (RQ) problem.

we first show that problem (RQ) is equivalent to solving a Lagrange dual formulation by applying strong duality.

It’s clear to see that problem (RQ) is equivalent to
begin{equation}
(text{RQ}): quad
begin{array}{c l}
min &f(x) = displaystylefrac{ f_1(x)}{1+ | x|^2},
text{s.t.} & displaystylefrac{c(x)}{1+ | x|^2} leq 0.
end{array}
end{equation}
For convenience, (RQ) problem in the following refers to above foumulation
The Lagrange function of (RQ) is writed that
begin{equation}
L(x,lambda) = frac{f_1(x)}{1+ | x|^2} + lambda frac{c(x)}{1+ | x|^2},
end{equation}
then the dual function is given by
begin{equation}
g(lambda) = inf_x L(x,lambda),quad lambda geq 0.
end{equation}
The Lagrange dual problem is thus
begin{equation}
(text{LD-RQ}): quad
begin{array}{c l}
max & g(lambda)
text{s.t.} & lambda geq 0.
end{array}
end{equation}

we utilize the bisection search to solve the Lagrange dual problem. Then, it allows us to compute a (RQ) optimal solution from a dual optimal solution.

Generally speaking, we can find the optimal function value of the nonconvex problem (RQ) by firstly solving the following convex SDP problem:
begin{equation}
(text{SDP}): quad
begin{array}{c l}
maxlimits_{lambda geq 0} & t
text{s.t.} & begin{bmatrix}
A_1 & b_1
b_1^T & c_1
end{bmatrix} + lambda begin{bmatrix}
A_2 & 0
0 & -c_2
end{bmatrix} succeq tI.
end{array}
end{equation}
Therefore, we solve the optimal multiplier to compare the running time by some software packages and our method. These packages mainly include SeDuMi , SDPT3 within CVX as well as SCS , CVXOPT within CVXPY . Some of the experimental results are as follows.