Harmonic mean in cvx

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

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.

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

2 Likes

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.

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

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!)

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 .

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.

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.

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

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.

Hi, if We have a logarithm of harmonic mean, how is express for CVX?

For the record, the answer to the immediately preceding post is supplied by @Michal_Adamaszek at How can I express this concave function in CVX .