Search

Consider the problem of minimizing a sum of convex composite functions over a decentralized network, where each agent in the network holds a private function consisting of a smooth part and a nonsmooth part, and it can only exchange information with its neighbors during the optimization process. One approach to tackling this problem is to study its penalized approximation. Although such an approximation becomes more accurate as the penalty parameter becomes smaller, it is well known that the penalized objective will also become more ill-conditioned, thereby causing the popular proximal gradient descent method to slow down substantially. To break this accuracy-speed tradeoff, we propose to solve the penalized approximation with the alternating direction method of multipliers (ADMM). We also exploit the composite structure of the private functions by linearizing the smooth parts and handling the nonsmooth parts with proximal operators, which allows us to further reduce the computational costs. The proposed penalty ADMM (abbreviated as PAD) is proven to be sublinearly convergent when the private functions are convex, and linearly convergent when in addition the smooth parts are strongly convex. We present numerical results to corroborate the theoretical analyses and to further demonstrate the advantages of PAD over existing state-of-the-art algorithms such as DL-ADMM, PG-EXTRA, and NIDS.

Many contemporary applications in signal processing and machine learning give rise to structured nonconvex nonsmooth optimization problems that can often be tackled by simple iterative methods quite effectively. One of the keys to understanding such a phenomenon-and, in fact, a very difficult conundrum even for experts-lies in the study of "stationary points" of the problem in question. Unlike smooth optimization, for which the definition of a stationary point is rather standard, there are myriad definitions of stationarity in nonsmooth optimization. In this article, we provide an introduction to different stationarity concepts for several important classes of nonconvex nonsmooth functions, discuss the geometric interpretations of these concepts, and further clarify their relationships. We then demonstrate the relevance of these constructions in some representative applications and indicate how they could affect the performance of iterative methods for addressing these applications.

Stochastic gradient descent (SGD) usually samples training data based on the uniform distribution, which may not be a good choice because of the high variance of its stochastic gradient. Thus, importance sampling methods are considered in the literature to improve the performance. Most previous work on SGD-based methods with importance sampling requires the knowledge of Lipschitz constants of all component gradients, which are in general difficult to estimate. In this paper, we study an adaptive importance sampling method for common SGD-based methods by exploiting the local first-order information without knowing any Lipschitz constants. In particular, we periodically changes the sampling distribution by only utilizing the gradient norms in the past few iterations. We prove that our adaptive importance sampling non-asymptotically reduces the variance of the stochastic gradients in SGD, and thus better convergence bounds than that for vanilla SGD can be obtained. We extend this sampling method to several other widely used stochastic gradient algorithms including SGD with momentum and ADAM. Experiments on common convex learning problems and deep neural networks illustrate notably enhanced performance using the adaptive sampling strategy.

In this paper, we aim at solving the cardinality constrained high-order portfolio optimization, i.e., mean-variance-skewness-kurtosis model with cardinality constraint (MVSKC). Optimization for the MVSKC model is of great difficulty in two parts. One is that the objective function is non-convex, the other is the combinational nature of the cardinality constraint, leading to non-convexity as well dis-continuity. Based on the observation that cardinality constraint has the difference-of-convex (DC) property, we transform the cardinality constraint into a penalty term and then propose three algorithms including the proximal difference of convex algorithm (pDCA), pDCA with extrapolation (pDCAe) and the successive convex approximation (SCA) to handle the resulting penalized MVSK (PMVSK) formulation. Moreover, theoretical convergence results of these algorithms are established respectively. Numerical experiments on the real datasets demonstrate the superiority of our proposed methods in obtaining high utility and sparse solutions as well as efficiency in terms of time usage., ICASSP 2021

This paper proposes a penalty alternating direction method of multipliers (ADMM) to minimize the summation of convex composite functions over a decentralized network. Each agent in the network holds a private function consisting of a smooth part and a nonsmooth part, and can only exchange information with its neighbors during the optimization process. We consider a penalized approximation of the decentralized optimization problem; but unlike the existing penalty methods, here the penalty parameter can be very small such that the approximation error is negligible. On the other hand, the small penalty parameter makes the penalized objective ill-conditioned, such that the popular proximal gradient descent method has to use a small step size, and is hence slow. To address this issue, we propose to solve the penalized formulation with ADMM. We further utilize the composite structures of the private functions through linearizing the smooth parts so as to reduce computational costs, and handling the nonsmooth parts with proximal operators. The proposed penalty ADMM (abbreviated as PAD) is provably convergent when the private functions are convex, and linearly convergent when the smooth parts are further strongly convex. Numerical experiments corroborate the theoretical analyses, and demonstrate the advantages of PAD over existing state-of-the-art algorithms, such as DL-ADMM, PG-EXTRA and NIDS.

