How to assign a count constraint to linear optimization

Hi There !

I am relatively new to optimization toolbox.

I want to use linear optimizer linprog to setup a linear portfolio weighting problem. I can setup all constraints but cannot setup the constraint that minimum number of variables that need to be used are 120.

In this case, I want to optimize the weights of the securities in the portfolio but also ensure atleast 120 securities are used. Should I use a nonlinear optimizer with a constraint objective function or am I missing something and there is a clever way to code this into a linear optimization ?

Can someone please help ?

Regards, Abhishek

[Abhishek BANERJEE]

Okay, I found the answer. To setup a constraint which counts the number of securities in this case would be to use n constraints of the form Xn >= 0 so bsaically have the first n rows of the inequality matrix set to -1 diagonally.

[Matt J]

No, that won't work because Xn>=0 also means that Xn can equal 0, i.e., not be used. The constraint you really want is Xn>0 and this leads to an ill-defined problem. much like minimizing the 1D function f(x)=x on x>0.

Incidentally, you would not use the rows of the inequality constraints to enforce Xn>=0. You would use LINPROG's 6th input argument lb.

[Abhishek BANERJEE]

No lb wont work as then also it can be zero as its an inequality. Is there another way to do it ?

[Matt J]

My point was only that the way to enforce constraints of the form lb<=x<=ub is NOT with the arguments A,b.

Answer 1

[Alan Weiss]

You are looking for mixed integer programming. Unfortunately, there is currently no Optimization Toolbox solver that supports this functionality.

The Global Optimization Toolbox GA solver can attempt to solve this kind of problem, but only for relatively low-dimensional cases, so I would not bother trying it on your problem.

Sorry.

Alan Weiss

MATLAB mathematical toolbox documentation

[Abhishek BANERJEE]

Hi Alan,

Thanks for looking into this. I was able to setup an excel solver to do this but I chose to use matlab because I ran into the issue that not more than 200 variables can be used in excel solver. Hence I could not use solver to optimize portfolios with more than 200 securities to begin with.

I am surprised to know that its not possible to do this in Matlab. Would you be kind to suggest an alternative product or maybe some algorithm that I can code into matlab to effectively implement this ?

Regards, Abhishek

[Abhishek BANERJEE]

Hi Alan,

I did a bit of reading on mixed integer programming and I think my problem is not that constrained. Basically, in my opinion, mixed integer programming means that some of the weights have to be integers. In my case that is not necessary. I dont need any of the weights to be integers. In my case, I just want a minimum number of weights to be non-zero.

I know in nonlinear programming we can set up an constraint function of the form g(x) where g(x) = (count of all non-zero elements of solution vector) -120 >= 0

Is it possible to implement that by some workarround ?

Regards, Abhishek

[Matt J]

I am surprised to know that its not possible to do this in Matlab.

If you're surprised that MATLAB cannot do this, then you did not understand my earlier example of why this is impossible, by MATLAB or any other solver. I'll try to give a more concrete 2D example.

min x+y
s.t.
 0<=x<=.3
 0<=y<=.3

Suppose you wanted to solve this linear program subject to the additional constraint that at least 1 of the x,y are strictly greater than 0. What would the solution be?

The solution does not exist because whether x or y is the variable to be strictly greater than 0, you have to make it arbitrarily close to zero to minimize the objective function. In other words, the minimum cannot be attained under the constraints as you've described them. If you accept a solution that minimizes the function asymptotically, you get x=y=0 which takes you back to the solution without the >0 condition.

You need to rethink the formulation of your problem, or at least how you've described it to us.

[Abhishek BANERJEE]

Alan,Matt,

I see your point. However, I perhaps have not formed the problem well and I am looking for someone who can help me understand how such a problem can be formed in matlab.

Going back to your example let me define this problem in more detail - maybe that helps. But I dont agree with your example. Maybe I am missing something.

My problem is of the following form

lets assume that c = -(scurityReturn)

f(x) = min (x1c1  + x2c2 + x3c3 + x4c4 +x5c5 +x6c6 + x7c7 + x8c8 + x9c9)

c = {-2.1,-1,-0.5,-0.3,1.5,2.5, 2.8,2.9}

2 <=x <= 30

x1+x2 <= 70
x3+x4 <= 40
x5+x6 <= 40
x7+x8+x9 <= 20
x1+x2 ...+x9 <= 100

I want to use atleast x1 to x6 and if required more

I think this problem has a solution.

Manually solving it gives me 

Without the constraint that x1 .. x6 needs to be used the solution is

fval = {30,30,30,10,0,0,0,0,0}

However, if we apply the constraint that x1 .. x6 needs to be used then its 

fval = {30,30,30,6,2,2,0,0,0}

Here it has maximized x1 and x2 but maitained both constraints x<= 30 and x1+x2 <= 70 and so on.

Can this be formulated somehow in Matlab.

I dont know if I am going the wrong way but I think this can be solved.

[Alan Weiss]

As I stated before, this is a relatively standard mixed integer linear programming problem. Currently, Optimization Toolbox does not directly support this type of problem. However, if you are willing to do a little extra work, you can often formulate your problem as a binary integer programming problem. This example might give you some ideas on how to do so.

And by the way, your "c" vector has only 8 components, it should have 9.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation