PaperlayerView exact revision on arXiv

Source-linked AI summary

Large-Scale Convex Optimization for Dense Wireless Cooperative Networks

Yuanming Shi, Jun Zhang, Brendan O'Donoghue, Khaled B. Letaief

arXiv:1506.00749v1cs.ITmath.ITmath.OC

TL;DR

Large-scale wireless optimization strains conventional solvers and modeling frameworks, while existing custom methods may not scale or detect infeasibility effectively. The paper combines matrix stuffing with ADMM applied to a homogeneous self-dual embedding. Its simulations report substantial solver speedups and scalability to problem sizes where the compared interior-point solvers fail.

  • Problem

    Dense wireless optimization creates large problems, while standard solvers can be computationally prohibitive and many custom methods do not scale well or detect infeasibility effectively.

    Source: §I · p. 2, D. A Unified Framework of Large-Scale… · p. 4

  • Method

    The framework transforms convex problems into standard cone form through matrix stuffing, then applies ADMM to the homogeneous self-dual embedding of the primal-dual pair.

    Source: §I · p. 2, 3) Homogeneous Self-Dual Embedding · p. 6

  • Results

    At L = 50, the operator-splitting solver is about 20x faster than MOSEK6 and 130x faster than SDPT3, while at L = 200 it solves in about 5 minutes as interior-point solvers fail at L = 100, 150, and 200.

    Source: A. Effectiveness and Reliability of… · p. 9

  • Takeaways & Limitations

    The framework supports large-scale wireless optimization with infeasibility detection and parallel computing, without requiring smooth or separable objective functions.

    Source: §I · p. 2, §VII · p. 11

Abstract

from arXiv · show

Convex optimization is a powerful tool for resource allocation and signal processing in wireless networks. As the network density is expected to drastically increase in order to accommodate the exponentially growing mobile data traffic, performance optimization problems are entering a new era characterized by a high dimension and/or a large number of constraints, which poses significant design and computational challenges. In this paper, we present a novel two-stage approach to solve large-scale convex optimization problems for dense wireless cooperative networks, which can effectively detect infeasibility and enjoy modeling flexibility. In the proposed approach, the original large-scale convex problem is transformed into a standard cone programming form in the first stage via matrix stuffing, which only needs to copy the problem parameters such as channel state information (CSI) and quality-of-service (QoS) requirements to the pre-stored structure of the standard form. The capability of yielding infeasibility certificates and enabling parallel computing is achieved by solving the homogeneous self-dual embedding of the primal-dual pair of the standard form. In the solving stage, the operator splitting method, namely, the alternating direction method of multipliers (ADMM), is adopted to solve the large-scale homogeneous self-dual embedding. Compared with second-order methods, ADMM can solve large-scale problems in parallel with modest accuracy within a reasonable amount of time. Simulation results will demonstrate the speedup, scalability, and reliability of the proposed framework compared with the state-of-the-art modeling frameworks and solvers.

I. INTRODUCTION

Dense cooperative networks create large optimization problems that challenge both standard solvers and modeling frameworks. The paper proposes a two-stage convex-optimization framework and illustrates its setting with a fully cooperative wireless network.

I. INTRODUCTION

  • Dense networks can involve hundreds of RAUs, creating high-dimensional problems with many constraints that strain interior-point solvers and make repeated modeling transformations costly.Prior wireless studies often used small networks or sub-optimal algorithms.Source: §I · pp. 1–2
  • The framework transforms the original convex problem into a standard cone program, then solves its homogeneous self-dual embedding with ADMM to support parallel computation and infeasibility certificates.The cone-program structure uses a subspace constraint and a Cartesian product of standard convex cones.Source: §I · p. 2

A. Contributions

  • Matrix stuffing reuses pre-generated standard-form structures, copying each instance’s channel, QoS, and power parameters instead of repeatedly parsing and regenerating the problem.The mapping depends on network size.Source: §I · p. 2
  • The paper formulates wireless performance problems in a unified framework and reports that optimal beamforming can significantly outperform sub-optimal schemes.The framework is intended to help evaluate cooperation strategies in dense networks.Source: A. Contributions · p. 2

