MATLAB: How to minimize the 12th norm of a difference vector

Question

Hi everybody, I have two vectores, lets say x and y. I calculate the difference vector d=x-y; I want to minimize d through the 12-norm of the difference (Euclidean distance) vector over 100 iterations. Is there anyone who could help me?

Kind regards, Joaquim

Answer 1

This is quite confusing, because you have not ever explained what you really want. In your words:

"x is a weighted sum of two vectores A and B, x= weight1 *A + weigth2*B. The purpose of the minimization is to find the weights that minimize x-y."

You say that you have vector y, and two vectors A and B. Then you need to compute the weighted linear combination x of vectors A and B, that minimizes the norm (lets not worry about which norm for the moment), so

norm(x-y) = norm((w1*A + w1*B) - y)

If you really want the 12norm here, this is a straight optimization problem, but the 12 norm is really not much different from the infinity norm. Solving an inf norm problem will reduce to a linear programming problem, whereas solving the 2-norm problem is simple linear least squares.

For example, to solve the 2-norm (i.e., Euclidean distance, which you did say above) problem, all you need do is:

W12 = [A(:),B(:)]\y(:);
weight1 = W12(1);
weight2 = W12(2);

That simple. So it is trivial to do. There are at least a half dozen other ways to compute the same set of weights in MATLAB, but the above solution is simplest. It yields a set of weights that minimize the 2-norm of the difference between x and y. There are no iterations needed. That is the true solution, IF you really wanted a 2-norm.

However, if you really wanted a 12 norm, and would not be interested in the infinity norm, then some iterative scheme would be employed.

Do you really need to do this as a 12 norm? Why would you pick such an arbitrary value as 12? As I said, it will be relatively little different from the infinity norm. For example:

v = randn(1,100);
norm(v,12)
ans =
        2.926
norm(v,inf)
ans =
        2.811

Whereas, the 2-norm is quite different.

norm(v,2)
ans =
       9.8925

So if you insist on computing the solution under a 12 norm via some (unspecified iterative scheme) I can show you some ways to do so. Will ANY reasonable iterative scheme suffice?

For example, lets make up some data, then I'll solve it under a 12-norm using fminsearch.

y = randn(100,1);
A = randn(100,1);
B = randn(100,1);

The 2 norm solution is:

W12_2norm = [A(:),B(:)]\y(:)
W12_2norm =
   -0.0024203
      0.11984

Now, create an objective function to use for an optimizer.

fun_12 = @(W12) norm((A*W12(1) + B*W12(2)) - y,12);
fun_12(W12_2norm)
ans =
       2.8766

The 2-norm solution is not the minimum set of weights for the 12norm problem. But it will provide starting values for the optimization.

[W12_12norm,fval] = fminsearch(fun_12,W12_2norm)
W12_12norm =
      0.31792
     -0.11325
fval =
       2.7072

So a different set of weights has been obtained, which yields a somewhat lower value for the 12-norm.

Again, the 12-norm seems a bit arbitrary to me. A different solution comes from the infinity norm.

fun_inf = @(W12) norm((A*W12(1) + B*W12(2)) - y,inf);
[W12_infnorm,fval] = fminsearch(fun_inf,W12_2norm)
W12_infnorm =
   -0.0047671
     -0.68259
fval =
       2.7561

I need to be a bit careful there, because the inf norm is really not well-solved using fminsearch, because the inf norm will not be a smooth, differentiable function. fminsearch would prefer differentiability. I'd have been better off using a linprog solution on that, but since you have not asked at all for an inf norm solution, I'm not going to go that deeply into the solution, especially since I have no idea what you really want.

If you can explain more clearly what you really need, I could give a more precise answer. And there are lots of iterative ways I could have solved this problem (fminbnd, for example), but I don't see why any particular iterative solution would be better than what I've shown already.