Multi-group multicast beamforming in wireless systems with large antenna arrays and massive audience is investigated in this paper. Multicast beamforming design is a well-known non-convex quadratically constrained quadratic programming (QCQP) problem. A conventional method to tackle this problem is to approximate it as a semi-definite programming problem via semi-definite relaxation, whose performance, however, deteriorates considerably as the number of per-group users goes large. A recent attempt is to apply convex-concave procedure (CCP) to find a stationary solution by treating it as a difference of convex programming problem, whose complexity, however, increases dramatically as the problem size increases. In this paper, we propose a low-complexity high-performance algorithm for multi-group multicast beamforming design in large-scale wireless systems by leveraging the alternating direction method of multipliers (ADMM) together with CCP. In specific, the original non-convex QCQP problem is first approximated as a sequence of convex subproblems via CCP. Each convex subproblem is then reformulated as a novel ADMM form. Our ADMM reformulation enables that each updating step is performed by solving multiple small-size subproblems with closed-form solutions in parallel. Numerical results show that our fast algorithm maintains the same favorable performance as state-of-the-art algorithms but reduces the complexity by orders of magnitude.
Both the two-stage approach for SOCPs @cite_7 and consensus ADMM for QCQPs @cite_32 deal with general optimization frameworks, but require a large number of auxiliary variables and hence lift the original problem into a much higher dimension space. Customized algorithms for specific problems to enable efficient or parallel computing are developed in @cite_19 @cite_26 by exploiting the structures of the problems. Specifically, in @cite_19 , the authors consider the robust coordinated beamforming in multi-cell networks. By using SDR approximation and S-Procedure methods, the original non-convex beamforming problem is first reformulated as a tractable convex SDP. Then an ADMM-based distributed algorithm is proposed, which is provably able to converge to the global optimum of the centralized SDP problem. The ADMM update in each BS, however, still relies on general-purpose solvers. In @cite_28 , the joint BS activation and beamforming design for power minimization problem in HetNets is first reformulated as an SOCP using a sparsity regularizer. An efficient algorithm based on ADMM is developed to solve the SOCP, in which each updating step is in closed form and can be carried out distributively among multiple BSs.
@cite_26 @cite_7 @cite_28 @cite_32 @cite_19
1874281995 2110838621 2236834722 2027650277
Multicell coordinated beamforming (MCBF), where multiple base stations (BSs) collaborate with each other in the beamforming design for mitigating the intercell interference (ICI), has been a subject drawing great attention recently. Most MCBF designs assume perfect channel state information (CSI) of mobile stations (MSs); however CSI errors are inevitable at the BSs in practice. Assuming elliptically bounded CSI errors, this paper studies the robust MCBF design problem that minimizes the weighted sum power of BSs subject to worst-case signal-to-interference-plus-noise ratio (SINR) constraints on the MSs. Our goal is to devise a distributed optimization method to obtain the worst-case robust beamforming solutions in a decentralized fashion with only local CSI used at each BS and limited backhaul information exchange between BSs. However, the considered problem is difficult to handle even in the centralized form. We first propose an efficient approximation method for solving the nonconvex centralized problem, using semidefinite relaxation (SDR), an approximation technique based on convex optimization. Then a distributed robust MCBF algorithm is further proposed, using a distributed convex optimization technique known as alternating direction method of multipliers (ADMM). We analytically show the convergence of the proposed distributed robust MCBF algorithm to the optimal centralized solution. We also extend the worst-case robust beamforming design as well as its decentralized implementation method to a fully coordinated scenario. Simulation results are presented to examine the effectiveness of the proposed SDR method and the distributed robust MCBF algorithm. Aiming at solving large-scale optimization problems, this paper studies distributed optimization methods based on the alternating direction method of multipliers (ADMM). By formulating the optimization problem as a consensus problem, the ADMM can be used to solve the consensus problem in a fully parallel fashion over a computer network with a star topology. However, traditional synchronized computation does not scale well with the problem size, as the speed of the algorithm is limited by the slowest workers. This is particularly true in a heterogeneous network where the computing nodes experience different computation and communication delays. In this paper, we propose an asynchronous distributed ADMM (AD-ADMM), which can effectively improve the time efficiency of distributed optimization. Our main interest lies in analyzing the convergence conditions of the AD-ADMM, under the popular partially asynchronous model, which is defined based on a maximum tolerable delay of the network. Specifically, by considering general and possibly non-convex cost functions, we show that the AD-ADMM is guaranteed to converge to the set of KarushKuhnTucker (KKT) points as long as the algorithm parameters are chosen appropriately according to the network delay. We further illustrate that the asynchrony of the ADMM has to be handled with care, as slightly modifying the implementation of the AD-ADMM can jeopardize the algorithm convergence, even under the standard convex setting. The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of the ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed, asynchronous and incremental manner. First, the component functions can be distributed to different computing nodes, who perform the updates asynchronously without coordinating with each other. Two sources of asynchrony are covered by our algorithm: one is caused by the heterogeneity of the computational nodes, and the other arises from unreliable communication links. Second, the algorithm can be viewed as implementing an incremental algorithm where at each step the (possibly delayed) gradients of only a subset of component functions are update d. We show that when certain bounds are put on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem. To the best of our knowledge, the proposed ADMM implementation can tolerate the highest degree of asynchrony, among all known asynchronous variants of the ADMM. Moreover, it is the first ADMM implementation that can deal with nonconvexity and asynchrony at the same time. We consider the interference management problem in a multicell MIMO heterogeneous network. Within each cell there is a large number of distributed micro pico base stations (BSs) that can be potentially coordinated for joint transmission. To reduce coordination overhead, we consider user-centric BS clustering so that each user is served by only a small number of (potentially overlapping) BSs. Thus, given the channel state information, our objective is to jointly design the BS clustering and the linear beamformers for all BSs in the network. In this paper, we formulate this problem from a sparse optimization perspective, and propose an efficient algorithm that is based on iteratively solving a sequence of group LASSO problems. A novel feature of the proposed algorithm is that it performs BS clustering and beamformer design jointly rather than separately as is done in the existing approaches for partial coordinated transmission. Moreover, the cluster size can be controlled by adjusting a single penalty parameter in the nonsmooth regularized utility function. The convergence of the proposed algorithm (to a stationary solution) is guaranteed, and its effectiveness is demonstrated via extensive simulation. Nonconvex quadratically constrained quadratic programming (QCQP) problems have numerous applications in signal processing, machine learning, and wireless communications, albeit the general QCQP is NP-hard, and several interesting special cases are NP-hard as well. This paper proposes a new algorithm for general QCQP. The problem is first reformulated in consensus optimization form, to which the alternating direction method of multipliers can be applied. The reformulation is done in such a way that each of the subproblems is a QCQP with only one constraint (QCQP-1), which is efficiently solvable irrespective of (non)convexity. The core components are carefully designed to make the overall algorithm more scalable, including efficient methods for solving QCQP-1, memory efficient implementation, parallel distributed implementation, and smart initialization. The proposed algorithm is then tested in two applications: multicast beamforming and phase retrieval. The results indicate superior performance over prior state-of-the-art methods.