The software-defined network (SDN) is a new networking paradigm to improve network performance via logically centralized control and open standardized interfaces. However, the introduction of SDN technology faces many difficulties due to operational and economic constraints. Therefore, an incremental deployment scenario, the so-called hybrid SDN, is preferred. The transition from a legacy network to a pure SDN may take a long time; hence, it is of vital importance to consider the network optimization problem for hybrid SDNs. With SDN-enabled devices, multi-paths, where each flow can have multiple alternative paths, can be supported in bandwidth allocation. In contrast to traditional bandwidth allocation mechanisms in pure IP networks and full SDNs, this paper proposes a utility maximization model with the coexistence of single paths and multi-paths in the network, which aims to facilitate the transition to SDNs. We also design a novel algorithm to solve the maximization model, which is no longer strictly concave. Extensive simulations are conducted to evaluate the performance of the proposed bandwidth allocation strategy. Compared with existing strategies, our strategy has a good performance in terms of utility improvement. The results also show that with an increasing number of devices deployed in the SDN, more paths can be used to allocate the bandwidth; thus, a greater network utility can be achieved.