检索结果-内蒙古大学图书馆

An Interior Point Method for Solving semidefinite Programs Using Cutting Planes and Weighted Analytic Centers

JOURNAL OF APPLIED MATHEMATICS 2012年第unknown期2012卷 1-21页

作者： Machacek, John Jibrin, Shafiu No Arizona Univ Dept Math & Stat Flagstaff AZ 86011 USA Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA

We investigate solving semidefinite programs (SDPs) with an interior point method called SDP-CUT, which utilizes weighted analytic centers and cutting plane constraints. SDP-CUT iteratively refines the feasible region to achieve the optimal solution. The algorithm uses Newton's method to compute the weighted analytic center. We investigate different stepsize determining techniques. We found that using Newton's method with exact line search is generally the best implementation of the algorithm. We have also compared our algorithm to the SDPT3 method and found that SDP-CUT initially gets into the neighborhood of the optimal solution in less iterations on all our test problems. SDP-CUT also took less iterations to reach optimality on many of the problems. However, SDPT3 required less iterations on most of the test problems and less time on all the problems. Some theoretical properties of the convergence of SDP-CUT are also discussed.

关键词： INTERIOR-point methods semidefinite programming PROBLEM solving ALGORITHMS ITERATIVE methods (Mathematics) STOCHASTIC convergence

来源：评论

学校读者我要写书评

暂无评论

Discrete-Time Indefinite Stochastic LQ Control via SDP and LMI Methods

引用

JOURNAL OF APPLIED MATHEMATICS 2012年第unknown期2012卷 1-14页

作者： Zhou, Shaowei Zhang, Weihai Shandong Univ Sci & Technol Coll Informat & Elect Engn Qingdao 266510 Peoples R China

This paper studies a discrete-time stochastic LQ problem over an infinite time horizon with state-and control-dependent noises, whereas the weighting matrices in the cost function are allowed to be indefinite. We mainly use semidefinite programming (SDP) and its duality to treat corresponding problems. Several relations among stability, SDP complementary duality, the existence of the solution to stochastic algebraic Riccati equation (SARE), and the optimality of LQ problem are established. We can test mean square stabilizability and solve SARE via SDP by LMIs method.

关键词： DISCRETE-time systems STOCHASTIC processes H2 control semidefinite programming LINEAR matrix inequalities TIME perspective COST functions (Optimization)

来源：评论

学校读者我要写书评

暂无评论

EXPERIMENTAL EVALUATION OF SIMULTANEOUS 3D LOCALIZATION OF SENSOR NODES AND TRACKING MOVING TARGETS

EXPERIMENTAL EVALUATION OF SIMULTANEOUS 3D LOCALIZATION OF S...

引用

European Signal Processing Conference

作者： Pinar Oguz Ekim Joao Gomes Joao Xavier Paulo Oliveira Institute for Systems and Robotics - Instituto Superior Tecnico (ISR/IST) Technical University of Lisbon (UTL)

ISBN: (纸本)9781467310680

In this work we carry out an experimental performance characterization of a simultaneous localization and tracking (SLAT) algorithm for sensor networks, whose aim is to determine the positions of sensor nodes and a moving target in a network, given incomplete and inaccurate range measurements between the target and each of the sensors. To achieve this, we propose to iteratively maximize a likelihood function (ML) of positions given the observed ranges, which requires initialization with an approximate solution to avoid convergence towards local extrema. A modified Euclidean Distance Matrix (EDM) completion problem is solved for a block of target range measurements to approximately set up initial sensor/target positions, and the likelihood function is then iteratively refined through Majorization-Minimization (MM). To reduce the computational load, an incremental scheme is used whereby each new target or sensor position is estimated from range measurements, providing additional initialization for ML without the need for solving an expanded EDM completion problem. The proposed algorithms are experimentally evaluated with a series of 3D indoor tests for a range of operation of up to ten meters using a Crossbow Cricket location system and a robotic or human target. Centimetric accuracy is obtained under realistic conditions.

