0

I want to add $f(\vec{x})=\frac{ \vec{x}^{\top}\vec{b}} {\vec{x}^{\top}\vec{c}}$ to an optimization problem as an additional objective, such that: $$\min_x g(\vec{x})+f(\vec{x}) \\ s.t ~~x_i \ge 0$$

in which $g(x)$ is convex, and $\vec{b}$ and $\vec{c}$ are positive vectors. I tried to checked the hessian of $f(x)$ for its convexity, and apparently depending on $\vec{x}$ it may be convex or concave (generally non-convex).

So when i use a convex solver (matlab fmincon), the result varies depending on the initial point. However when i use another constraint such as $\sum{x_i}=1$ or $\vec{x}^{\top}\vec{c}=1$ in combination with $x_i \geq 0$ it always converges to a certain answer $\vec{x}^*$ regardless of initial $x$.

So my question is, do those constraints make the optimization problem convex, although $f(x)$ is not convex? And if yes, can we optimize it using typical constrained convex optimization methods, for instance based on gradient-descent?

Bob
  • 690
  • Doesn't it depend on the sign of $x^T c$? – user251257 Jan 02 '18 at 15:27
  • 1
    No. Linear fractional forms are neither concave nor convex. Consult textbooks like Boyd & Vandenberghe for information on how linear fractional functions can be handled in the context of convex optimization, but there is no way to incorporate them into a standard convex program. – Michael Grant Jan 02 '18 at 15:52
  • @user251257 , Well, as $c_i \geq 0$ and $x$ should be positive that won't happen. But yes in the case of $x^Tc \geq 0$ the hessian becomes psd. But i still have the same question, if a constraint make the function convex, can we use a constraint optimization scheme regardless of $f(x)$ being non-convex outside of the constraint regions? – Bob Jan 02 '18 at 15:54
  • @MichaelGrant, Thank you! i'll look into that! :-) – Bob Jan 02 '18 at 15:55
  • It is simply not the case that the Hessian is PSD for $c^Tx\geq 0$. – Michael Grant Jan 02 '18 at 16:07
  • 1
    And you may be interested in this: https://math.stackexchange.com/questions/2038759/why-is-it-necessary-to-have-convexity-outside-the-feasible-region – Michael Grant Jan 02 '18 at 16:08
  • @MichaelGrant, i checked the LFP procedure , it converts the optimization to a Linear Programming, however it doesn't provide one specific $\vec{x}$ for my case, yet as a good point the minimum of $f(x)$ would be always the same. I think it is difficult to use that variable conversion when i have also $g(x)$ in the problem, and i'm afraid it makes it more complicated. – Bob Jan 02 '18 at 17:22
  • 1
    Ah, indeed, there are specific cases where problems involving linear fractional functions can be converted to convex form; for instance, if the entire objective is LF, and the constraints are all linear, or if you have a constraint such as $b^T x / c^T x \leq \alpha$, where $\alpha$ is constant and it is known that $c^T x \geq 0$. But the point is that the LF term is not convex, and so some sort of conversion must be performed. – Michael Grant Jan 02 '18 at 17:25

0 Answers0