Variable selection is one of the most important tasks in statistics and machine learning. To incorporate more prior information about the regression coefficients, various constrained Lasso models have been proposed in the literature. Compared with the classic (unconstrained) Lasso model, the algorithmic aspects of constrained Lasso models are much less explored. In this paper, we demonstrate how the recently developed semis-mooth Newton-based augmented Lagrangian framework can be extended to solve a linear equality-constrained Lasso model. A key technical challenge that is not present in prior works is the lack of strong convexity in our dual problem, which we overcome by adopting a regularization strategy. We show that under mild assumptions, our proposed method will converge superlinearly. Moreover, extensive numerical experiments on both synthetic and real-world data show that our method can be substantially faster than existing first-order methods while achieving a better solution accuracy.

In this paper, we consider a device-to-device (D2D) network underlying a cellular system wherein the densely deployed D2D user devices can act as wireless relays for a distant transceiver pair. We aim to devise a beamforming strategy for the relays that maximizes the data rate of the distant transceiver while satisfying interference constraints at the cellular receivers. Towards that end, we first formulate a beamforming problem whose solution is robust against the channel uncertainties in the relay-destination hop. Motivated by practical observations, we assume that the random channels in this hop follow unimodal distributions and propose a novel unimodal distributionally robust model to capture the channel uncertainties. Then, we extend the formulation so that it can also guard against the channel uncertainty in the source-relay hop under the worst case robust model. The resulting robust beamforming problem is generally non-convex and intractable. Therefore, we design an iterative algorithm, which is based on solving semidefinite programs, to find an approximate solution to it. Simulation results show that under mild conditions, our robust model significantly improves the throughput of D2D relay transmissions when compared with the conventional robust models that merely rely on the channels’ moment information. It also outperforms the Bernstein-type inequality-based convex approximation, which assumes that the channel follows a Gaussian distribution.

This paper concentrates on a robust transmit optimization problem for the multiuser multi-input single-output (MISO) downlink scenario and under inaccurate channel state information (CSI). This robust problem deals with a general-rank transmit covariance design, and it follows a safe rate-constrained formulation under spherically bounded CSI uncertainties. Curiously, simulation results in previous works suggested that the robust problem admits rank-one optimal transmit covariances in most cases. Such a numerical finding is appealing because transmission with rank-one covariances can be easily realized by single-stream transmit beamforming. This gives rise to a fundamentally important question, namely, whether we can theoretically identify conditions under which the robust problem admits a rank-one solution. In this paper, we identify one such condition. Simply speaking, we show that the robust problem is guaranteed to admit a rank-one solution if the CSI uncertainties are not too large and the multiuser channel is not too poorly conditioned. To establish the aforementioned condition, we develop a novel duality framework, through which an intimate relationship between the robust problem and a related maximin problem is revealed. Our condition involves only a simple expression with respect to the multiuser channel and other system parameters. In particular, unlike other sufficient rank-one conditions that have appeared in the literature, ours is verifiable. The application of our analysis framework to several other CSI uncertainty models is also discussed., To appear in IEEE Trans. Signal Process. This version combines the main manuscript and its accompanied supplementary report into one single article

In this paper, we consider the large-scale case of the robust beamforming problem with interference temperature constraints. Previous semidefinite relaxation (SDR) method becomes impracticable because of its expensive computational cost. Even successive convex approximation (SCA) method, the state-of-the-art method, cannot tackle this problem efficiently. Thus, we are motivated to design two efficient first-order methods, multi-block alternating direction method of multipliers (ADMM) and linear programming-assisted subgradient descent (LPA-SD), to solve it. Numerical results demonstrate the potential of our proposed methods in terms of both computational efficiency and solution quality.