A. Signal Model

  • The illustrated setting is a fully cooperative downlink network with centralized processing, where the model assumes full and perfect CSI at the central processor.The paper states that the approach can also apply to uplink problems when the resulting optimization problems are convex.Source: A. Signal Model · p. 3

B. Network Power Minimization

The section formulates network power minimization as coordinated beamforming under user QoS requirements and RAU power limits. It also describes group-sparse beamforming as a two-stage approach to reducing network power consumption.

B. Network Power Minimization

  • Coordinated beamforming minimizes total RAU transmit power while meeting the target SINR requirements of all mobile users.Each RAU also has its own transmit-power constraint.Source: B. Network Power Minimization · p. 3
  • The feasible set combines per-RAU transmit-power constraints with per-user QoS constraints, which can be reformulated as second-order cones.The resulting power-minimization problem is an SOCP.Source: B. Network Power Minimization · p. 3
  • Group-sparse beamforming first induces sparsity in the aggregated beamformer, then selects RAUs to switch off while checking whether the remaining units can still meet QoS.The stated objective includes optical fronthaul-link and RAU transmit-power consumption.Source: B. Network Power Minimization · pp. 3–4

C. Network Utility Maximization

Network utility maximization can require repeated convex feasibility checks, while some common utility formulations are NP-hard. The paper places these problems in a unified convex-optimization framework and uses matrix stuffing to reduce transformation overhead.

D. A Unified Framework of Large-Scale Network Optimization

C. Network Utility Maximization

  • For general increasing utility maximization, the paper describes searching for optimal SINRs through monotonic optimization, which may require exponentially many iterations in the number of users.The feasibility checks use the power-minimization problem at target SINRs.Source: C. Network Utility Maximization · p. 4

III. MATRIX STUFFING FOR FAST STANDARD CONE PROGRAMMING TRANSFORMATION

  • Matrix stuffing avoids repeated parsing and canonicalization by storing the standard-form structure and inserting each problem instance’s parameters into it.The paper presents this transformation as a way to address modeling overhead.Source: §III · pp. 4–5

A. Conic Formulation of Convex Programs

The framework converts the original convex problem into an equivalent standard cone program, whose solutions can yield either an optimum or an infeasibility certificate. Matrix stuffing reuses a stored problem structure to make instance-specific transformation efficient.

A. Conic Formulation of Convex Programs

  • The equivalent cone program preserves the ability to recover either an optimal solution or an infeasibility certificate for the original problem.The cone program uses a subspace and a Cartesian product of second-order cones; sparse storage reduces memory overhead.Source: A. Conic Formulation of Convex Programs · p. 5
  • The transformation introduces a variable for each subexpression in the disciplined convex programming form, rewriting the problem into Smith form.This standard form supports homogeneous self-dual embedding and a set structure suited to parallel computing.Source: A. Conic Formulation of Convex Programs · p. 5

B. Matrix Stuffing for Fast Transformation

  • For each network size, the framework can store the standard-form structure and its symbolic problem parameters offline.The stored structure includes dimensions, cone sizes, and the symbolic matrix A and vectors b and c.Source: B. Matrix Stuffing for Fast… · p. 5
  • For each instance, matrix stuffing copies its parameters into the corresponding standard-form data rather than repeatedly parsing and regenerating the problem.The copied parameters include channel coefficients, maximum transmit powers, and SINR targets.Source: B. Matrix Stuffing for Fast… · p. 5
  • The transformed cone program has a much larger dimension than the original problem, increasing from an original dimension of 2NK in the equivalent real field.The passage does not provide a complete readable expression for the transformed dimension.Source: B. Matrix Stuffing for Fast… · p. 5

IV. THE OPERATOR SPLITTING METHOD FOR LARGE-SCALE HOMOGENEOUS SELF-DUAL EMBEDDING

  • Directly solving the standard cone program may not provide infeasibility certificates, so the framework instead solves its primal-dual homogeneous self-dual embedding with ADMM.The embedding joins optimality and infeasibility information in one system.Source: §IV · p. 5, A. Homogeneous Self-Dual Embedding of… · pp. 5–6

