I have a large amount of money in a lot of small coins in my wallet (most of them like 0.0002 BTC). But whatever I do, I loose about 15% due to transaction fees, because transactions are too large. Is there any tool for optimization of transactions, which could combine those coins into transactions with minimal or zero fee?
If the coins are in the same wallet then you should be able to send your "large amount of money" in one transaction.
If your coins are spread across multiple wallets in the same client then you would need to take the 15% loss. Or not pay a transaction fee and hope your coins get validated by a very friendly miner. (I would advise the former.)
In the event that your coins are spread across multiple wallets, you should bite the bullet and send them all to a single wallet so you don't continue losing money in the future.
It also might be a good idea to have slightly larger transactions, so you don't pay as many fees.
Lets assume you want to consolidate a lot of small unspent Inputs that are signed for use by addresses located on a few clients.
For every client, create a raw transaction with the unspent Inputs you want to spend (send to another address). Somehow join all the raw transactions, and start signing with the first client. Every client will have to sign before the finished transaction is broadcasted to the network.
I'm not exactly sure how to accomplish this, but all the bits of the puzzle exists:
To try this were going to use brainwallet.org with "correct horse battery staple". Then were going to http://brainwallet.org/#tx with that private key to create a raw transaction.
The private key is known and used by a lot of users, so there is "dust" we need to remove with "Edit Inputs". I saved the first and the last unspent outputs, to make this example shorter.
Think of these two unspent outputs belonging to different addresses. Then you need to sign with both to make it an valid transaction.
Take a look at Gavins example for signing a 2-of-3 transaction, notice how the hex is getting longer for every signing and returns "complete: true" when the transaction is valid for broadcast.
The last part is figuring out what fee is required, look at the JSON Transaction and notice "size":xxxx. Now use what you learn here to calculate an appropriate fee. (You need to include the fee before signing)
Import all your private keys with dust to Electrum and use them to pay the fee in your normal tansactions prioritizing them when making payments.