
In this paper, we consider a fundamental problem in modern digital
communications known as multiinput multioutput (MIMO) detection, which can be
formulated as a complex quadratic programming problem subject to unitmodulus
and discrete argument constraints. Various semidefinite relaxation (SDR) based
algorithms have been proposed to solve the problem in the literature. In this
paper, we first show that the conventional SDR is generally not tight for the
problem. Then, we propose a new and enhanced SDR and show its tightness under
an easily checkable condition, which essentially requires the level of the
noise to be below a certain threshold. The above results have answered an open
question posed by So in [35]. Numerical simulation results show that our
proposed SDR significantly outperforms the conventional SDR in terms of the
relaxation gap.

An important step in a multisensor surveillance system is to estimate sensor
biases from their noisy asynchronous measurements. This estimation problem is
computationally challenging due to the highly nonlinear transformation between
the global and local coordinate systems as well as the measurement asynchrony
from different sensors. In this paper, we propose a novel nonlinear least
squares (LS) formulation for the problem by assuming the existence of a
reference target moving with an (unknown) constant velocity. We also propose an
efficient block coordinate decent (BCD) optimization algorithm, with a
judicious initialization, to solve the problem. The proposed BCD algorithm
alternately updates the range and azimuth bias estimates by solving linear
least squares problems and semidefinite programs (SDPs). In the absence of
measurement noise, the proposed algorithm is guaranteed to find the global
solution of the problem and the true biases. Simulation results show that the
proposed algorithm significantly outperforms the existing approaches in terms
of the root mean square error (RMSE).

The performance of cloud radio access network (CRAN) is limited by the
finite capacities of the backhaul links connecting the centralized processor
(CP) with the basestations (BSs), especially when the backhaul is implemented
in a wireless medium. This paper proposes the use of wireless multicast
together with BS caching, where the BSs prestore contents of popular files, to
augment the backhaul of CRAN. For a downlink CRAN consisting of a single
cluster of BSs and wireless backhaul, this paper studies the optimal cache size
allocation strategy among the BSs and the optimal multicast beamforming
transmission strategy at the CP such that the user's requested messages are
delivered from the CP to the BSs in the most efficient way. We first state a
multicast backhaul rate expression based on a joint cachechannel coding
scheme, which implies that larger cache sizes should be allocated to the BSs
with weaker channels. We then formulate a twotimescale joint cache size
allocation and beamforming design problem, where the cache is optimized offline
based on the longterm channel statistical information, while the beamformer is
designed during the file delivery phase based on the instantaneous channel
state information. By leveraging the sample approximation method and the
alternating direction method of multipliers (ADMM), we develop efficient
algorithms for optimizing cache size allocation among the BSs, and quantify how
much more cache should be allocated to the weaker BSs. We further consider the
case with multiple files having different popularities and show that it is in
general not optimal to entirely cache the most popular files first. Numerical
results show considerable performance improvement of the optimized cache size
allocation scheme over the uniform allocation and other heuristic schemes.

In a fullduplex (FD) multiuser network, the system performance is not only
limited by the selfinterference but also by the cochannel interference due to
the simultaneous uplink and downlink transmissions. Joint design of the
uplink/downlink transmission direction of users and the power allocation is
crucial for achieving high system performance in the FD multiuser network. In
this paper, we investigate the joint uplink/downlink transmission direction
assignment (TDA), user paring (UP) and power allocation problem for maximizing
the system maxmin fairness (MMF) rate in a FD multiuser orthogonal frequency
division multiple access (OFDMA) system. The problem is formulated with a
twotimescale structure where the TDA and the UP variables are for optimizing
a longterm MMF rate while the power allocation is for optimizing an
instantaneous MMF rate during each channel coherence interval. We show that the
studied joint MMF rate maximization problem is NPhard in general. To obtain
highquality suboptimal solutions, we propose efficient methods based on simple
relaxation and greedy rounding techniques. Simulation results are presented to
show that the proposed algorithms are effective and achieve higher MMF rates
than the existing heuristic methods.

In this paper, we consider the linearly constrained composite convex
optimization problem, whose objective is a sum of a smooth function and a
possibly nonsmooth function. We propose an inexact augmented Lagrangian (IAL)
framework for solving the problem. The stopping criterion used in solving the
augmented Lagrangian (AL) subproblem in the proposed IAL framework is weaker
and potentially much easier to check than the one used in most of the existing
IAL frameworks/methods. We analyze the global convergence and the nonergodic
convergence rate of the proposed IAL framework.