In this paper, we develop a novel robust optimization approach to source localization using time-difference-of-arrival (TDOA) measurements that are collected under non-line-of-sight (NLOS) conditions. A key feature of our approach is that it does not require knowledge of the distribution or statistics of the NLOS errors, which are often difficult to obtain in practice. Instead, it only assumes that the NLOS errors have bounded supports. Based on this assumption, we formulate the TDOA-based source localization problem as a robust least squares (RLS) problem, in which a location estimate that is robust against the NLOS errors is sought. Since the RLS problem is non-convex, we propose two efficiently implementable convex relaxation-based approximation methods to tackle it. We then conduct a thorough theoretical analysis of the approximation quality and computational complexity of these two methods. In particular, we establish conditions under which they will yield a unique localization of the source. Simulation results on both synthetic and real data show that the performance of our approach under various NLOS settings is very stable and is significantly better than that of several existing non-robust approaches.

We consider the joint admission control and multicast downlink beamforming (JABF) problem, which is a fundamental problem in signal processing and admits a natural mixed-integer quadratically constrained quadratic program (MIQCQP) formulation. One popular approach to tackling such MIQCQP formulation is to develop convex relaxations of both the binary and continuous variables. However, most existing convex relaxations impose rather weak relationships between the binary and continuous variables and thus do not yield high-performance solutions. To overcome this weakness, we propose to keep the binary constraints intact and apply the semidefinite relaxation (SDR) technique to continuous variables. Although the resulting relaxation takes the form of a mixed-integer semidefinite program (MISDP) and is theoretically intractable in general, by exploiting the fact that such MISDP arises as a mixed-integer SDR of an MIQCQP and harnessing recent computational advances in solving large-scale mixed-integer second-order cone programming (MISOCP) problems, we develop a novel, practically efficient algorithm that provably converges to an optimal solution to the MISDP in a finite number of steps. The key idea of our algorithm is to construct successively tighter second-order cone (SOC) outer approximations of the constraints in the MISDP and solve a sequence of MISOCPs to obtain an optimal solution to the MISDP. Our work also provides, to the best of our knowledge, the first general framework for solving MISDPs that arise as mixed-integer SDRs of MIQCQPs. Next, we show that by applying a Gaussian randomization procedure to the optimal solution to the MISDP, we obtain a feasible solution to the JABF problem whose approximation accuracy is on the order of M, the number of users in the network. This improves upon the approximation accuracy guarantee of an existing convex relaxation method. Lastly, we present numerical results to demonstrate the viability of our proposed approach.

This letter considers multi-input single-output (MISO) downlink multicasting with finite-alphabet inputs when perfect channel state information is known at the transmitter. Two advanced transmit schemes, namely the beamformed (BF) Alamouti scheme and the stochastic beamforming (SBF) scheme, for maximizing the finite-alphabet-constrained multicast rate are studied. We show that the transmit optimization for these two schemes can be formulated as an SNR-based max-min-fair (MMF) problem with Gaussian inputs, which can be handled via the semidefinite relaxation (SDR) technique. Apart from transmit optimization, we analyzed the rate performance of the two schemes. Our analytical results show that for BF Alamouti, the multicast rate degrades with the number of users $M$ at a rate of $\sqrt M $ , which is better than the traditional transmit beamforming scheme. For SBF, the multicast rate degradation is less sensitive to the increase in the number of users and outperforms BF Alamouti for large $M$ . All the results were verified by numerical simulations.

Unlike dimensionality reduction (DR) tools for single-view data, e.g., principal component analysis (PCA), canonical correlation analysis (CCA) and generalized CCA (GCCA) are able to integrate information from multiple feature spaces of data. This is critical in multi-modal data fusion and analytics, where samples from a single view may not be enough for meaningful DR. In this work, we focus on a popular formulation of GCCA, namely, MAX-VAR GCCA. The classic MAX-VAR problem is optimally solvable via eigen-decomposition, but this solution has serious scalability issues. In addition, how to impose regularizers on the sought canonical components was unclear - while structure-promoting regularizers are often desired in practice. We propose an algorithm that can easily handle datasets whose sample and feature dimensions are both large by exploiting data sparsity. The algorithm is also flexible in incorporating regularizers on the canonical components. Convergence properties of the proposed algorithm are carefully analyzed. Numerical experiments are presented to showcase its effectiveness.

