The Cloud computing paradigm enables innovative and disruptive services by allowing enterprises to lease computing, storage and network resources from physical infrastructure owners, to offer a persistently available service. This shift in infrastructure management responsibility has brought new revenue models and new challenges to Cloud providers. One of those challenges is to efficiently migrate multiple virtual machines (VMs) within the hosting infrastructure, since these migrations are often required to be "live", i.e., without noticeable service interruptions. In this paper we propose a geometric programming model and an online multi-VM live migration algorithm based on such model. The goal of the geometric program is to minimize the total migration time via optimal bit-rate assignments. By solving our geometric program we gained qualitative and quantitative insights into the design of efficient solutions for multi-VM live migrations. We found that transferring merely a few rounds of dirty memory pages are enough to significantly lower the total migration time. We also demonstrated that, under realistic settings, the proposed method converges sharply to an optimal bit-rate assignment, making our approach a viable solution for improving current live-migration implementations.