The use of lowresolution digitaltoanalog converters (DACs) for transmit
precoding provides crucial energy efficiency advantage for massive
multipleinput multipleoutput (MIMO) implementation. This paper formulates a
quadrature amplitude modulation (QAM) constellation range and onebit
symbollevel precoding design problem for minimizing the average symbol error
rate (SER) in downlink massive MIMO transmission. A tight upperbound for SER
with lowresolution DAC precoding is first derived. The derived expression
suggests that the performance degradation of onebit precoding can be
interpreted as a decrease in the effective minimum distance of the QAM
constellation. Using the obtained SER expression, we propose a QAM
constellation range design for the singleuser case. It is shown that in the
massive MIMO limit, a reasonable choice for constellation range with onebit
precoding is that of the infiniteresolution precoding with persymbol power
constraint, but reduced by a factor of $\sqrt{2/\pi}$ or about $0.8$. The
corresponding minimum distance reduction translates to about 2dB gap between
the performance of onebit precoding and infiniteresolution precoding. This
paper further proposes a lowcomplexity heuristic algorithm for onebit
precoder design. Finally, the proposed QAM constellation range and precoder
design are generalized to the multiuser downlink. We propose to scale the
constellation range for infiniteresolution zeroforcing (ZF) precoding with
persymbol power constraint by the same factor of $\sqrt{2/\pi}$ for onebit
precoding. The proposed onebit precoding scheme is shown to be within 2dB of
infiniteresolution ZF. In term of number of antennas, onebit precoding
requires about 50% more antennas to achieve the same performance as
infiniteresolution precoding.

Crowdsourced wireless community network enables individual users to share
their private WiFi access points (APs) with each other, hence can achieve a
large WiFi coverage with a small deployment cost via crowdsourcing. This paper
presents a novel contractbased incentive framework to incentivize such a WiFi
network crowdsourcing under incomplete information (where each user has certain
private information such as mobility pattern and WiFi access quality). In the
proposed framework, the network operator designs and offers a set of contract
items to users, each consisting of a WiFi access price (that a user can charge
others for accessing his AP) and a subscription fee (that a user needs to pay
the operator for joining the community). Different from the existing contracts
in the literature, in our contract model each user's best choice depends not
only on his private information but also on other users' choices. This greatly
complicates the contract design, as the operator needs to analyze the
equilibrium choices of all users, rather than the best choice of each single
user. We first derive the feasible contract that guarantees the users' truthful
information disclosure based on the equilibrium analysis of user choice, and
then derive the optimal (and feasible) contract that yields the maximal profit
for the operator. Our analysis shows that a user who provides a higher WiFi
access quality is more likely to choose a higher WiFi access price and
subscription fee, regardless of the user mobility pattern. Simulation results
further show that when increasing the average WiFi access quality of users,
the operator can gain more profit, but (counterintuitively) offer lower WiFi
access prices and subscription fees for users.

To support multiple ondemand services over fixed communication networks,
network operators must allow flexible customization and fast provision of their
network resources. One effective approach to this end is network
virtualization, whereby each service is mapped to a virtual subnetwork
providing dedicated ondemand support to network users. In practice, each
service consists of a prespecified sequence of functions, called a service
function chain (SFC), while each service function in a SFC can only be provided
by some given network nodes. Thus, to support a given service, we must select
network function nodes according to the SFC and determine the routing strategy
through the function nodes in a specified order. A crucial network slicing
problem that needs to be addressed is how to optimally localize the service
functions in a physical network as specified by the SFCs, subject to link and
node capacity constraints. In this paper, we formulate the network slicing
problem as a mixed binary linear program and establish its strong NPhardness.
Furthermore, we propose efficient penalty successive upper bound minimization
(PSUM) and PSUMR(ounding) algorithms, and two heuristic algorithms to solve
the problem. Simulation results are shown to demonstrate the effectiveness of
the proposed algorithms.