In this work, we consider the robust beamforming design for secondary downlink multicasting channels, where primary users are present with norm-bounded channel errors. In particular, the max-min-fair formulation is considered and the resulting design problem is a quadratically constrained quadratic program (QCQP) with a set of semi-infinite constraints, which is NP-hard in general. As a remedy, we apply the semidefinite relaxation (SDR) technique and S-lemma to approximate the problem into a tractable form. The key contribution of this paper is to study the approximation quality. Our analytical results show that, the SDR solution achieves an objective value that is at least Ω(1/MN log J) times the optimal objective value, where M is the number of secondary users, J is the number of primary users, and N is the number of antennas at the secondary base station. This is a fundamentally new result for SDR applied to robust QCQPs. Practically, it provides a performance guarantee for the robust beamforming design. All these results are verified by our numerical simulations.

Consider a multi-input multi-output (MIMO) channel wiretapped by multiple multi-antenna eavesdroppers. Assuming imperfect eavesdroppers' channel state information (CSI) at the transmitter, an outage-constrained secrecy rate maximization (OC-SRM) problem is considered. Specifically, we aim to design the transmit covariance matrix such that the outage secrecy rate is maximized for a given outage probability. The OC-SRM problem is challenging, and as a compromise, we resort to a recently developed Bernstein-type inequality approach to obtain a safe (conservative) approximate solution for OC-SRM. The merit of the proposed safe design lies in its tractability. In particular, a safe solution can be efficiently computed by alternately solving two convex conic optimization problems. The efficacy of the proposed design is demonstrated by simulations.

We consider a wireless network with densely deployed user devices (e.g., a device-to-device or wireless sensor network) underlaying a cellular system, in which some user devices act as relays to facilitate data transmissions between a distant transceiver pair under imperfect channel information. Motivated by the observation that most of the channel distributions are unimodal, we formulate a novel distributionally robust beamforming problem, in which the random channel coefficient follows a class of unimodal distribution with known first- and second-order moments. Our design objective is to maximize the worst-case signal-to-noise ratio (SNR) at the dedicated user device while satisfying a probabilistic interference constraint at the cellular user equipment (CUE). Though such a unimodal distributionally robust (UDR) beamforming problem is non-convex, we show that an approximate solution can be computed efficiently using semidefinite programming. Our simulation results show that under mild conditions, the UDR model yields significant beamforming performance improvement over conventional robust models that merely rely on first- and second-order moments of the channel distribution.

Generalized canonical correlation analysis (GCCA) aims at finding latent low-dimensional common structure from multiple views (feature vectors in different domains) of the same entities. Unlike principal component analysis (PCA) that handles a single view, (G)CCA is able to integrate information from different feature spaces. Here we focus on MAX-VAR GCCA, a popular formulation which has recently gained renewed interest in multilingual processing and speech modeling. The classic MAX-VAR GCCA problem can be solved optimally via eigen-decomposition of a matrix that compounds the (whitened) correlation matrices of the views; but this solution has serious scalability issues, and is not directly amenable to incorporating pertinent structural constraints such as non-negativity and sparsity on the canonical components. We posit regularized MAX-VAR GCCA as a non-convex optimization problem and propose an alternating optimization (AO)-based algorithm to handle it. Our algorithm alternates between {\em inexact} solutions of a regularized least squares subproblem and a manifold-constrained non-convex subproblem, thereby achieving substantial memory and computational savings. An important benefit of our design is that it can easily handle structure-promoting regularization. We show that the algorithm globally converges to a critical point at a sublinear rate, and approaches a global optimal solution at a linear rate when no regularization is considered. Judiciously designed simulations and large-scale word embedding tasks are employed to showcase the effectiveness of the proposed algorithm.

In this paper, we consider the robust beamforming design in a device-to-device (D2D) two-hop one-way relay network. Specifically, we study the amplify-and-forward (AF) scheme in the scenario where both the transmitter-to-relays link and relays-to-receiver link are subject to estimation errors. Assuming that those errors lie in a ball with bounded radius, the resulting design problem can be formulated as a semi-infinite program (SIP) that involves high-degree polynomial inequality constraints, which is difficult to deal with in general. In this paper, we employ the semidefinite relaxation (SDR) technique and tools from polynomial optimization to construct a safe approximation of the aforementioned SIP. Furthermore, we propose an alternating algorithm to tackle the safe approximation. To the best of our knowledge, our work is the first to provide an efficient algorithmic approach to the aforementioned robust beamforming design problem. In addition, our numerical results show that the proposed robust beamforming design is more reliable than the non-robust counterpart, and it can achieve better signal-to-noise ratios (SNRs) than the existing linear approximation approach, which ignores error terms with degree higher than one.

