0

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

Improve this question
2
  • Won't this just be at w = [0; 0; 0]? Commented Sep 6, 2011 at 14:14
  • 1
    @Richie: Only if H is positive semidefinite. Commented Sep 6, 2011 at 14:51

4 Answers 4

Reset to default
2

You're trying to solve a quadratic minimization problem with linear constraints (also known as quadratic programming).

Do you know anything about your matrix H -- in particular, is it positive semidefinite? I would really expect this to be the case, since this is usual for the problem domains in which quadratic programming problems usually crop up.

If H really is positive semidefinite, and your only constraint is |w1|+|w2|+|w3| < 3, then, as Richie Cotton has already pointed out, the minimum is trivially at w=0. Maybe you have some additional constraints?

If you do have additional constraints, but H is still positive semidefinite, there are existing efficient solvers for this class of problem. In MATLAB, take a look at quadprog.

You'll have to reformulate your single nonlinear constraint |w1|+|w2|+|w3| < 3 as a series of linear constraints.

In the one-dimensional case, the constraint |w1| < 1 turns into two linear constraints:

 w1 < 1
-w1 < 1.

In the two-dimensional case, the constraint |w1| + |w2| < 1 turns into four linear constraints:

 w1+w2 < 1
 w1-w2 < 1
-w1+w2 < 1
-w1-w2 < 1

I'll leave the extension to three dimensions to you.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

my matrix H is positive semidefinite, I also have an additional constraint, the sum of the three weights w1, w2 and w3 is equal to one.I did actually use quadprog, and turned the constraint into 8 linear equations. And it worked. However, my problem is with 25 weights, and since this generates too many linear equations, matlab ran out of memory. Is there a fix for this?
1

you need to use the optimization toolbox, specifically fmincon:

use fun to establish w'Hw, and you want c(eq) = (|w1|+|w2|+|w3| - 3) <0 which you set with nonlcon (in the documentation).

Improve this answer

6 Comments

quadprog is going to be much more efficient (and robust) for this than the more general fmincon.
quadprog implies a positive definite matrix, which may or may not be the case. Also, for a simple matrix, the difference in efficiency is minimal
That is incorrect. Matlab's quadprog computes a local optimum when the Hessian is indefinite. It will perform better than fmincon
Hi, since quadprog did not work in the dimension I required (N = 25), I tried fmincon. To test my code, I started with three weights, w1,w2 & w3. I found that, with some matrices I got the correct weights, however with others it just produced equal weights. Does anyone have any idea why this is? Does it have something to do with whether or not the matrix is positive definite or not? The covariance matrix H is estimated using various different methods, it is assumed to b positive semidefinite, but this is not always achieved by the estimation method.
@Jen: could it be that it is not converging? add the Display option via opimset (options = optimset('Display','final-detailed'). If that's the case you need to change the tolerance values. Also, can you give me an example matrix of when it gives that answer? FTR, I was wrong to suggest quadprog only works with positive definite matrices.
|
0

I'd suggest you look at the fminsearch function in the matlab documentation.

Improve this answer

Comments

0

Rasman, below is the fmincon code I am using:

    function PortfolioWeights = GMVPC1Type2(SCM)
    w0 = [0.1 0.1 0.1 0.1 0.1];
    n = length(w0);

    options = optimset('Display','final-detailed');
    PortfolioWeights = fmincon(@myobj2,w0,[],[],ones(1,n),1,[],[],@myconstraint1,options)

        function f = myobj2(w)
        w = [w(1);w(2);w(3);w(4);w(5)];
        f = w'*SCM*w;
        end
    end
    -----------------------------------------------------------------------------
    function [c ceq] = myconstraint1(w)

    c = abs(w(1))+abs(w(2))+abs(w(3))+abs(w(4))+abs(w(5))-1
    ceq = [];

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

I added in options = optimset('Display','final-detailed'); as you suggested. I get the following message:

Optimization stopped because the predicted change in the objective function,
6.115031e-009, is less than options.TolFun = 1.000000e-006, and the maximum constraint
violation, 0.000000e+000, is less than options.TolCon = 1.000000e-006.

Optimization Metric                                                 Options
abs(steplength*directional derivative) =  6.12e-009        TolFun =  1e-006 (default)
max(constraint violation) =  0.00e+000                     TolCon =  1e-006 (default)

Active inequalities (to within options.TolCon = 1e-006):
  lower      upper     ineqlin   ineqnonlin
                                 1

PortfolioWeights =

    0.2000    0.2000    0.2000    0.2000    0.2000

The matrix I am using is:

0.000257165759136336    8.48196702102889e-05    9.27141501220362e-05    0.000111360154790061    0.000155196440517440
8.48196702102889e-05    0.000277377166669392    0.000101880007672550    0.000107375764193076    0.000117042329431538
9.27141501220362e-05    0.000101880007672550    0.000300697293925817    0.000112004860252653    0.000134354417344316
0.000111360154790061    0.000107375764193076    0.000112004860252653    0.000311028738698100    0.000147296211557256
0.000155196440517440    0.000117042329431538    0.000134354417344316    0.000147296211557256    0.000376418027192374
Improve this answer

7 Comments

a few comments: you can simplify the L1-norm to sum(abs(w)) or norm(w,1). Also, you are setting Aeq and Beq so that the norm is always one. That may be why your solution doesn't work as expected. Finally, since the matrix is positive-definate, the best answer is the smallest possible vector (e.g. 0)
@Rasman The norm is defined in the nonlinear constraint under myconstraint1. The Aeq and beq is referring to the fact that I want my weights to sum to 1. Thus the sallest possible vector (0) will not apply.
for the norm I'm just saying that instead of writing out the terms, you can do a simple operation (and then you can simply put Aeq and Beq as ceq). Looking at the response, the problem is the tolerance values as it converges prematurely. change options = optimset('Display','final-detailed','TolFun',1e-15), you can change the other tolerance parameters as needed
It worked for N=5. I will try it when N=25. Thank you. What is the deal with the tolerance levels? What does changing it achieve. I looked it up in product help, but it didnt make much sense to me. Still do not understand your first point though.
So I tried it for the case when N = 25. I get weights which are not equal this time, which is a good sign. The message I get however is: " Solver stopped prematurely. fmincon stopped because it exceeded the function evaluation limit, options.MaxFunEvals = 2500 (the default value)." Did it work? Sorry if this is a trivial question. I dont really understand when it converges correctly. Cheers.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.