0
$\begingroup$

What are the fastest algorithm(s) (possibly approximation algorithms) for solving convex-convex quadratic fractional programming problems, i.e. optimization problems of the form

$$ \begin{align*} \sup& &\frac{x^TQx}{x^TPx}\\ \text{s.t.}& &A^Tx \leq b\\ &&x\geq 0 \end{align*} $$ where $Q\in\mathbb{R}^{n\times n}$ is a given symmetric positive semidefinite matrix, $P\in\mathbb{R}^{n\times n}$ is a given symmetric positive definite matrix, $A \in \mathbb{R}^{m\times n}$ is a given matrix, $b \in\mathbb{R}^{m\times 1}$ is a given column vector, and $m,n \in \{1,2,...\}$ are given.

I'm looking for algorithms that will run fast when $m, n \leq 500$.

Here's one algorithm that fits the bill:

R. Yamamoto and H. Konno: An efficient algorithm for solving convex-convex quadratic fractional programs. J. Optim. Theory Appl. 133 (2007), 241–255. DOI:10.1007/s10957- 007-9188-y

Are there any other algorithms that perform at least as fast as this one?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.