This letter shows that the flexible association of possibly multiple base
stations (BSs) to each user over multiple frequency bands, along with the joint
optimization of BS transmit power that encourages the turningoff of the BSs at
offpeak time, can significantly improve the performance of a downlink
heterogeneous wireless cellular network. We propose a gradient projection
algorithm for optimizing BS association and an iteratively reweighting scheme
together with a novel proximal gradient method for optimizing power in order to
find the optimal tradeoff between network utility and power consumption.
Simulation results reveal significant performance improvement as compared to
the conventional singleBS association.

The interval subset sum problem (ISSP) is a generalization of the wellknown
subset sum problem. Given a set of intervals
$\left\{[a_{i,1},a_{i,2}]\right\}_{i=1}^n$ and a target integer $T,$ the ISSP
is to find a set of integers, at most one from each interval, such that their
sum best approximates the target $T$ but cannot exceed it. In this paper, we
first study the computational complexity of the ISSP. We show that the ISSP is
relatively easy to solve compared to the 01 Knapsack problem (KP). We also
identify several subclasses of the ISSP which are polynomial time solvable
(with high probability), albeit the problem is generally NPhard. Then, we
propose a new fully polynomial time approximation scheme (FPTAS) for solving
the general ISSP problem. The time and space complexities of the proposed
scheme are ${\cal O}\left(n \max\left\{1 / \epsilon,\log n\right\}\right)$ and
${\cal O}\left(n+1/\epsilon\right),$ respectively, where $\epsilon$ is the
relative approximation error. To the best of our knowledge, the proposed scheme
has almost the same time complexity but a significantly lower space complexity
compared to the best known scheme. Both the correctness and efficiency of the
proposed scheme are validated by numerical simulations. In particular, the
proposed scheme successfully solves ISSP instances with $n=100,000$ and
$\epsilon=0.1\%$ within one second.

Consider the singlegroup multicast beamforming problem, where multiple users
receive the same data stream simultaneously from a single transmitter. The
problem is NPhard and all existing algorithms for the problem either find
suboptimal approximate or local stationary solutions. In this paper, we propose
an efficient branchandbound algorithm for the problem that is guaranteed to
find its global solution. To the best of our knowledge, our proposed algorithm
is the first tailored global algorithm for the singlegroup multicast
beamforming problem. Simulation results show that our proposed algorithm is
computationally efficient (albeit its theoretical worstcase iteration
complexity is exponential with respect to the number of receivers) and it
significantly outperforms a stateoftheart generalpurpose global
optimization solver called Baron. Our proposed algorithm provides an important
benchmark for performance evaluation of existing algorithms for the same
problem. By using it as the benchmark, we show that two stateoftheart
algorithms, semidefinite relaxation algorithm and successive linear
approximation algorithm, work well when the problem dimension (i.e., the number
of antennas at the transmitter and the number of receivers) is small but their
performance deteriorates quickly as the problem dimension increases.

In this letter, we consider the joint power and admission control (JPAC)
problem by assuming that only the channel distribution information (CDI) is
available. Under this assumption, we formulate a new chance (probabilistic)
constrained JPAC problem, where the signal to interference plus noise ratio
(SINR) outage probability of the supported links is enforced to be not greater
than a prespecified tolerance. To efficiently deal with the chance SINR
constraint, we employ the sample approximation method to convert them into
finitely many linear constraints. Then, we propose a convex approximation based
deflation algorithm for solving the sample approximation JPAC problem. Compared
to the existing works, this letter proposes a novel twotimescale JPAC
approach, where admission control is performed by the proposed deflation
algorithm based on the CDI in a large timescale and transmission power is
adapted instantly with fast fadings in a small timescale. The effectiveness of
the proposed algorithm is illustrated by simulations.

