Copyright © 2014 John Wiley & Sons, Ltd. In this paper, a novel decentralized algorithm is proposed to minimize power flow loss in a large-scale future grid connecting with many real-time-distributed generation systems by which power flows bi-directionally. The DC-power loss at each link is defined as the product of resistance and the square of current that can be considered as a quadratic flow cost. We employ the notion of tie-sets that reduces the complexity of the power flow loss problem by dividing a power network into a set of loops that forms a linear vector space on which the power loss problem can be formulated as a convex optimization problem. As finding a solution in each tie-set enables global optimization, we realize parallel computing within a system of independent tie-sets by integrating autonomous agents. Simulation results demonstrate the minimization of the power loss on every link by iteratively optimized power flows and show the superiority against the traditional centralized optimization scheme.