We consider the problem of geolocating two unknown co-channel emitters by a cluster of formation-flying satellites using both time difference of arrival (TDOA) and frequency difference of arrival (FDOA) measurements. As the association between the TDOA/FDOA measurements obtained by each pair of satellites and the corresponding emitters is typically not known, the emitter-measurement association and the emitters' locations need to be jointly estimated. In this paper, we first formulate the joint estimation problem as a mixed integer nonlinear optimization problem. Then, we propose a semidefinite relaxation-based approach to tackle the problem and demonstrate its efficacy via simulations.

The wide applicability of chance-constrained programming, together with advances in convex optimization and probability theory, has created a surge of interest in finding efficient methods for processing chance constraints in recent years. One of the successes is the development of so-called safe tractable approximations of chance-constrained programs, where a chance constraint is replaced by a deterministic and efficiently computable inner approximation. Currently, such an approach applies mainly to chance-constrained linear inequalities, in which the data perturbations either are independent or define a known covariance matrix. However, its applicability to chance-constrained conic inequalities with dependent perturbations---which arises in finance, control, and signal processing applications---remains largely unexplored. In this paper, we develop safe tractable approximations of chance-constrained affinely perturbed linear matrix inequalities, in which the perturbations are not necessarily independent,...

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. Consequently, we obtain a rather complete answer to a question raised by Tseng. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems., 32 pages

In this article, we have provided general, comprehensive coverage of the SDR technique, from its practical deployments and scope of applicability to key theoretical results. We have also showcased several representative applications, namely MIMO detection, B? shimming in MRI, and sensor network localization. Another important application, namely downlink transmit beamforming, is described in [1]. Due to space limitations, we are unable to cover many other beautiful applications of the SDR technique, although we have done our best to illustrate the key intuitive ideas that resulted in those applications. We hope that this introductory article will serve as a good starting point for readers who would like to apply the SDR technique to their applications, and to locate specific references either in applications or theory.

Owing to their high accuracy and ease of formulation, there has been great interest in applying convex optimization techniques, particularly that of semidefinite programming (SDP) relaxation, to tackle the sensor network localization problem in recent years. However, a drawback of such techniques is that the resulting convex program is often expensive to solve. In order to speed up computation, various edge sparsification heuristics have been proposed, whose aim is to reduce the number of edges in the input graph. Although these heuristics do reduce the size of the convex program and hence make it faster to solve, they are often ad hoc in nature and do not preserve the localization properties of the input. As such, one often has to face a tradeoff between solution accuracy and computational effort. In this paper, we propose a novel edge sparsification heuristic that can provably preserve the localization properties of the original input. At the heart of our heuristic is a graph decomposition procedure, which allows us to identify certain sparse generically universally rigid subgraphs of the input graph. Our computational results show that the proposed approach can significantly reduce the computational and memory complexities of SDP-based algorithms for solving the sensor network localization problem. Moreover, it compares favorably with existing speedup approaches, both in terms of accuracy and solution time.

In this paper, we consider various moment inequalities for sums of random matrices—which are well-studied in the functional analysis and probability theory literature—and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine’s inequality in functional analysis. Using this result, we show that an SDP-based algorithm of Nemirovski, which is developed for solving a class of quadratic optimization problems with orthogonality constraints, has a logarithmic approximation guarantee. This improves upon the polynomial approximation guarantee established earlier by Nemirovski. Furthermore, we obtain improved safe tractable approximations of a certain class of chance constrained linear matrix inequalities. Secondly, we consider a recent result of Delage and Ye on the so-called data-driven distributionally robust stochastic programming problem. One of the assumptions in the Delage–Ye result is that the underlying probability distribution has bounded support. However, using a suitable moment inequality, we show that the result in fact holds for a much larger class of probability distributions. Given the close connection between the behavior of sums of random matrices and the theoretical properties of various optimization problems, we expect that the moment inequalities discussed in this paper will find further applications in optimization.

