An SDP Approach For Solving Quadratic Fractional Programming Problems

arXiv1402.4198MaRDI QIDQ6249115FDOQ6249115

Authors: Van-Bong Nguyen, Ruey-Lin Sheu, Yong Xia 

Publication date: 17 February 2014

Abstract: This paper considers a fractional programming problem (P) which minimizes a ratio of quadratic functions subject to a two-sided quadratic constraint. As is well-known, the fractional objective function can be replaced by a parametric family of quadratic functions, which makes (P) highly related to, but more difficult than a single quadratic programming problem subject to a similar constraint set. The task is to find the optimal parameter $lambd{a}^{*}$ and then look for the optimal solution if $lambd{a}^{*}$ is attained. Contrasted with the classical Dinkelbach method that iterates over the parameter, we propose a suitable constraint qualification under which a new version of the S-lemma with an equality can be proved so as to compute $lambd{a}^{*}$ directly via an exact SDP relaxation. When the constraint set of (P) is degenerated to become an one-sided inequality, the same SDP approach can be applied to solve (P) {it without any condition}. We observe that the difference between a two-sided problem and an one-sided problem lies in the fact that the S-lemma with an equality does not have a natural Slater point to hold, which makes the former essentially more difficult than the latter. This work does not, either, assume the existence of a positive-definite linear combination of the quadratic terms (also known as the dual Slater condition, or a positive-definite matrix pencil), our result thus provides a novel extension to the so-called "hard case" of the generalized trust region subproblem subject to the upper and the lower level set of a quadratic function.

This page was built for publication: An SDP Approach For Solving Quadratic Fractional Programming Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6249115)