I think the optimization problem is to minimize the portfolio variance from the target allocation. I'm going to assume we are trading equities or etfs in which case the trade quantity can only be integers. (Mutual funds can have fractional shares but we can get into that later).
Min Sumofall Ending allocation% - target allocation %
Each security would be traded 0 or 1 time. The extra 100$ should actually be a 5th security called cash with a target allocation of 0%.
From the example, the transaction cost would be the pricequantity1%. Thats not how it works in the real world though so let's throw that out. The transaction cost is going to be a flat amount per trade, lets say 5$ because that is fairly common. That 5$ will be the same regardless of the price.
So if you ran all the combinations of trades you can make there is going to come a point where that 5$ per trade is going to reduce the total variance by less than making a trade will. For his example, you probably wouldn't make very many trades. Especially for security 1 or 2, because the prices are really high and a single trade would greatly increase the total portfolio variance.
I'm getting tired so I'll check back in later.. 242
but the answer to the algorithm is to not trade security 1 or 2, sell security 4 and 5(cash), and buy security 3.
Doh... I think I may have it wrong, the optimization problem is really maximize the portfolio value given a limit to the total portfolio variance. Or, some sort of ratio of portfolio value to variance. If you simply minimized variance then it would make trades in the overweight securities just so that you would incur trading costs and reduce your overweight in that security.
Edit: If you want a real brain buster try to figure it out when you add in all the real world considerations and constraints.... some securities have 0 commissions, some 5, some 20$. Some incur 2% fee if sold within 60 days. Some trade in only whole quantities(equities) and some trade in fractional quantities(mutual funds). Most people have more than 1 account so that adds to the complexity. Each security can have vastly different costs based on which account you put it in because of all the tax rules. 242