Harmonic mean in cvx


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)

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


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 .