A. Homogeneous Self-Dual Embedding of Cone Programming

1) Certificates of Infeasibility:

The section develops computable infeasibility certificates and uses a homogeneous self-dual embedding to combine feasibility outcomes and optimality conditions in one problem. The embedding can return an optimum or an infeasibility certificate, though one outcome of its trichotomy is inconclusive.

1) Certificates of Infeasibility:

  • For the general problem with per-user QoS and per-RAU power constraints, analytic feasibility conditions are difficult to obtain, and prior work often assumes feasibility or uses heuristics.A dual variable satisfying the stated certificate system proves primal infeasibility.Source: 1) Certificates of Infeasibility · p. 6

2) Optimality Conditions:

  • When the cone program is feasible, its optimal variables satisfy the KKT conditions, including complementary slackness that forces the duality gap to zero.Source: 2) Optimality Conditions · p. 6

3) Homogeneous Self-Dual Embedding:

  • The homogeneous self-dual embedding avoids solving feasibility and KKT problems sequentially by encoding optimality and infeasibility outcomes in one system.Its Cartesian-product set structure supports parallelizable algorithm design.Source: 3) Homogeneous Self-Dual Embedding · pp. 6–7
  • The embedding's trichotomy can yield an optimal solution or an infeasibility certificate, but when τ = κ = 0 it gives no conclusion about the cone problem.Source: 3) Homogeneous Self-Dual Embedding · p. 7

B. The Operator Splitting Method

The paper solves the homogeneous self-dual embedding with an operator-splitting ADMM algorithm. Its cone-product structure supports parallel computing, while the stated convergence rate and empirical accuracy characterize the approach.

B. The Operator Splitting Method

  • The embedding's constraint is a Cartesian product of standard cones, enabling parallelizable computation with operator splitting rather than a second-order method with cubic complexity for second-order cone programs.The paper reports that each iteration can be computed cheaply and efficiently.Source: B. The Operator Splitting Method · p. 7
  • Replicating variables x and y converts the embedding into a consensus form that is readily solved by operator splitting.Source: B. The Operator Splitting Method · p. 7
  • The ADMM updates use a linear solve, projection onto C, and a dual-variable update; the stated convergence rate is O(1/k), with empirical convergence to modest accuracy in reasonable time.The algorithm will not converge to zero if a nonzero solution exists.Source: B. The Operator Splitting Method · p. 7

1) Subspace Projection via Factorization Caching:

The implementation makes the embedding's subspace and cone projections tractable through sparse factorization reuse and separate closed-form cone projections. The paper also notes that manual matrix-stuffing mappings require substantial work and verification.

1) Subspace Projection via Factorization Caching:

  • Each iteration's subspace projection reduces to solving a linear system with a symmetric quasidefinite matrix, for which sparse permuted LDLT factorization can exploit sparsity.The factorization is computed once and cached for later projections.Source: 1) Subspace Projection via… · p. 7
  • With the cached factorization, subsequent subspace projections use forward and backward substitutions rather than recomputing the factorization.The cited costs depend on the number of nonzero entries in the factor L.Source: 1) Subspace Projection via… · p. 7

2) Cone Projection via Proximal Operator Evaluation:

  • Projection onto the Cartesian-product cone can be performed separately and in parallel on its component cones, using closed-form projections.The passage gives nonnegative-real and second-order cones as examples.Source: 2) Cone Projection via Proximal… · pp. 7–8

A. Automatic Code Generation for Fast Transformation

  • The stored mapping enables fast matrix-stuffing transformation and reduces modeling overhead relative to parser/solver frameworks, but deriving it manually is tedious and correctness is difficult to verify.The authors derived the mapping manually and checked it against CVX through extensive simulations.Source: A. Automatic Code Generation for Fast… · p. 8

B. Implementation of the Operator Splitting Algorithm

The operator-splitting implementation is paired with matrix stuffing to scale modeling and solving, while numerical results assess runtime, solution quality, and infeasibility detection. The results show faster large-scale optimization and feasibility detection, with practical deployment still requiring further investigation.