Most of the recent work on 2-stage stochastic combinatorial optimization problems has focused on minimization of the expected cost or the worst-case cost of the solution. Those two objectives can be viewed as two extreme ways of handling risk. In this paper we propose to use a one-parameter family of functionals to interpolate between them. Although such a family has been used in the mathematical finance and stochastic programming literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, a broad class of risk-adjusted 2-stage stochastic programs can be efficiently treated by the sample average approximation (SAA) method. In particular, our result shows that it is computationally feasible to incorporate some degree of robustness even when the underlying distribution can only be accessed in a black-box fashion. We also show that when combined with suitable rounding procedures, our result yields new approximation algorithms for many risk-adjusted 2-stage stochastic combinatorial optimization problems under the black-box setting.

This paper considers robust transmit beamforming for multiuser multi-input single-output (MISO) downlink transmission, where imperfect channel state information (CSI) is assumed at the base station (BS). The imperfect CSI is captured by a moment-based random error model, in which the BS knows only the mean and covariance of each CSI error, but not the exact distribution. Under this error model, we formulate a distributionally robust beamforming (DRB) problem, in which the total transmit power at the BS is to be minimized, while each user's SINR outage probability, evaluated w.r.t. any distribution with the given mean and covariance, is kept below a given threshold. The DRB problem is a semi-infinite chance-constrained problem. By employing recent results in distributionally robust optimization, we show that the DRB problem admits an explicit conic reformulation, which can be conveniently turned into a convex optimization problem after semidefinite relaxation (SDR). We also consider the case where the mean and covariance are not perfectly known. We show that the resulting DRB problem still admits a conic reformulation and can be approximately solved using SDR. The robustness of the proposed designs are demonstrated by numerical simulations.

In this paper, we consider an outage-based robust beamforming problem in two-way relay networks under the imperfect channel state information (CSI) scenario. Specficially, our goal is to minimize the relay transmit power while keeping the probability of each user's signal-to-interference-plus-noise ratio (SINR) outage as caused by the imperfect CSI below a given threshold. Assuming that the CSI errors follow a complex Gaussian distribution, the probabilistic SINR constraints involve quartic polynomials of complex Gaussian random variables, which, to the best of our knowledge, have not been treated from a computational perspective before. Using moment inequalities for Gaussian polynomials and the semidefinite relaxation technique, we propose a new tractable approximation approach for tackling such constraints. Simulation results show that the proposed method outperforms the existing robust approaches when the CSI errors are large.

We identify and address algorithmic and game-theoretic issues arising from welfare maximization in the well-studied two-stage stochastic optimization framework. In contrast, prior work in algorithmic mechanism design has focused almost exclusively on optimization problems without uncertainty. We show both positive results, by demonstrating a mechanism that implements the social welfare maximizer in sequential ex post equilibrium, and also negative results, by showing the impossibility of dominant-strategy implementation. In this letter, we describe the relationship between mechanism design and stochastic optimization, and highlight our key technical results. An extended abstract will appear in WINE 2007, and a journal version is under preparation.

The successful deployment and operation of location-aware networks, which have recently found many applications, depends crucially on the accurate localization of the nodes. Currently, a powerful approach to localization is that of convex relaxation. In a typical application of this approach, the localization problem is first formulated as a rank-constrained semidefinite program (SDP), where the rank corresponds to the target dimension in which the nodes should be localized. Then, the non-convex rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this paper, we explore the use of a non-convex surrogate of the rank function, namely the so-called Schatten quasi- norm, in network localization. Although the resulting optimization problem is non-convex, we show, for the first time, that a first- order critical point can be approximated to arbitrary accuracy in polynomial time by an interior-point algorithm. Moreover, we show that such a first-order point is already sufficient for recovering the node locations in the target dimension if the input instance satisfies certain established uniqueness properties in the literature. Finally, our simulation results show that in many cases, the proposed algorithm can achieve more accurate localization results than standard SDP relaxations of the problem.