In this paper, we consider a multiuser wireless system with one full duplex
(FD) base station (BS) serving a set of half duplex (HD) mobile users.To cope
with the inband selfinterference (SI) and cochannel interference, we
formulate a qualityofservice (QoS) based linear transceiver design problem.
The problem jointly optimizes the downlink (DL) and uplink (UL) beamforming
vectors of the BS and the transmission powers of UL users so as to provide both
the DL and UL users with guaranteed signaltointerferenceplusnoise ratio
performance, using a minimum UL and DL transmission sum power.The considered
system model not only takes into account noise caused by nonideal RF circuits,
analog/digital SI cancellation but also constrains the maximum signal power at
the input of the analogtodigital converter (ADC) for avoiding signal
distortion due to finite ADC precision. The formulated design problem is not
convex and challenging to solve in general. We first show that for a special
case where the SI channel estimation errors are independent and identically
distributed, the QoSbased linear transceiver design problem is globally
solvable by a polynomialtime bisection algorithm.For the general case, we
propose a suboptimal algorithm based on alternating optimization (AO). The AO
algorithm is guaranteed to converge to a KarushKuhnTucker solution.To reduce
the complexity of the AO algorithm, we further develop a fixedpoint method by
extending the classical uplinkdownlink duality in HD systems to the FD
system.Simulation results are presented to demonstrate the performance of the
proposed algorithms and the comparison with HD systems.

Consider a multiuser multicarrier communication system where multiple users
share multiple discrete subcarriers. To achieve high spectrum efficiency, the
users in the system must choose their transmit power dynamically in response to
fast channel fluctuations. Assuming perfect channel state information, two
formulations for the spectrum management (power control) problem are considered
in this paper: the first is to minimize the total transmission power subject to
all users' transmission data rate constraints, and the second is to maximize
the minrate utility subject to individual power constraints at each user. It
is known in the literature that both formulations of the problem are polynomial
time solvable when the number of subcarriers is one and strongly NPhard when
the number of subcarriers are greater than or equal to three. However, the
complexity characterization of the problem when the number of subcarriers is
two has been missing for a long time. This paper answers this longstanding
open question: both formulations of the problem are strongly NPhard when the
number of subcarriers is two.

Crowdsourced wireless community networks can effectively alleviate the
limited coverage issue of WiFi access points (APs), by encouraging individuals
(users) to share their private residential WiFi APs with others. In this
paper, we provide a comprehensive economic analysis for such a crowdsourced
network, with the particular focus on the users' behavior analysis and the
community network operator's pricing design. Specifically, we formulate the
interactions between the network operator and users as a twolayer Stackelberg
model, where the operator determining the pricing scheme in Layer I, and then
users determining their WiFi sharing schemes in Layer II. First, we analyze
the user behavior in Layer II via a twostage membership selection and network
access game, for both smallscale networks and largescale networks. Then, we
design a partial price differentiation scheme for the operator in Layer I,
which generalizes both the complete price differentiation scheme and the single
pricing scheme (i.e., no price differentiation). We show that the proposed
partial pricing scheme can achieve a good tradeoff between the revenue and the
implementation complexity. Numerical results demonstrate that when using the
partial pricing scheme with only two prices, we can increase the operator's
revenue up to 124.44% comparing with the single pricing scheme, and can achieve
an average of 80% of the maximum operator revenue under the complete price
differentiation scheme.

Optimization problems over permutation matrices appear widely in facility
layout, chip design, scheduling, pattern recognition, computer vision, graph
matching, etc. Since this problem is NPhard due to the combinatorial nature of
permutation matrices, we relax the variable to be the more tractable doubly
stochastic matrices and add an $L_p$norm ($0 < p < 1$) regularization term to
the objective function. The optimal solutions of the $L_p$regularized problem
are the same as the original problem if the regularization parameter is
sufficiently large. A lower bound estimation of the nonzero entries of the
stationary points and some connections between the local minimizers and the
permutation matrices are further established. Then we propose an $L_p$
regularization algorithm with local refinements. The algorithm approximately
solves a sequence of $L_p$ regularization subproblems by the projected gradient
method using a nonmontone line search with the BarzilaiBorwein step sizes. Its
performance can be further improved if it is combined with certain local search
methods, the cutting plane techniques as well as a new negative proximal point
scheme. Extensive numerical results on QAPLIB and the bandwidth minimization
problem show that our proposed algorithms can often find reasonably high
quality solutions within a competitive amount of time.