B. Implementation of the Operator Splitting Algorithm

  • OSADMM’s subspace projection is the main computational bottleneck; distributed factorization and symbolic factorization are proposed as ways to speed it up.Symbolic factorization could support real-time numerical solutions, but the authors state that this requires further investigation.Source: B. Implementation of the Operator… · p. 8

VI. NUMERICAL RESULTS

  • The numerical comparisons separate modeling time from solving time and use repeated problem instances with pre-stored cone-program structures; solver comparisons also differ in threading and accuracy goals.SCS is single-threaded and targets modest accuracy, whereas the interior-point solvers are multithreaded and target high accuracy.Source: §VI · pp. 8–9

A. Effectiveness and Reliability of the Proposed Large-Scale Convex Optimization Framework

  • Matrix stuffing cuts modeling time by about 15x to 60x versus CVX, including roughly 10 seconds versus 3 minutes at L = 150.The authors note that practical implementation could reduce this time further, but would require substantial investigation.Source: A. Effectiveness and Reliability of… · p. 9
  • At L = 200, SCS solves the problem in about 5 minutes while interior-point solvers fail at L = 100, 150, and 200; at L = 20 and 50, solutions are within 0.03% of second-order results.At L = 50, SCS is about 20x faster than MOSEK and 130x faster than SDPT3.Source: A. Effectiveness and Reliability of… · p. 9, Table I · p. 10

B. Infeasibility Detection Capability

  • For L = 100 (K = 100; 200 random network realizations), Matrix Stuffing+SCS matches CVX+SCS in infeasibility detection and reduces average modeling time from 18.6079 to 0.5028 seconds, about 40x.Source: B. Infeasibility Detection Capability · p. 10

C. Group Sparse Beamforming for Network Power Minimization

The simulations assess group-sparse network power minimization and max-min rate optimization, then identify practical implementation challenges. They report faster modeling or solving in the tested comparisons, alongside accurate solutions and infeasibility detection.

C. Group Sparse Beamforming for Network Power Minimization

  • The group-sparse beamforming procedure uses successive convex feasibility problems to select active RAUs, relying on infeasibility detection.It then solves a convex optimization problem to determine the transmit beamformers.Source: C. Group Sparse Beamforming for… · pp. 10–11
  • 20x: Matrix Stuffing+SCS reduced solving time relative to CVX+SDPT3 for the 20-RAU, 40-user network.Average total and solving times were (48.6916, 41.0316) seconds for CVX+SDPT3 and (2.4673, 2.3061) seconds for Matrix Stuffing+SCS.Source: C. Group Sparse Beamforming for… · pp. 10–11
  • At 50 RAUs and 50 users, Matrix Stuffing+SCS achieved the same network power solutions as CVX+SCS while reducing modeling time about 30x.CVX+SCS and Matrix Stuffing+SCS had average solving/modeling times of (11.9643, 69.0520) and (14.6559, 2.1567) seconds, respectively.Source: C. Group Sparse Beamforming for… · p. 11

D. Max-min Rate Optimization

  • For max-min rate optimization, the proposed framework reduced both solving and modeling times versus CVX+SCS for optimal beamforming.Average solving/modeling times were (176.3410, 55.1542) seconds for CVX+SCS and (82.0180, 1.2012) seconds for Matrix Stuffing+SCS.Source: D. Max-min Rate Optimization · p. 11
  • Optimal beamforming improved per-user rate over RZF, ZFBF, and MRT in the tested comparison.For those heuristic strategies, the reported CVX+SDPT3 solving times were small because the bisection search required only linear programs for power control with fixed beamformer directions.Source: D. Max-min Rate Optimization · p. 11

VII. CONCLUSIONS AND FURTHER WORKS

  • Practical deployment still faces challenging automatic symbolic transformation, costly semidefinite-cone projection, and the need to scale convex subproblems in non-convex algorithms.The paper identifies reliability and correctness verification as challenges for symbolic transformation; semidefinite projection requires eigenvalue decomposition, and scalable per-iteration computation is a hoped-for route to scaling majorization-minimization.Source: §VII · p. 12

APPENDIX CONIC FORMULATION FOR CONVEX PROGRAMS