In physical-layer multicasting over a multiuser MISO downlink channel, transmit beamforming using semidefinite relaxation (SDR) has been a popular approach. In this paper, we propose a rank-2 transmit beamformed Alamouti space-time code scheme, which may be seen as a generalization of the previous SDR-based beamforming framework. The beamforming problem arising from the proposed scheme is a rank-2 constrained semidefinite program (SDP).We deal with it using the SDR technique, but this time using rank-2 approximation rather than rank-1 approximation in the previous transmit beamforming. An analysis on the worst-case approximation accuracy of the rank-2 SDR approximation is provided, which reveals that the approximation accuracy degrades at a rate of √M, where M is the number of users served. This improves upon the case of transmit beamforming, where the worst-case approximation accuracy degrades at the higher rate of M. Simulation results further show that the proposed scheme performs better than the transmit beamforming scheme.

Consider a scenario in which an MISO channel is overheard by multiple single-antenna eavesdroppers. The transmitter has perfect channel state information (CSI) with the legitimate channel, but has imperfect CSI with the eavesdroppers' channels. The CSI uncertainties are assumed stochastic. We formulate an artificial-noise (AN)-aided secrecy-rate maximization problem where the CSI uncertainties are handled using an outage-based formulation. Our aim is to find, for this problem, tractable designs for the transmit and AN covariances. Unfortunately, outage-based optimization problems are generally difficult to solve. The main contribution here is to derive a safe, convex optimization-based, approximation to the considered problem. The advantages of the method are shown by simulations.

This paper considers the problem of low complexity implementation of high-performance semidefinite relaxation (SDR) MIMO detection methods. Currently, most SDR MIMO detectors are implemented using interior-point methods. Although such implementations have worst-case polynomial complexity (approximately cubic in the problem size), they can be quite computationally costly in practice. Here we depart from the interior-point method framework and investigate the use of other low per-iteration-complexity techniques for SDR MIMO detection. Specifically, we employ the row-by-row (RBR) method, which is a particular version of block coordinate descent, to solve the semidefinite programs that arise in the SDR MIMO context with an emphasis on the QPSK scenario. In each iteration of the RBR method, only matrix-vector multiplications are needed, and hence it can be implemented in a very efficient manner. Our simulation results show that the RBR method can indeed offer a significant speedup in runtime, while providing bit error rate performance on par with the interior-point methods.

Owing to its versatile model power and wide applicability, semidefinite programming (SDP) has received a lot of attention of late in many communities. In this article, we will survey some recent applications of SDP, with a particular emphasis on semidefinite relaxations of hard optimization problems. We will also provide pointers to the literature, for further reading. Keywords: semidefinite programming; semidefinite relaxation; quadratic optimization; polynomial optimization; chance-constrained optimization; approximation algorithms

In this paper we consider a probabilistic signal-to-interference and-noise ratio (SINR) constrained problem for transmit beamforming design in the presence of imperfect channel state information (CSI), under a multiuser multiple-input single-output (MISO) downlink scenario. In particular, we deal with outage-based quality-of-service constraints, where the probability of each user's SINR not satisfying a service requirement must not fall below a given outage probability specification. The study of solution approaches to the probabilistic SINR constrained problem is important because CSI errors are often present in practical systems and they may cause substantial SINR outages if not handled properly. However, a major technical challenge is how to process the probabilistic SINR constraints. To tackle this, we propose a novel relaxation- restriction (RAR) approach, which consists of two key ingredients-semidefinite relaxation (SDR), and analytic tools for conservatively approximating probabilistic constraints. The underlying goal is to establish approximate probabilistic SINR constrained formulations in the form of convex conic optimization problems, so that they can be readily implemented by available solvers. Using either an intuitive worst-case argument or specialized probabilistic results, we develop various conservative approximation schemes for processing probabilistic constraints with quadratic uncertainties. Consequently, we obtain several RAR alternatives for handling the probabilistic SINR constrained problem. Our techniques apply to both complex Gaussian CSI errors and i.i.d. bounded CSI errors with unknown distribution. Moreover, results obtained from our extensive simulations show that the proposed RAR methods significantly improve upon existing ones, both in terms of solution quality and computational complexity.

