44 results on '"So, Anthony Man-Cho"'
Search Results
2. A Penalty Alternating Direction Method of Multipliers for Convex Composite Optimization Over Decentralized Networks
- Author
-
Qing Ling, Huikang Liu, Anthony Man-Cho So, and Jiaojiao Zhang
- Subjects
Mathematical optimization ,Computer science ,Composite optimization ,Signal Processing ,Convergence (routing) ,Process (computing) ,Regular polygon ,Function (mathematics) ,Electrical and Electronic Engineering ,Decentralized network ,Gradient descent ,Convex function - Abstract
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.
- Published
- 2021
3. Hardness and approximation results for [L.sub.p]-ball constrained homogeneous polynomial optimization problems
- Author
-
Hou, Ke and So, Anthony Man-Cho
- Subjects
Mathematical optimization ,Polynomials -- Research ,Mathematical research ,Algorithms -- Research ,Algorithm ,Business ,Computers and office automation industries ,Mathematics - Abstract
In this paper, we establish hardness and approximation results for various [L.sub.p]-ball constrained homogeneous polynomial optimization problems, where p [member of] [2, [infinity]]. Specifically, we prove that for any given [...]
- Published
- 2014
- Full Text
- View/download PDF
4. Understanding Notions of Stationarity in Nonsmooth Optimization: A Guided Tour of Various Constructions of Subdifferential for Nonsmooth Functions
- Author
-
Jiajin Li, Anthony Man-Cho So, and Wing-Kin Ma
- Subjects
Mathematical optimization ,Optimization problem ,Iterative method ,Computer science ,Applied Mathematics ,020206 networking & telecommunications ,02 engineering and technology ,Subderivative ,Stationary point ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Relevance (information retrieval) ,Minification ,Electrical and Electronic Engineering ,Convex function ,Simple (philosophy) - Abstract
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.
- Published
- 2020
5. Low-Cost Lipschitz-Independent Adaptive Importance Sampling of Stochastic Gradients
- Author
-
Xiaolu Wang, Huikang Liu, Anthony Man-Cho So, and Jiajin Li
- Subjects
Mathematical optimization ,021103 operations research ,Uniform distribution (continuous) ,Adaptive sampling ,Artificial neural network ,Computer science ,business.industry ,0211 other engineering and technologies ,02 engineering and technology ,010501 environmental sciences ,Lipschitz continuity ,01 natural sciences ,Stochastic gradient descent ,Sampling distribution ,Convergence (routing) ,Artificial intelligence ,business ,Importance sampling ,0105 earth and related environmental sciences - Abstract
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.
- Published
- 2021
6. Sparse High-Order Portfolios via Proximal DCA and SCA
- Author
-
Taoli Zheng, Zengde Deng, Anthony Man-Cho So, and Jinxin Wang
- Subjects
Mathematical optimization ,Linear programming ,Computer science ,Extrapolation ,Approximation algorithm ,Constraint (information theory) ,FOS: Economics and business ,Cardinality ,Portfolio Management (q-fin.PM) ,Optimization and Control (math.OC) ,Convergence (routing) ,FOS: Mathematics ,Portfolio optimization ,PDCA ,Mathematics - Optimization and Control ,Quantitative Finance - Portfolio Management - Abstract
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
- Published
- 2020
7. A Penalty Alternating Direction Method of Multipliers for Decentralized Composite Optimization
- Author
-
Qing Ling, Jiaojiao Zhang, and Anthony Man-Cho So
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,Computer science ,Composite optimization ,Process (computing) ,Regular polygon ,020206 networking & telecommunications ,02 engineering and technology ,Function (mathematics) ,020901 industrial engineering & automation ,Approximation error ,0202 electrical engineering, electronic engineering, information engineering ,Penalty method ,Gradient descent ,Convex function - Abstract
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.
- Published
- 2020
8. An Efficient Augmented Lagrangian-Based Method for Linear Equality-Constrained Lasso
- Author
-
Zengde Deng, Man-Chung Yue, and Anthony Man-Cho So
- Subjects
Mathematical optimization ,021103 operations research ,Augmented Lagrangian method ,Computer science ,MathematicsofComputing_NUMERICALANALYSIS ,0211 other engineering and technologies ,Duality (optimization) ,Feature selection ,02 engineering and technology ,01 natural sciences ,Regularization (mathematics) ,Convexity ,010104 statistics & probability ,Lasso (statistics) ,Linear regression ,Key (cryptography) ,0101 mathematics - Abstract
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.
- Published
- 2020
9. Distributionally Robust Collaborative Beamforming in D2D Relay Networks With Interference Constraints
- Author
-
Xiaoxia Huang, Anthony Man-Cho So, Shimin Gong, and Sissi Xiaoxiao Wu
- Subjects
Beamforming ,0209 industrial biotechnology ,Mathematical optimization ,Computer science ,Iterative method ,Gaussian ,Data_CODINGANDINFORMATIONTHEORY ,02 engineering and technology ,law.invention ,symbols.namesake ,020901 industrial engineering & automation ,Relay ,law ,Robustness (computer science) ,Computer Science::Networking and Internet Architecture ,0202 electrical engineering, electronic engineering, information engineering ,Wireless ,Electrical and Electronic Engineering ,Computer Science::Information Theory ,business.industry ,Applied Mathematics ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,020206 networking & telecommunications ,Computer Science Applications ,symbols ,business ,Communication channel - Abstract
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.
- Published
- 2017
10. Unraveling the Rank-One Solution Mystery of Robust MISO Downlink Transmit Optimization: A Verifiable Sufficient Condition via a New Duality Result
- Author
-
Jiaxian Pan, Wing-Kin Ma, Anthony Man-Cho So, and Tsung-Hui Chang
- Subjects
FOS: Computer and information sciences ,Beamforming ,Mathematical optimization ,021103 operations research ,Optimization problem ,Information Theory (cs.IT) ,Computer Science - Information Theory ,0211 other engineering and technologies ,Duality (optimization) ,020206 networking & telecommunications ,Data_CODINGANDINFORMATIONTHEORY ,02 engineering and technology ,Minimax ,Precoding ,Channel state information ,Bounded function ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Verifiable secret sharing ,Electrical and Electronic Engineering ,Computer Science::Information Theory ,Mathematics - Abstract
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
- Published
- 2017
11. Fast First-order Methods for the Massive Robust Multicast Beamforming Problem with Interference Temperature Constraints
- Author
-
Peng Wang, Anthony Man-Cho So, and Huikang Liu
- Subjects
Beamforming ,Mathematical optimization ,Linear programming ,Multicast ,Computer science ,020206 networking & telecommunications ,02 engineering and technology ,First order ,Interference (wave propagation) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Relaxation (approximation) ,Subgradient method ,Descent (mathematics) - Abstract
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.
- Published
- 2019
12. Robust Convex Approximation Methods for TDOA-Based Localization Under NLOS Conditions
- Author
-
Youming Li, Anthony Man-Cho So, and Gang Wang
- Subjects
Mathematical optimization ,Noise measurement ,Computational complexity theory ,010401 analytical chemistry ,Robust optimization ,020206 networking & telecommunications ,02 engineering and technology ,Multilateration ,01 natural sciences ,0104 chemical sciences ,Non-line-of-sight propagation ,Robustness (computer science) ,Bounded function ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Measurement uncertainty ,Electrical and Electronic Engineering ,Mathematics - Abstract
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.
- Published
- 2016
13. Mixed-Integer Semidefinite Relaxation of Joint Admission Control and Beamforming: An SOC-Based Outer Approximation Approach with Provable Guarantees
- Author
-
Anthony Man-Cho So and Sherry Xue-Ying Ni
- Subjects
Beamforming ,Sequence ,Mathematical optimization ,Quadratically constrained quadratic program ,Computer science ,Gaussian ,Approximation algorithm ,020206 networking & telecommunications ,02 engineering and technology ,Admission control ,01 natural sciences ,010104 statistics & probability ,symbols.namesake ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,Relaxation (approximation) ,0101 mathematics ,Integer (computer science) - Abstract
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.
- Published
- 2018
14. Unconstrained and Constrained Optimization Problems
- Author
-
Shuguang Cui, Anthony Man-Cho So, and Rui Zhang
- Subjects
Mathematical optimization ,Constrained optimization problem ,Computer science - Published
- 2017
15. Rank-Two Beamforming and Stochastic Beamforming for MISO Physical-Layer Multicasting with Finite-Alphabet Inputs
- Author
-
Qiang Li, Sissi Xiaoxiao Wu, Anthony Man-Cho So, and Wing-Kin Ma
- Subjects
Beamforming ,Mathematical optimization ,Multicast ,Applied Mathematics ,Transmitter ,Physical layer ,Data_CODINGANDINFORMATIONTHEORY ,Channel state information ,Signal Processing ,Telecommunications link ,Computer Science::Networking and Internet Architecture ,Bit error rate ,Electrical and Electronic Engineering ,Algorithm ,Quadrature amplitude modulation ,Computer Science::Information Theory ,Mathematics - Abstract
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.
- Published
- 2015
16. Scalable and flexible Max-Var generalized canonical correlation analysis via alternating optimization
- Author
-
Kejun Huang, Xiao Fu, Anthony Man-Cho So, Mingyi Hong, and Nicholas D. Sidiropoulos
- Subjects
Mathematical optimization ,Dimensionality reduction ,020206 networking & telecommunications ,02 engineering and technology ,Sensor fusion ,Generalized canonical correlation ,Principal component analysis ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,Feature (machine learning) ,020201 artificial intelligence & image processing ,Algorithm design ,Canonical correlation ,Algorithm ,Mathematics - Abstract
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.
- Published
- 2017
17. SDR approximation bounds for the robust multicast beamforming problem with interference temperature constraints
- Author
-
Man-Chung Yue, Wing-Kin Ma, Sissi Xiaoxiao Wu, and Anthony Man-Cho So
- Subjects
Beamforming ,Quadratically constrained quadratic program ,Mathematical optimization ,Multicast ,Approximation algorithm ,020206 networking & telecommunications ,Data_CODINGANDINFORMATIONTHEORY ,02 engineering and technology ,01 natural sciences ,010104 statistics & probability ,Base station ,Robustness (computer science) ,Telecommunications link ,0202 electrical engineering, electronic engineering, information engineering ,0101 mathematics ,Computer Science::Information Theory ,Communication channel ,Mathematics - Abstract
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.
- Published
- 2017
18. A Safe Approximation Approach to Secrecy Outage Design for MIMO Wiretap Channels
- Author
-
Qiang Li, Wing-Kin Ma, and Anthony Man-Cho So
- Subjects
3G MIMO ,Mathematical optimization ,Covariance matrix ,Applied Mathematics ,MIMO ,Data_CODINGANDINFORMATIONTHEORY ,Maximization ,Channel state information ,Signal Processing ,Secrecy ,Electrical and Electronic Engineering ,Conic optimization ,Computer Science::Cryptography and Security ,Computer Science::Information Theory ,Mathematics ,Communication channel - Abstract
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.
- Published
- 2014
19. Distributionally Robust Relay Beamforming in Wireless Communications
- Author
-
Xiaoxia Huang, Anthony Man-Cho So, Sissi Xiaoxiao Wu, and Shimin Gong
- Subjects
Beamforming ,Mathematical optimization ,021103 operations research ,business.industry ,Wireless network ,Computer science ,0211 other engineering and technologies ,Robust optimization ,020206 networking & telecommunications ,02 engineering and technology ,law.invention ,User equipment ,Relay ,law ,Computer Science::Networking and Internet Architecture ,0202 electrical engineering, electronic engineering, information engineering ,Wireless ,business ,Algorithm ,Wireless sensor network ,Computer Science::Information Theory ,Communication channel - Abstract
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.
- Published
- 2016
20. Scalable and Flexible Multiview MAX-VAR Canonical Correlation Analysis
- Author
-
Kejun Huang, Mingyi Hong, Xiao Fu, Anthony Man-Cho So, and Nicholas D. Sidiropoulos
- Subjects
FOS: Computer and information sciences ,Mathematical optimization ,Word embedding ,Optimization problem ,Feature vector ,Machine Learning (stat.ML) ,020206 networking & telecommunications ,Feature selection ,02 engineering and technology ,Statistics - Machine Learning ,Generalized canonical correlation ,Signal Processing ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Algorithm design ,Electrical and Electronic Engineering ,Canonical correlation ,Mathematics - Abstract
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.
- Published
- 2016
21. A polynomial optimization approach for robust beamforming design in a device-to-device two-hop one-way relay network
- Author
-
Sissi Xiaoxiao Wu, Anthony Man-Cho So, and Xueying Ni
- Subjects
Beamforming ,Mathematical optimization ,021103 operations research ,Device to device ,0211 other engineering and technologies ,020206 networking & telecommunications ,Data_CODINGANDINFORMATIONTHEORY ,02 engineering and technology ,Hop (networking) ,Bounded function ,Computer Science::Networking and Internet Architecture ,0202 electrical engineering, electronic engineering, information engineering ,Ball (bearing) ,Polynomial optimization ,Relay network ,Linear approximation ,Computer Science::Information Theory ,Mathematics - Abstract
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.
- Published
- 2016
22. A semidefinite relaxation approach to the geolocation of two unknown co-channel emitters by a cluster of formation-flying satellites using both TDOA and FDOA measurements
- Author
-
Lizhong Jiang, Anthony Man-Cho So, and Kehu Yangg
- Subjects
Mathematical optimization ,Computer science ,020206 networking & telecommunications ,020302 automobile design & engineering ,02 engineering and technology ,Multilateration ,Geolocation ,0203 mechanical engineering ,0202 electrical engineering, electronic engineering, information engineering ,FDOA ,Cluster (physics) ,Physics::Accelerator Physics ,Satellite ,Relaxation (approximation) ,Algorithm ,Communication channel ,Integer (computer science) - Abstract
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.
- Published
- 2016
23. Linear Matrix Inequalities with Stochastically Dependent Perturbations and Applications to Chance-Constrained Semidefinite Optimization
- Author
-
Anthony Man-Cho So, Sin-Shuen Cheung, and Kuncheng Wang
- Subjects
Semidefinite programming ,Linear inequality ,Mathematical optimization ,Probability theory ,Conic section ,Covariance matrix ,Convex optimization ,MathematicsofComputing_NUMERICALANALYSIS ,Second-order cone programming ,Software ,Stochastic programming ,Theoretical Computer Science ,Mathematics - Abstract
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,...
- Published
- 2012
24. A Unified Approach to Error Bounds for Structured Convex Optimization Problems
- Author
-
Anthony Man-Cho So and Zirui Zhou
- Subjects
FOS: Computer and information sciences ,Mathematical optimization ,Optimization problem ,Iterative method ,General Mathematics ,0211 other engineering and technologies ,Proper convex function ,Machine Learning (stat.ML) ,010103 numerical & computational mathematics ,02 engineering and technology ,Residual ,01 natural sciences ,Machine Learning (cs.LG) ,Statistics - Machine Learning ,FOS: Mathematics ,Mathematics - Numerical Analysis ,0101 mathematics ,Mathematics - Optimization and Control ,Mathematics ,Complement (set theory) ,021103 operations research ,Function (mathematics) ,Numerical Analysis (math.NA) ,Computer Science - Learning ,Optimization and Control (math.OC) ,Convex optimization ,Convex function ,Software - Abstract
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
- Published
- 2015
25. Semidefinite Relaxation of Quadratic Optimization Problems
- Author
-
Anthony Man-Cho So, Shuzhong Zhang, Yinyu Ye, Wing-Kin Ma, and Zhi-Quan Luo
- Subjects
Beamforming ,Mathematical optimization ,Applied Mathematics ,Rank (computer programming) ,MIMO ,Data_CODINGANDINFORMATIONTHEORY ,Multiuser detection ,Computer engineering ,Signal Processing ,Key (cryptography) ,Relaxation (approximation) ,Quadratic programming ,Electrical and Electronic Engineering ,Wireless sensor network ,Mathematics - Abstract
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.
- Published
- 2010
26. Universal Rigidity and Edge Sparsification for Sensor Network Localization
- Author
-
Yinyu Ye, Anthony Man-Cho So, and Zhisu Zhu
- Subjects
Semidefinite programming ,Mathematical optimization ,Speedup ,Heuristic (computer science) ,Convex optimization ,Graph (abstract data type) ,Relaxation (approximation) ,Heuristics ,Wireless sensor network ,Software ,Theoretical Computer Science ,Mathematics - Abstract
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.
- Published
- 2010
27. Moment inequalities for sums of random matrices and their applications in optimization
- Author
-
Anthony Man-Cho So
- Subjects
Semidefinite programming ,Moment (mathematics) ,Mathematical optimization ,Optimization problem ,Probability theory ,General Mathematics ,Probability distribution ,Approximation algorithm ,Quadratic programming ,Software ,Stochastic programming ,Mathematics - Abstract
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.
- Published
- 2009
28. Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
- Author
-
Jiawei Zhang, Yinyu Ye, and Anthony Man-Cho So
- Subjects
Mathematical optimization ,Optimization problem ,General Mathematics ,Probabilistic-based design optimization ,Stochastic dominance ,Combinatorial optimization ,Approximation algorithm ,Stochastic optimization ,Management Science and Operations Research ,Stochastic approximation ,Stochastic programming ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 2009
29. Distributionally robust chance-constrained transmit beamforming for multiuser MISO downlink
- Author
-
Anthony Man-Cho So, Qiang Li, and Wing-Kin Ma
- Subjects
Beamforming ,Mathematical optimization ,Base station ,Robustness (computer science) ,Convex optimization ,Telecommunications link ,Robust optimization ,Data_CODINGANDINFORMATIONTHEORY ,Covariance ,Transmitter power output ,Computer Science::Information Theory ,Mathematics - Abstract
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.
- Published
- 2014
30. Robust beamforming in two-way relay networks: Quartically perturbed chance constrained formulation and tractable approximation
- Author
-
Kehu Yang, Anthony Man-Cho So, and Shuai Ma
- Subjects
Beamforming ,Mathematical optimization ,medicine.medical_treatment ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Probabilistic logic ,Data_CODINGANDINFORMATIONTHEORY ,Transmitter power output ,Complex normal distribution ,law.invention ,Moment (mathematics) ,Relay ,law ,Computer Science::Networking and Internet Architecture ,medicine ,Random variable ,Relaxation technique ,Computer Science::Information Theory ,Mathematics - Abstract
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.
- Published
- 2014
31. Mechanism design for stochastic optimization problems
- Author
-
Anthony Man-Cho So, Mukund Sundararajan, and Samuel Ieong
- Subjects
Mechanism design ,Mathematical optimization ,Optimization problem ,Computer science ,Probabilistic-based design optimization ,Stochastic optimization ,General Medicine ,Maximization ,Impossibility ,Mathematical economics ,Stochastic programming ,Algorithmic mechanism design - Abstract
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.
- Published
- 2007
32. Beyond convex relaxation: A polynomial-time non-convex optimization approach to network localization
- Author
-
Kam-Fung Sze, Zirui Zhou, Anthony Man-Cho So, Senshan Ji, and Yinyu Ye
- Subjects
Convex analysis ,Polynomial ,Quadratically constrained quadratic program ,Mathematical optimization ,Optimization problem ,Computer science ,Convex relaxation ,Convex set ,Proper convex function ,Linear matrix inequality ,Subderivative ,Nonlinear programming ,Convex optimization ,Second-order cone programming ,Convex combination ,Conic optimization - Abstract
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.
- Published
- 2013
33. Rank-two transmit beamformed Alamouti space-time coding for physical-layer multicasting
- Author
-
Wing-Kin Ma, Anthony Man-Cho So, and Sissi Xiaoxiao Wu
- Subjects
Beamforming ,Mathematical optimization ,Signal-to-noise ratio ,Multicast ,Encoding (memory) ,Code (cryptography) ,Physical layer ,Data_CODINGANDINFORMATIONTHEORY ,Relaxation (approximation) ,Space–time code ,Algorithm ,Mathematics - Abstract
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.
- Published
- 2012
34. Safe convex approximation to outage-based MISO secrecy rate optimization under imperfect CSI and with artificial noise
- Author
-
Anthony Man-Cho So, Wing-Kin Ma, and Qiang Li
- Subjects
Approximation theory ,Mathematical optimization ,Optimization problem ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Transmitter ,Data_CODINGANDINFORMATIONTHEORY ,Maximization ,Channel state information ,Convex optimization ,Artificial noise ,Computer Science::Cryptography and Security ,Computer Science::Information Theory ,Mathematics ,Communication channel - Abstract
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.
- Published
- 2011
35. Cheap semidefinite relaxation MIMO detection using row-by-row block coordinate descent
- Author
-
Wing-Kin Ma, Anthony Man-Cho So, and Hoi-To Wai
- Subjects
Mathematical optimization ,Speedup ,Computational complexity theory ,Iterative method ,MIMO ,Context (language use) ,Relaxation (approximation) ,Coordinate descent ,Algorithm ,Computer Science::Information Theory ,Block (data storage) ,Mathematics - Abstract
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.
- Published
- 2011
36. Semidefinite Optimization Applications
- Author
-
Anthony Man-Cho So
- Subjects
Semidefinite embedding ,Semidefinite programming ,Mathematical optimization ,Quadratically constrained quadratic program ,Optimization problem ,MathematicsofComputing_NUMERICALANALYSIS ,MathematicsofComputing_GENERAL ,Mathematics::Optimization and Control ,Approximation algorithm ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Second-order cone programming ,Quadratic programming ,Conic optimization ,Mathematics - Abstract
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
- Published
- 2011
37. Outage Constrained Robust Transmit Optimization for Multiuser MISO Downlinks: Tractable Approximations by Conic Optimization
- Author
-
Anthony Man-Cho So, Tsung-Hui Chang, Kun-Yu Wang, Wing-Kin Ma, and Chong-Yung Chi
- Subjects
FOS: Computer and information sciences ,Mathematical optimization ,Optimization problem ,Computational complexity theory ,Computer Science - Information Theory ,Gaussian ,Information Theory (cs.IT) ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Probabilistic logic ,Robust optimization ,Data_CODINGANDINFORMATIONTHEORY ,Complex normal distribution ,symbols.namesake ,Robustness (computer science) ,Signal Processing ,symbols ,Computer Science::Networking and Internet Architecture ,Electrical and Electronic Engineering ,Conic optimization ,Mathematics ,Computer Science::Information Theory - Abstract
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.
- Published
- 2011
- Full Text
- View/download PDF
38. Probabilistic Sinr Constrained Robust Transmit Beamforming: A Bernstein-Type Inequality Based Conservative Approach
- Author
-
Kun-Yu Wang, Anthony Man-Cho So, Tsung-Hui Chang, Chong-Yung Chi, and Wing-Kin Ma
- Subjects
Beamforming ,FOS: Computer and information sciences ,Mathematical optimization ,Stochastic process ,medicine.medical_treatment ,Information Theory (cs.IT) ,Computer Science - Information Theory ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Probabilistic logic ,Data_CODINGANDINFORMATIONTHEORY ,Complex normal distribution ,Robustness (computer science) ,Channel state information ,Convex optimization ,medicine ,Relaxation technique ,Mathematics ,Computer Science::Information Theory - Abstract
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
- Published
- 2010
39. Optimal Spectrum Sharing in MIMO Cognitive Radio Networks via Semidefinite Programming
- Author
-
Anthony Man-Cho So and Ying Jun Zhang
- Subjects
Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,Semidefinite programming ,Beamforming ,Mathematical optimization ,Quadratically constrained quadratic program ,Computer Networks and Communications ,Computer science ,MIMO ,Transmitter ,Throughput ,Computer Science - Networking and Internet Architecture ,Channel capacity ,Cognitive radio ,Channel state information ,Electrical and Electronic Engineering ,Throughput (business) ,Communication channel ,Computer Science::Information Theory - Abstract
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
- Published
- 2010
40. Probabilistic analysis of semidefinite relaxation detectors for multiple-input, multiple-output systems
- Author
-
Yinyu Ye and Anthony Man-Cho So
- Subjects
Semidefinite embedding ,Semidefinite programming ,Quadratically constrained quadratic program ,Mathematical optimization ,Convex optimization ,Linear matrix inequality ,Probabilistic analysis of algorithms ,Relaxation (approximation) ,Algorithm ,Conic optimization ,Mathematics - Published
- 2009
41. Stochastic Mechanism Design
- Author
-
Anthony Man-Cho So, Mukund Sundararajan, and Samuel Ieong
- Subjects
Mechanism design ,Mathematical optimization ,Optimization problem ,Multicast ,Incentive compatibility ,Set function ,Maximization ,Special case ,Algorithmic mechanism design ,Mathematics - Abstract
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.
- Published
- 2007
42. Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
- Author
-
Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang
- Subjects
Mathematical optimization ,Robustness (computer science) ,Mathematical finance ,Approximation algorithm ,Probability distribution ,Combinatorial optimization ,Context (language use) ,Mathematical economics ,Stochastic programming ,Probability measure ,Mathematics - Abstract
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.
- Published
- 2006
43. Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity.
- Author
-
So, Anthony Man-Cho and Zhou, Zirui
- Subjects
- *
STOCHASTIC convergence , *MACHINE learning , *AUTOMATIC differentiation , *MATHEMATICAL optimization , *ANALYSIS of variance - Abstract
Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems. Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate. Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration. Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature. In this paper, we combine the best of these two types of results by developing a framework for analysing the non-asymptotic convergence rates of IGMs when they are applied to a class of structured convex optimization problems that includes least squares regression and logistic regression. We then demonstrate the power of our framework by proving, in a unified manner, new linear convergence results for three recently proposed algorithms—the incremental gradient method with increasing sample size [R.H. Byrd, G.M. Chin, J. Nocedal, and Y. Wu,Sample size selection in optimization methods for machine learning, Math. Program. Ser. B 134 (2012), pp. 127–155; M.P. Friedlander and M. Schmidt,Hybrid deterministic–stochastic methods for data fitting, SIAM J. Sci. Comput. 34 (2012), pp. A1380–A1405], the stochastic variance-reduced gradient (SVRG) method [R. Johnson and T. Zhang,Accelerating stochastic gradient descent using predictive variance reduction, Advances in Neural Information Processing Systems 26: Proceedings of the 2013 Conference, 2013, pp. 315–323], and the incremental aggregated gradient (IAG) method [D. Blatt, A.O. Hero, and H. Gauchman,A convergent incremental gradient method with a constant step size, SIAM J. Optim. 18 (2007), pp. 29–51]. We believe that our techniques will find further applications in the non-asymptotic convergence analysis of other first-order methods. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
44. Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems.
- Author
-
Ke Hou and Anthony Man-Cho So
- Subjects
HOMOGENEOUS polynomials ,MATHEMATICAL optimization ,APPROXIMATION theory ,CONVEX geometry ,CONVEX programming - Abstract
In this paper, we establish hardness and approximation results for various Lp-ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], both the problem of optimizing a degree-d homogeneous polynomial over the L
p -ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over Lp -balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Ω((log n)(d-2)/p /nd/2-1 ) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Ω((log n/n)d/2-1 ), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems. [ABSTRACT FROM AUTHOR]- Published
- 2014
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.