Harmonic mean in cvx


#1

We know harmonic mean is concave on the positive side. Is there any way to feed this function to cvx?


Harmonic mean not defined in CVX
(Michael C. Grant) #2

It depends on what you want to do with it.

For those who don’t know what the harmonic mean is, it’s f(x)=1/\sum_i x_i^{-1}. For positive x, it is concave. It’s also increasing in x, so that means it can accept a concave argument according to the DCP rules. Unfortunately, we haven’t figured out how to map it to the conic solvers in the most important case.

Let’s define g(x)=1/f(x)=\sum_i x_i^{-1}, which is just inv_pos(x):

  • To \text{maximize}~f(x), then you can just do \text{minimize} g(x) instead, which is just minimize(sum(inv_pos(x))).
  • To apply a constant lower bound f(x)\geq \alpha, then you can just multiply through to get 1\geq \alpha g(x), which is just 1 >= alpha*sum(inv_pos(x)).

What we cannot do, to the best of our knowledge, is f(x) \geq y, or equivalently 1 \geq y g(x), where both x and y are variables. If anyone knows how, please tell us, and I’ll put harm_mean into the function library! But that’s exactly the form I need in order to do that.

Again, x can be replaced with a vector of concave expressions according to the DCP rules, because inv_pos is convex and decreasing.


(Wouter Koolen-Wijkstra) #3

Dear all,

One way to enter the harmonic mean is as follows:

function cvx_optval = harm_mean(x)

cvx_begin
variable z
maximize 2*z - sum(quad_over_lin(z, x))
cvx_end

Cheers,
Wouter


Harmonic mean not defined in CVX
(Mark L. Stone) #4

It looks like you implemented harmonic mean as defined above by @mcg . However, that formula is missing a factor of length(x) in the numerator vs. the definition used in most of math, MATLAB’s harmmean , and CVXPY. However, Boyd and Vandenberghe define it as @mcg in their book “Convex Optimization”, but their Additional Exercises for that book define it with the factor of n (i.e., length(x)).

So to implement the standard definition of harmonic mean, I believe you have to multiply the objective by length(x), and then perhaps you have it.

I will defer to @mcg to assess your solution.


(Michael C. Grant) #5

I do think this is correct, subject to the scaling factor offered by Mark. Thank you!


(Michael C. Grant) #6

I should note that the developers of CVXPY figured this out at some point; I just hadn’t noticed, as I don’t use it (gasp!)


(Mark L. Stone) #7

Also see exercise 4.26a of Boyd and Vandenberghe . And for a generalization of harmonic mean to p-norms, see the solution (perhaps inspired by this thread?) posted by @Michal_Adamaszek at https://themosekblog.blogspot.dk/2018/03/harmonic-mean-p-norms-and-extremely.html .


(陈为) #8

I have a question here. x should be a vector in this optimization problem. But according to the document of quad_over_lin, “x must be a scalar or the same size as SUM(ABS(z).^2,DIM)”. As we cannot use quad_over_lin(1, [1 2 3]). However, the function you proposed is accepted by CVX. I am just curious about how this works.


(Mark L. Stone) #9

You can look at the source code in
cvx/functions/@cvx/quad_over_lin.m

Note that the version for numerical arguments in
cvx/functions/quad_over_lin.m
does not accept such an argument combination.

I defer to the developer for explanation of why.


(Wouter Koolen-Wijkstra) #10

Dear 陈为,

You are right. I do not know the motivation behind this discrepancy. Many matlab functions broadcast scalars, and I apparently correctly assumed quad_over_lin does too. As Mark_L_Stone noted, the cvx and numerical versions disagree. If you need a version that works for both, you can replace
sum(quad_over_lin(z, x))
by
sum(quad_over_lin(repmat(z,1,length(x)), x, 0))

Judging from the solver output these are indeed identical.

Cheers,
Wouter


(陈为) #11

Thank you for your prompt reply! I am solving a relevant optimization problem using CVX. And your post helps me a lot. There is nothing wrong with your code, it is perfectly accepted by CVX. I’m just curious about the reason for this discrepancy. And, as Mark_L_Stone said, there did exist some differences between the cvx and numerical versions. Thanks once again for your patience.