Recently, robust transmit beamforming has drawn considerable attention because it can provide guaranteed receiver performance in the presence of channel state information (CSI) errors. Assuming complex Gaussian distributed CSI errors, this paper investigates the robust beamforming design problem that minimizes the transmission power subject to probabilistic signal-to-interference-plus-noise ratio (SINR) constraints. The probabilistic SINR constraints in general have no closed-form expression and are difficult to handle. Based on a Bernstein-type inequality of complex Gaussian random variables, we propose a conservative formulation to the robust beamforming design problem. The semidefinite relaxation technique can be applied to efficiently handle the proposed conservative formulation. Simulation results show that, in comparison with the existing methods, the proposed method is more power efficient and is able to support higher target SINR values for receivers., This paper has been withdrawn by the authors

In this paper, we study the optimal secondary-link beamforming pattern that balances between the SU's throughput and the interference it causes to PUs in MIMO cognitive radio networks. In particular, we aim to maximize the throughput of the SU, while keeping the interference temperature at the primary receivers below a certain threshold. Unlike traditional MIMO systems, SUs may not have the luxury of knowing the channel state information (CSI) on the links to PUs. This presents a key challenge for a secondary transmitter to steer interference away from primary receivers. In this paper, we consider three scenarios, namely when the secondary transmitter has complete, partial, or no knowledge about the channels to the primary receivers. In particular, when complete CSI is not available, the interference-temperature constraints are to be satisfied with high probability, thus resulting in chance constraints that are typically hard to deal with. Our contribution is fourfold. First, by analyzing the distributional characteristics of MIMO channels, we propose a unified homogeneous QCQP formulation that can be applied to all three scenarios. The homogeneous QCQP formulation, though non-convex, is amenable to semidefinite programming (SDP) relaxation methods. Secondly, we show that the SDP relaxation admits no gap when the number of primary links is no larger than two. Thirdly, we propose a randomized polynomial-time algorithm for constructing a near-optimal solution to the QCQP problem when there are more than two primary links. Finally, we show that when the secondary transmitter has no CSI on the links to primary receivers, the optimal solution to the QCQP problem can be found by a simple matrix eigenvalue-eigenvector computation, which can be done much more efficiently than solving the QCQP directly., 12 pages 6 Figures

We study the problem of welfare maximization in a novel setting motivated by the standard stochastic two-stage optimization with recourse model. We identify and address algorithmic and game-theoretic challenges that arise from this framework. In contrast, prior work in algorithmic mechanism design has focused almost exclusively on optimization problems without uncertainty. We make two kinds of contributions. First, we introduce a family of mechanisms that induce truthtelling in general two-stage stochastic settings. These mechanisms are not simple extensions of VCG mechanisms, as the latter do not readily address incentive issues in multi-stage settings. Our mechanisms implement the welfare maximizer in sequential ex post equilibrium for risk-neutral agents. We provide formal evidence that this is the strongest implementation one can expect. Next, we investigate algorithmic issues by studying a novel combinatorial optimization problem called the Coverage Cost problem, which includes the well-studied Fixed-Tree Multicast problem as a special case. We note that even simple instances of the stochastic variant of this problem are #P-Hard. We propose an algorithm that approximates optimal welfare with high probability, using a combination of sampling and supermodular set function maximization--the techniques may be of independent interest. To the best of our knowledge, our work is the first to address both game-theoretic and algorithmic challenges of mechanism design in multi-stage settings with data uncertainty.

Due to their wide applicability and versatile modeling power, stochastic programming problems have received a lot of attention in many communities. In particular, there has been substantial recent interest in 2–stage stochastic combinatorial optimization problems. Two objectives have been considered in recent work: one sought to minimize the expected cost, and the other sought to minimize the worst–case cost. These two objectives represent two extremes in handling risk — the first trusts the average, and the second is obsessed with the worst case. In this paper, we interpolate between these two extremes by introducing an one–parameter family of functionals. These functionals arise naturally from a change of the underlying probability measure and incorporate an intuitive notion of risk. Although such a family has been used in the mathematical finance [11] and stochastic programming [13] literature before, its use in the context of approximation algorithms seems new. We show that under standard assumptions, our risk–adjusted objective can be efficiently treated by the Sample Average Approximation (SAA) method [9]. In particular, our result generalizes a recent sampling theorem by Charikar et al. [2], and it shows that it is possible to incorporate some degree of robustness even when the underlying probability distribution can only be accessed in a black–box fashion. We also show that when combined with known techniques (e.g. [4,14]), our result yields new approximation algorithms for many 2–stage stochastic combinatorial optimization problems under the risk–adjusted setting.