关键词： Localization Tracking Sensor networks semidefinite programming Real indoor experiments

来源：评论

学校读者我要写书评

暂无评论

MINIMIZING CONDITION NUMBER VIA CONVEX programming

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2011年第4期32卷 1193-1211页

作者： Lu, Zhaosong Pong, Ting Kei Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Univ Washington Dept Math Seattle WA 98195 USA

In this paper we consider minimizing the spectral condition number of a positive semidefinite matrix over a nonempty closed convex set Omega. We show that it can be solved as a convex programming problem, and moreover, the optimal value of the latter problem is achievable. As a consequence, when Omega is positive semidefinite representable, it can be cast into a semidefinite programming problem. We then propose a first-order method to solve the convex programming problem. The computational results show that our method is usually faster than the standard interior point solver SeDuMi [J. F. Sturm, Optim. Methods Softw., 11/12 (1999), pp. 625-653] while producing a comparable solution. We also study a closely related problem, that is, finding an optimal preconditioner for a positive definite matrix. This problem is not convex in general. We propose a convex relaxation for finding positive definite preconditioners. This relaxation turns out to be exact when finding optimal diagonal preconditioners.

关键词： condition number diagonal preconditioner convex programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

semidefinite programming relaxation approach for multiuser detection of QAM signals

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2007年第12期6卷 4275-4279页

作者： Mao, Zhiwei Wang, Xianmin Wang, Xiaofeng Lakehead Univ Thunder Bay ON P7B 5E1 Canada Concordia Univ Montreal PQ Canada

A semidefinite programming (SDP) relaxation approach is proposed to solve multiuser detection problems in systems with M-ary quadrature amplitude modulation (M-QAM). In the proposed approach, the optimal M-ary maximum likelihood (ML) detection is carried out by converting the associated M-ary integer programming problem into a binary integer programming problem. Then a relaxation approach is adopted to convert the binary integer programming problem into an SDP problem. This relaxation process leads to a detector of much reduced complexity. A multistage approach is then proposed to improve the performance of the SDP relaxation based detectors. Computer simulations demonstrate that the symbol-error rate (SER) performance offered by the proposed multistage SDP relaxation based detectors outperforms that of several existing suboptimal detectors.

关键词： semidefinite programming multistage detection multiuser detection QAM

来源：评论

学校读者我要写书评

暂无评论

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

引用

MATHEMATICAL programming 2011年第2期129卷 301-329页

作者： Zheng, Xiao Jin Sun, Xiao Ling Li, Duan Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0-1 constraints.

关键词： Quadratically constrained quadratic programming Convex relaxation Decomposition-approximation method Polyhedral approximation semidefinite programming Rank-2 semidefinite inequalities

来源：评论

学校读者我要写书评

暂无评论

Solution of the Propeller Conjecture in R~3 12

Solution of the Propeller Conjecture in R~3

引用

ACM Symposium on Theory of Computing

作者： Steven Heilman Aukosh Jagannath Assaf Naor Courant Institute NYU New York NY USA

ISBN: (纸本)9781450312455

It is shown that every measurable partition {A_1,...,A_k} of R~3 satisfies ∑_(i=1)~k ‖∫_(A_i) xe~(-1/2‖x‖_2~2)dx‖_2~2 ≤ 9π~2. (1) Let {P_1, P_2, P_3} be the partition of R~2 into 120° sectors centered at the origin. The bound (1) is sharp, with equality holding if A_i = P_i × R for i ∈ {1, 2, 3} and A_i = 0 for i ∈ {4,...,k}. This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the Unique Games hardness threshold of the Kernel Clustering problem with 4×4 centered and spherical hypothesis matrix equals 2π/3.

关键词： Theory Kernel clustering Unique games hardness semidefinite programming Grothendieck inequalities

来源：评论

学校读者我要写书评

暂无评论

CoMP in Heterogeneous Networks: Linear Transceiver Design Using the Minimum Weighted Arithmetic-MSE Criterion