The appendix illustrates how a real-field convex problem is converted through disciplined convex programming and Smith-form reformulation into a cone-program-compatible representation. A norm equality is relaxed to an inequality, which the authors show is tight at the optimum.

APPENDIX CONIC FORMULATION FOR CONVEX PROGRAMS

  • The appendix uses a real-field problem with objective f(x) = ∥v∥2 to illustrate the systematic conversion to standard convex cone programming form.It says the approach will then be extended to the complex-field case.Source: APPENDIX CONIC FORMULATION FOR CONVEX… · p. 12
  • The original problem is first rewritten in disciplined convex programming form.The passage identifies this as following the disciplined convex programming principle.Source: APPENDIX CONIC FORMULATION FOR CONVEX… · p. 12
  • The appendix states that convexity of the disciplined formulation can be checked using the disciplined convex programming ruleset.The passage gives associated matrices and vectors but does not further explain their roles.Source: APPENDIX CONIC FORMULATION FOR CONVEX… · p. 12

A. Smith Form Reformulation

  • Smith-form reformulation introduces a new variable for each subexpression in the disciplined convex program.Source: A. Smith Form Reformulation · p. 12
  • The Smith-form construction separately expresses RAU transmit-power constraints and MU QoS constraints.These are denoted G1(l) and G2(k), respectively.Source: A. Smith Form Reformulation · p. 12
  • The Smith form contains the non-convex constraint ∥x1∥ = x0, so the authors relax it to ∥x1∥ ≤ x0.Source: A. Smith Form Reformulation · p. 12
  • The relaxed constraint is active at the optimum, making the relaxed Smith form equivalent to the original disciplined convex problem.The stated justification is that otherwise x0 could be scaled down to reduce the objective while retaining feasibility.Source: A. Smith Form Reformulation · p. 12

B. Conic Reformulation

This section assembles the relaxed Smith-form constraints into the standard cone program. It defines optimization variables and slack-variable cones for the general, RAU, and user constraint blocks.

B. Conic Reformulation

  • The relaxed Smith form is converted to standard cone-program form by ordering the optimization variables consistently with the equations in G0.Source: B. Conic Reformulation · p. 12
  • The standard-form construction includes slack variables constrained to a convex set.Source: B. Conic Reformulation · p. 12
  • For each RAU constraint block G1(l), the variables are ordered to match its equations and its slack vector belongs to a product of two convex sets.The slack vector is denoted µ1_l and has dimension KN_l+2.Source: B. Conic Reformulation · p. 12
  • For each MU QoS block G2(k), the variables follow its equation order and its slack vector belongs to a product of two convex sets.The slack vector is denoted µ2_k and has dimension K+3.Source: B. Conic Reformulation · p. 13
  • The full standard-form variable vector ν is assembled from the indicated optimization-variable blocks.Source: B. Conic Reformulation · p. 13
  • The objective coefficient vector is c = [1; 0n−1], and the cone K is a Cartesian product of 2(L+K)+1 second-order cones.The passage also introduces A and b as the remaining standard-cone-program data.Source: B. Conic Reformulation · p. 13
  • The standard-form construction specifies a dimension expression for the program’s variables or data.The supplied passage gives the expression as (KN_l + 1)+K(K + 2).Source: B. Conic Reformulation · p. 13

C. Matrix Stuffing

Matrix stuffing forms each instance’s standard cone-program data by copying problem parameters into a pre-stored structure. The complex-field extension maps complex channel and beamforming vectors into real-valued representations.

C. Matrix Stuffing

  • Matrix stuffing copies maximum RAU powers, SINR thresholds, and channel realizations into the corresponding standard-form data.The passage identifies these as values placed in b and A; the transformation is described as memory copying and as more efficient than numerical modeling frameworks such as CVX.Source: C. Matrix Stuffing · p. 13

D. Extension to the Complex Case

  • The complex-field problem is converted to a real-field problem by replacing h_k and v_i with their real-valued representations.The passage gives the transformed channel representation as ˜h_k ∈ R^(2N×2) and beamforming representation as ˜v_i ∈ R^(2N).Source: D. Extension to the Complex Case · p. 13
Loading 1506.00749v1…