Minimizing a function

Hi,

I would like to minimize w'Hw, with respect to w, where w is a vector, and H is matrix.

And with the following constraint, (|w1|+|w2|+|w3| < 3), ie. the l1 norm of the weights vector is less that 3.

How can I do this in matlab?

Thanks

Answer 1

[Cédric Devivier]

Hi,

Maybe the fminsearch function is enough ?

See the following link: http://www.mathworks.fr/help/techdoc/ref/fminsearch.html

Something like that should work. Copy these two routines in a single m file.

    function [w_min value] = minimize(w0,H)
        [w_min value] = fminsearch(@(w) funtomini(w,H,w0) , w0);
    end

    function value = funtomini(w,H,w0)
        if sum(abs(w))<3; 
            value = w'*H*w;
        else
            value = w0'*H*w0;
        end
    end

Find the minimum using this command

    [w_min value] = minimize(w0,H);

Cheers,

Cédric

Answer 2

[Teja Muppirala]

This is a quadratic programming problem, and can be solved very easily using QUADPROG. The only thing is correctly expressing the L1 constraint.

% Make some random H
H = rand(3,3);
H =H+H';

% Express the L1 constraint using matrices:
[X1,X2,X3] = ndgrid([-1 1]);
A = [X1(:) X2(:) X3(:)];
b = 3*ones(size(A,1),1);

% solve for x
x = quadprog(H,[],A,b)

[Walter Roberson]

It is not immediately clear to me that the L1 constraint is correct there. It appears to me that you have effectively limited the range of values to [-1,1], but that is not the range limit of the original problem. In the original problem, it is the _sum_ of the absolute values that must be less than 3, which is a condition reachable with values up to [-3,3] (for which the weights of the other two would have to be near 0.)

[Teja Muppirala]

I believe the method outlined above is correct.

The L1 constraint is defined by 8 planes using the following inequalities:

x1+x2+x3 <= 3

x1+x2-x3 <= 3

x1-x2+x3 <= 3

.

.

.

.

-x1-x2-x3 <= 3

If you have access to QUADPROG, you can copy and paste the code above and confirm that norm(x,1) = 3. (Unless H is positive definite, and the solution is x = [0 0 0])

This method will scale well until you run out of memory for your A matrix, since its size is very large: [(2^N) x N] where N is the length of x. And there are other ways to generate the A matrix that may be easier that using ndgrid:

N = 3;

A = sign(dec2bin(0:(2^N-1),N) - 48 - 0.5)

For this problem, if your problem size lets you use QUADPROG, it will work significanly faster than FMINCON, and more importantly, as N gets larger, say 10~20, it will find a better value for x than FMINCON will.

[Jen]

This method is correct, however when I applied to to my problem where N =25, I run out of memory.

I get the following error:

??? Error using ==> horzcat

Out of memory. Type HELP MEMORY for your options.

Error in ==> GMVPC1Type3 at 6

A = [X1(:) X2(:) X3(:) X4(:) X5(:) X6(:) X7(:) X8(:) X9(:) X10(:) X11(:) X12(:) X13(:) X14(:)

X15(:) X16(:) X17(:) X18(:) X19(:) X20(:) X21(:) X22(:) X23(:) X24(:) X25(:)];

Error in ==> SCM12 at 63

PortfolioWeights = GMVPC1Type3(SCM);

Do you have any other suggestions?

[Jen]

The fmincon code works below for some matrices, but for other, gives equal weights to w1,w2 and w3. Any ideas why this is?

Answer 3

[Jen]

Cedric - Will give it a go

Teja - I initially used QUADPROG, but couldnt find a way of expressing the L1 constraint.

I decided to use fmincon with a nonlinear constraint.

Aeq = [1,1,1;0.05,0.06,0];

beq = [1;0.05];

A = [0,1,0];
b = 0.5;

w0 = [0.5 0.5 0.5];

[w,fval] = fmincon(@myobj,w0,A,b,Aeq,beq,[],[],@myconstraint)
------------------------------------------------------------------
function f = myobj(w)

diagmatrix = [0.15,0,0;0,0.20,0;0,0,0.40];

corrmatrix = [1,0.5,-0.7;0.5,1,-0.4;-0.7,-0.4,1];

covmatrix = diagmatrix*corrmatrix*diagmatrix;
w = [w(1);w(2);w(3)];
f = w'*covmatrix*w;

end
-----------------------------------------------------------------
function [c ceq] = myconstraint(w)
c = abs(w(1)) + abs(w(2)) + abs(w(3))-3;

ceq = [];

end
------------------------------------------------------------------

My only concern is how well will this work when dealing with large matrices? Is there code to achieve this I wonder?

[Jen]

This code seems to work on some matrices, but on others, it just gives equal weights to w1,w2,w3....anyone have any ideas why?