Consider the joint power and admission control (JPAC) problem for a
multiuser singleinput singleoutput (SISO) interference channel. Most
existing works on JPAC assume the perfect instantaneous channel state
information (CSI). In this paper, we consider the JPAC problem with the
imperfect CSI, that is, we assume that only the channel distribution
information (CDI) is available. We formulate the JPAC problem into a chance
(probabilistic) constrained program, where each link's SINR outage probability
is enforced to be less than or equal to a specified tolerance. To circumvent
the computational difficulty of the chance SINR constraints, we propose to use
the sample (scenario) approximation scheme to convert them into finitely many
simple linear constraints. Furthermore, we reformulate the sample approximation
of the chance SINR constrained JPAC problem as a composite group sparse
minimization problem and then approximate it by a secondorder cone program
(SOCP). The solution of the SOCP approximation can be used to check the
simultaneous supportability of all links in the network and to guide an
iterative link removal procedure (the deflation approach). We exploit the
special structure of the SOCP approximation and customdesign an efficient
algorithm for solving it. Finally, we illustrate the effectiveness and
efficiency of the proposed sample approximationbased deflation approaches by
simulations.

A crowdsourced wireless community network can effectively alleviate the
limited coverage issue of WiFi access points (APs), by encouraging individuals
(users) to share their private residential WiFi APs with each other. This
paper presents the first study on the users' joint membership selection and
network access problem in such a network. Specifically, we formulate the
problem as a twostage dynamic game: Stage I corresponds to a membership
selection game, in which each user chooses his membership type; Stage II
corresponds to a set of network access games, in each of which each user
decides his WiFi connection time on the AP at his current location. We analyze
the Subgame Perfect Equilibrium (SPE) systematically, and study whether and how
best response dynamics can reach the equilibrium. Through numerical studies, we
further explore how the equilibrium changes with the users' mobility patterns
and network access evaluations. We show that a user with a more popular home
location, a smaller travel time, or a smaller network access evaluation is more
likely to choose a specific type of membership called Bill. We further
demonstrate how the network operator can optimize its pricing and incentive
mechanism based on the game equilibrium analysis in this work.

Mobile users' correlated mobility and data consumption patterns often lead to
severe cellular network congestion in peak hours and hot spots. This paper
presents an optimal design of time and location aware mobile data pricing,
which incentivizes users to smooth traffic and reduce network congestion. We
derive the optimal pricing scheme through analyzing a twostage decision
process, where the operator determines the time and location aware prices by
minimizing his total cost in Stage I, and each mobile user schedules his mobile
traffic by maximizing his payoff (i.e., utility minus payment) in Stage II. We
formulate the twostage decision problem as a bilevel optimization problem, and
propose a derivativefree algorithm to solve the problem for any increasing
concave user utility functions. We further develop low complexity algorithms
for the commonly used logarithmic and linear utility functions. The optimal
pricing scheme ensures a winwin situation for the operator and users.
Simulations show that the operator can reduce the cost by up to 97.52% in the
logarithmic utility case and 98.70% in the linear utility case, and users can
increase their payoff by up to 79.69% and 106.10% for the two types of
utilities, respectively, comparing with a time and location independent pricing
benchmark. Our study suggests that the operator should provide price discounts
at less crowded time slots and locations, and the discounts need to be
significant when the operator's cost of provisioning excessive traffic is high
or users' willingness to delay traffic is low.

We study the downlink linear precoder design problem in a multicell dense
heterogeneous network (HetNet). The problem is formulated as a general
sumutility maximization (SUM) problem, which includes as special cases many
practical precoder design problems such as multicell coordinated linear
precoding, full and partial percell coordinated multipoint transmission,
zeroforcing precoding and joint BS clustering and beamforming/precoding. The
SUM problem is difficult due to its nonconvexity and the tight coupling of the
users' precoders. In this paper we propose a novel convex approximation
technique to approximate the original problem by a series of convex
subproblems, each of which decomposes across all the cells. The convexity of
the subproblems allows for efficient computation, while their decomposability
leads to distributed implementation. {Our approach hinges upon the
identification of certain key convexity properties of the sumutility
objective, which allows us to transform the problem into a form that can be
solved using a popular algorithmic framework called BSUM (Block Successive
UpperBound Minimization).} Simulation experiments show that the proposed
framework is effective for solving interference management problems in large
HetNet.

In this paper, we consider largescale linearly constrained composite convex
optimization problem, whose objective is a sum of a smooth function and a
possibly nonsmooth function. We propose a scalable
\textbf{F}rank\textbf{W}olfe based \textbf{A}ugmented \textbf{L}agrangian
(FWAL) method for solving this problem. At each iteration, the proposed FWAL
method employs the FW method (or its variants) to approximately solve the AL
subproblem {(with fixed Lagrange multiplier)} within a preselected tolerance
and then updates the Lagrange multiplier. The proposed FWAL method is well
suitable for solving largescale problems, because its computational cost per
step scales (essentially) linearly with the size of the input. We analyze the
nonergodic convergence rate of the proposed FWAL method.

