In this paper, we propose a novel global optimization based 3-D multi-region segmentation algorithm for T1-weighted black-blood carotid magnetic resonance (MR) images. The proposed algorithm partitions a 3-D carotid MR image into three regions: wall, lumen, and background. The algorithm performs such partitioning by simultaneously evolving two coupled 3-D surfaces of carotid artery adventitia boundary (AB) and lumen-intima boundary (LIB) while preserving their anatomical inter-surface consistency such that the LIB is always located within the AB. In particular, we show that the proposed algorithm results in a fully time implicit scheme that propagates the two linearly ordered surfaces of the AB and LIB to their globally optimal positions during each discrete time frame by convex relaxation. In this regard, we introduce the continuous max-flow model and prove its duality/equivalence to the convex relaxed optimization problem with respect to each evolution step. We then propose a fully parallelized continuous max-flow-based algorithm, which can be readily implemented on a GPU to achieve high computational efficiency. Extensive experiments, with four users using 12 3T MR and 26 1.5T MR images, demonstrate that the proposed algorithm yields high accuracy and low operator variability in computing vessel wall volume. In addition, we show the algorithm outperforms previous methods in terms of high computational efficiency and robustness with fewer user interactions.