Minimizing sum of powers

1

Given a set of n vectors a_i, I am trying to find a vector x to minimize the expression |a_1-x|^p+|a_2-x|^p+|a_3-x|^p+…+|a_n-x|^p, where p is greater than 1.

I am having trouble with writing this sum expression in cvx syntax. Could someone explain what is wrong with the code below? In the code I try to initialize 5 15x1 vectors in sample, and try to find the correct value of x.

sample = rand(15,5);
p=1.5;

cvx_begin
variable x(15)
minimize( sum(pow_p(abs(sample-x),p)) )
cvx_end

2

sample - x is not dimensionally consistent; that is a (15 by 5) matrix minus a (5 by 1) vector. Also, |a_1-x|^p doesn’t even make sense when x is a vector, not a scalar. Perhaps you want p norm to the pth power of a_1 - x ?

The first step is for you to figure out what mathematically what you want, and it must be dimensionally consistent. You can NOT make use in CVX of the new capability described in https://blogs.mathworks.com/loren/2016/10/24/matlab-arithmetic-expands-in-r2016b/ .

3

Thanks for the reply! Yes, I was hoping to minimize the pnorm between the a_is and x, so ||a_1-x||+||a_2-x||+||a_3-x||+…+||a_n-x||. I have trouble seeing how to do this using cvx.

4

If p = 1 or 2, you can use a very compact and vectorized implementation:

m = 15; n= 5;
samplee = rand(m,n);
p = 2;
cvx_begin
variable x(m)
minimize(sum(norms(samplee-repmat(x,1,n),p)))
cvx_end

Here is a more brute force way which will work for any p >= 1.

p = 2; % p = 1.5 also works, even p = inf
cvx_begin
variable x(m)
Obj = 0;
for i = 1:n
  Obj = Obj + norm(samplee(:,i)-x,p);;
end
minimize(Obj)
cvx_end

For p =1 or 2, both programs work, and for the same instantiation of samplee, produce the same results, within numerical tolerance

For any p >= 1 (but not inf), you could instead make your objective be the sum of norm^p by changing
Obj = Obj + norm(samplee(:,i)-x,p);
in the 2nd version to
Obj = Obj + pow_pos(norm(samplee(:,i)-x,p),p);

1 Like