In this paper, we consider the problem of computing the smallest enclosing
ball (SEB) of a set of $m$ balls in $\mathbb{R}^n,$ where the product $mn$ is
large. We first approximate the nondifferentiable SEB problem by its
logexponential aggregation function and then propose a computationally
efficient inexact NewtonCG algorithm for the smoothing approximation problem
by exploiting its special (approximate) sparsity structure. The key difference
between the proposed inexact NewtonCG algorithm and the classical NewtonCG
algorithm is that the gradient and the Hessianvector product are inexactly
computed in the proposed algorithm, which makes it capable of solving the
largescale SEB problem. We give an adaptive criterion of inexactly computing
the gradient/Hessian and establish global convergence of the proposed
algorithm. We illustrate the efficiency of the proposed algorithm by using the
classical NewtonCG algorithm as well as the algorithm from [Zhou. {et al.} in
Comput. Opt. \& Appl. 30, 147160 (2005)] as benchmarks.

In an interference limited network, joint power and admission control (JPAC)
aims at supporting a maximum number of links at their specified signal to
interference plus noise ratio (SINR) targets while using a minimum total
transmission power. Various convex approximation deflation approaches have been
developed for the JPAC problem. In this paper, we propose an effective
polynomial time nonconvex approximation deflation approach for solving the
problem. The approach is based on the nonconvex $\ell_q$minimization
approximation of an equivalent sparse $\ell_0$minimization reformulation of
the JPAC problem where $q\in(0,1).$ We show that, for any instance of the JPAC
problem, there exists a $\bar q\in(0,1)$ such that it can be exactly solved by
solving its $\ell_q$minimization approximation problem with any $q\in(0, \bar
q]$. We also show that finding the global solution of the $\ell_q$
approximation problem is NPhard. Then, we propose a potential reduction
interiorpoint algorithm, which can return an $\epsilon$KKT solution of the
NPhard $\ell_q$minimization approximation problem in polynomial time. The
returned solution can be used to check the simultaneous supportability of all
links in the network and to guide an iterative link removal procedure,
resulting in the polynomial time nonconvex approximation deflation approach
for the JPAC problem. Numerical simulations show that the proposed approach
outperforms the existing convex approximation approaches in terms of the number
of supported links and the total transmission power, particularly exhibiting a
quite good performance in selecting which subset of links to support.

Consider the cellular downlink Orthogonal Frequency Division Multiple Access
(OFDMA) system where a single transmitter transmits signals to multiple
receivers on multiple discrete subcarriers. To adapt fast channel fluctuations,
the transmitter should be able to dynamically allocate subcarrier and power
resources. Assuming perfect channel knowledge, we formulate the joint
subcarrier and power allocation problem as two optimization problems: the first
is the one of minimizing the total transmission power subject to quality of
service constraints, and the second is the one of maximizing a system utility
function subject to power budget constraints. In this letter, we show that both
the aforementioned formulations of the joint subcarrier and power allocation
problem are generally NPhard. We also identify several subclasses of the
problem which are polynomial time solvable.

The composite $L_q~(0<q<1)$ minimization problem over a general polyhedron
has received various applications in machine learning, wireless communications,
image restoration, signal reconstruction, etc. This paper aims to provide a
theoretical study on this problem. Firstly, we show that for any fixed $0<q<1$,
finding the global minimizer of the problem, even its unconstrained
counterpart, is strongly NPhard. Secondly, we derive KarushKuhnTucker (KKT)
optimality conditions for local minimizers of the problem. Thirdly, we propose
a smoothing sequential quadratic programming framework for solving this
problem. The framework requires a (approximate) solution of a convex quadratic
program at each iteration. Finally, we analyze the worstcase iteration
complexity of the framework for returning an $\epsilon$KKT point; i.e., a
feasible point that satisfies a perturbed version of the derived KKT optimality
conditions. To the best of our knowledge, the proposed framework is the first
one with a worstcase iteration complexity guarantee for solving composite
$L_q$ minimization over a general polyhedron.