Assume f(x) and g(x) are convex functions. Our goal is minimization of f(x)/g(x). The f(x)/g(x) function is convex or concave depends on its parameters. Is it right to substitute it whit minimizing f(x) while maximizing g(x) and if CVX can implement this problem?
What you are describing is incorrect in general. If f(x) and g(x) are both convex, then f(x)/g(x) is not necessarily either convex or concave. For example, let f(x) = x and g(x) = -log(x). Then f(x)/g(x) is neither convex nor concave, as can easily be seen by examining the sign of its second derivative for various values of x. It would not be correct to minimize f(x) and maximize g(x), since the optimal value of x will generally not be the same.
Can you provide a detailed concrete example of what you are talking about? Perhaps you have a specific class of problems for which the ratio is convex and to which CVX can be applied?
thank you for your reply. In my problem X is a symmetric matrix. f(X) and g(X) are the abs of smallest and the largest eigenvalues of X respectively. I want to minimize f(X)/g(x)
This problem does not even fall into the description in your first post. If X is positive semii-definite, f(x) is concave and g(x) is convex. if X is negative semi-definite, f(x) is convex and g(x) is concave. In neither case, nor the more general case in which X could be indefinite, is f(x)/g(x) convex.
Your objective function, f(x)/g(x) is the reciprocal of the 2-norm condition number. That is a non-convex function. Even if you have a typo and mean your objective to the the 2-norm condition number, that is also non-convex. You can attempt to optimize this using a local nonlinear optimizer, and given the possibility of repeated eigenvalues, the objective function could be non-smooth (non-differentiable at repeated eigenvalues). See http://www.math.univ-toulouse.fr/~marechal/MinimizingCondition.pdf which address minimizing 2-norm condition number for positive semi-definite matrices (not maximizing it as, barring a typo, you seem to want to do), and of course you haven’t restricted the matrix to be positive semi-definite. See also http://www.math.toronto.edu/shub/Convexity%20Properties%20of%20the%20Condition%20Number.pdf and http://perso.math.univ-toulouse.fr/dedieu/files/2012/04/BDMSIISIMAX.pdf .
If your problem really is as stated, i.e., minimizing reciprocal of condition number, not minimizing condition number, it can be achieved if you can get X to have at least one eigenvalue equal to zero (i.e., be singular). This would result in the lowest possible value of your objective function, namely zero. How difficult or even possible that is to do depends on whatever constraints are applicable to X. if you are actually trying to minimize condition number, there may not be such an “easy” solution.
Edit: Per my post below, I withdraw the last paragraph above.
Thanks for your precise reply. The matrix X is neither positive nor negative definite. It can have negative and positive eigen values.
My objective function is NER which is the ratio of the absolute values of the smallest negative eigenvalue to the largest positive eigenvalue.
I don’t understand the necessity of singularity of X which you mentiond.
In my statement “it can be achieved if you can get X to have at least one eigenvalue equal to zero (i.e., be singular)”, I misinterpreted “abs of smallest negative eigenvalue” as meaning smallest abs(eigenvalue). In light of your clarification, I withdraw the last paragraph of my preceding post.
So what you have is a non-convex optimization problem. The difficulty of solving it depends on the constraints which are imposed on X. CVX can not be used directly to solve this problem, however, I would not rule out the possibility that you might be able to use CVX to solve convex sub-problems within a higher level algorithm.
Would you please let me know why NER is a nonconvex function?
Would you please let me know why it is a convex function?
I have no reason for its convexity. According previous posts, I think there is some references or information which shows non convexity of NER. If there is such a reference introducing that would be great help to me.
Here is a counterexample to the claim that NER, as you have defined it, is convex.
A = [0 1;1 1] B = [0 1;1 -1]
eig(A) = (1-sqrt(5))/2 and (1+sqrt(5))/2 eig(B) = -eig(A) NER(A) = NER(B) = -(1-sqrt(5))/(1+sqrt(5)) eig(0.5*A+0.5*B) = -1 and 1 NER(0.5*A+0.5*B) = 1
NER(0.5*A+0.5*B) = 1 > 0.5*NER(A)+0.5*NER(B) = -(1-sqrt(5))/(1+sqrt(5)) = 0.38196601125011
Thanks for your useful example. In my case A and B are symmetric matrices. In previous post, since eig(A) = -eig(B) we have NER(A) = 1/NER(B).
I investigate convexity of NER in my application as you prefer. The experimental results shows NER function is neither convex nor concave.