1
$\begingroup$

Given that $g(.),h(.)$ are twice-differentiable convex quadratic real functions whose domain is the set of all real matrices while the range is the set of positive real numbers, then:

Is maximizing the term $g(X)/h(X)$ w.r.t X the same as minimizing $h(X)-\nu g(X)$ for some scalar $\nu$? Is this always valid and why or why not and under what conditions?

I was thinking there is a different trade-off between how much, $g(X)$ is maximized while $h(X)$ is minimized in both the formulations.

$\endgroup$

3 Answers 3

1
$\begingroup$

In very abstract terms, a minimization requires (in most cases) that the minimizer makes the first derivative equal to zero. Then the minimizer of $g(X)/h(X)$ must satisfy $\frac {h'(X^*)}{g'(X^*)} = \frac {h(X^*)}{g(X^*)} $, while the minimizer of $h(X)-\nu g(X)$ must satisfy $\frac {h'(X^{**})}{g'(X^{**})} = \nu $.

For $X^{**} = X^{*}$ (which I presume is what you mean by "being the same as"), we must have $\frac {h(X^*)}{g(X^*)} = \nu$. So $\nu$ cannot be "some constant".

$\endgroup$
1
  • $\begingroup$ clear description. can you suggest on how the $\nu$ which is now a variable instead is chosen/solved for? $\endgroup$
    – hearse
    Oct 9, 2013 at 4:58
0
$\begingroup$

Not sure if I understand the question entirely correctly. But right now it seems to me that the answer is no. Suppose that both $g$ and $h$ are linear, then $h - \nu g$ is also linear, while $\frac{g}{h}$ might not be even convex. Similarly, let $g(x) = 1$ and $h(x) = x - 1$, then maximizing $\frac{g}{h} = \frac{1}{x -1}$ cannot be the same as minimizing $x - 1 - \nu$ for any $\nu$. In general it seems like this would hold only if you are lucky.

$\endgroup$
1
  • $\begingroup$ that's some great start. I had a similar opinion, but what do you think would be a reasonable condition, when it would work, as in I am unable to verify if it works for a given case. What would be the required conditions for it to work or as you put it to be 'lucky'? f(.)/g(.) is not convex in the cases am thinking of, while they are convex individually. So, how do i verify? Also f(.) and g(.) are quadratic in the cases i am interested in. $\endgroup$
    – hearse
    Oct 3, 2013 at 19:28
0
$\begingroup$

You can convert the maximization problem of $$\max g(X)/h(X)$$ to an equivalent minimization problem of $$\min h(X)/g(X)$$ using justification in "Minimization of Ratios" by S. Schaible .I

Then using the Dinkelbach approach, On nonlinear fractional programming, Management Sci. 13, you can convert it to the problem. $$\min h(X)- \nu g(X), \text{for some appropriate } \nu$$.

As @alecos-papadopoulos mentioned $\nu$ is not fixed but can be estimated using concavity properties if $F(\nu) = h(X)- \nu g(X)$ with repect to $\nu$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .