2
$\begingroup$

I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g(x)$ and $h(x)$. It is known that $f(x)$ has a global minimum, achieved at the unique point $x_0$. Also is known that $f(x)$ has countably many local minima, and function $f(x)$ value at no two local minima, is the same.

Question: Is there any optimization algorithm for this scenario, which converges to the global minimum. I am hoping there is some variant of gradient descent or the likes. Appreciate any references/solutions.

$\endgroup$
5
$\begingroup$

Despite your claim that these functions have "special properties", the properties you've supplied still leave f and g extremely general. This means the answers you're going to get must be correspondingly general. If, for instance, you know that g is always positive or f is quadratic, or g is some kind of positive semi-definite matrix, and so on, then you should ask a new question specifying this critical information from the start.

What you're trying to do is convex-convex fractional programming. Schaible's 1976 paper "Minimization of ratios" explains how such a problem can be transformed into a quasi-convex problem Schaible 1976

So you can make this into a quasi-convex problem. That means that you can use bisection to solve the problem to $\epsilon$ tolerance in $\lceil log_2((u-l)/\epsilon)\rceil$ steps where $l$ and $u$ bound the range of the $t$ variable shown above.

Depending on the functions involved, you may be able to use cvxpy to solve the problem. Some examples showing bisection of quasiconvex functions are here and here.

$\endgroup$
  • $\begingroup$ Sorry I forgot to mention : f,g are strictly positive. Hope that helps : in case in this light, if it would deserve another answer, please advice accordingly. Also both$f$ and $g$ are quadratic. $\endgroup$ – Rajesh Dachiraju Feb 23 at 3:45
  • $\begingroup$ need your permission to proceed if I can post another question, or if you could help on this post itself. Thanks $\endgroup$ – Rajesh Dachiraju Feb 23 at 3:50
  • $\begingroup$ sorry both $g$ and $h$ are quadratic and strictly positive. not $f$ as I had mistakenly put in previous comment. $\endgroup$ – Rajesh Dachiraju Feb 23 at 3:56
  • $\begingroup$ @RajeshDachiraju: Does your problem have any constraints? $\endgroup$ – Richard Feb 23 at 4:50
  • $\begingroup$ None except one parameter in parameter vector is always zero. $\endgroup$ – Rajesh Dachiraju Feb 23 at 5:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.