CoMP in Heterogeneous Networks: Linear Transceiver Design Us...

引用

International OFDM Workshop

作者： Tarik Akbudak Andreas Czylwik Chair of Communication Systems University of Duisburg-Essen

ISBN: (纸本)9783800733606

Coordinated multipoint transmission (CoMP) is considered for a heterogeneous network (HetNet) where different kinds of base stations (BS) are located. We focus on linear transceiver design with the goal of maximizing the weighted sum-rate in the downlink of a multipleinput multiple-output orthogonal frequency division multiple access (MIMO-OFDMA) system, where each subchannel is allocated to a single user (termed as single-user MIMOOFDMA). We address this in the context of minimizing the weighted arithmetic mean of the mean-square-errors (MSEs), i.e., weighted arithmetic-MSE minimization. The problem is shown to be non-convex for a given rank constraint on the number of streams at a subchannel. Therefore, the solutions to the rank-constrained problem are suboptimal in general. We show that iterative approaches provide more efficient suboptimal solutions compared to the rank-relaxed approach, especially in a heterogeneous network where highly imbalanced base stations are located.

关键词： Weighted sum-rate maximization Linear transceiver design Second-order cone programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Design of a multiple kernel learning algorithm for LS-SVM by convex programming

引用

NEURAL NETWORKS 2011年第5期24卷 476-483页

作者： Jian, Ling Xia, Zhonghang Liang, Xijun Gao, Chuanhou Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Western Kentucky Univ Dept Comp Sci Bowling Green KY 42101 USA Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China China Univ Petr Sch Math & Computat Sci Dongying 257061 Peoples R China

As a kernel based method, the performance of least squares support vector machine (LS-SVM) depends on the selection of the kernel as well as the regularization parameter (Duan, Keerthi, & Poo, 2003). Cross-validation is efficient in selecting a single kernel and the regularization parameter: however, it suffers from heavy computational cost and is not flexible to deal with multiple kernels. In this paper, we address the issue of multiple kernel learning for LS-SVM by formulating it as semidefinite programming (SDP). Furthermore, we show that the regularization parameter can be optimized in a unified framework with the kernel, which leads to an automatic process for model selection. Extensive experimental validations are performed and analyzed. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Least squares support vector machines Multiple kernel learning Convex optimization semidefinite programming Quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Robust linear transceivers for downlink multi-user multiple-input multiple-output systems using second-order cone programming optimisation

引用

IET COMMUNICATIONS 2011年第17期5卷 2586-2593页

作者： Li, H. Xie, S. Northeastern Univ Coll Informat Sci & Engn Shenyang 110006 Liaoning Peoples R China Inst Infocomm Res Singapore 138632 Singapore

This study addresses the joint robust linear transceiver design problems for a downlink multi-user multiple-input multiple-output (MIMO) antenna system in the presence of imperfect channel state information (CSI). The uncertainty in the channel is characteried by a norm-bounded region, and two robust optimal design problems are considered. One is aimed at minimising the total transmitter power subject to users' mean square error (MSE) constraints in the presence of channel uncertainty, the other is to minimise the worst-case sum-mean square error (sum-MSE) under power constraints for all admissible uncertainties. For these two problems, the authors propose two iterative algorithms based on second-order cone programming (SOCP) formulations, which can be efficiently solved and have less computational complexity than their semi-definite programming (SDP) counterparts. Simulation results also illustrate that the proposed robust design approaches can significantly reduce the computational complexity while achieving almost the same performance as the robust SDP methods.

关键词： convex programming norm-bounded region sum-MSE Optimisation techniques robust linear transceiver wireless channels worst-case sum-mean square error iterative methods semidefinite programming robust optimal design problem iterative algorithm mean square error methods Single antennas robust SDP method radio transceivers channel uncertainty downlink multiuser multiple-input multiple-output antenna system Interpolation and function approximation (numerical analysis) imperfect channel state information computational complexity Radio links and equipment second-order cone programming optimisation antennas power constraint MIMO communication

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：