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

Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function

Acta Mathematica Sinica,English Series 2007年第11期23卷 2027-2042页

作者： Yan Qin BAI Guo Qiang WANG Department of Mathematics College of Sciences Shanghai University Shanghai 200444 P. R. China College of Vocational Technology Shanghai University of Engineering Science Shanghai 200437 P. R. China

A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.

关键词： second-order cone optimization linear optimization interior-point methods large- and small-update methods polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

Energy optimisation in resilient self-stabilizing processes

Energy optimisation in resilient self-stabilizing processes

引用

International Symposium on Parallel Computing in Electrical Engineering

作者： Kosowski, Adrian Kuszner, Lukasz Gdansk Univ Technol Dept Algorithms & Syst Modeling PL-80952 Gdansk Poland

ISBN: (纸本)0769525547

When performing an algorithm in the self-stabilizing model, a distributed system must achieve a desirable global state regardless of the initial state, whereas each node has only local information about the system. Depending on adopted assumptions concerning the model of simultaneous execution and scheduler fairness, some algorithms may differ in stabilization time or possibly not stabilize at all. Surprisingly, we show that the class of polynomially-solvable self-stabilizing problems is invariant with respect to the assumption of weak scheduler fairness. Furthermore, for Systems with a single distinguished vertex we prove a much stronger equivalence, stating that synchronisation, the existence of a central scheduler and its fairness have no influence on polynomial stabilization time.

关键词： self-stabilization asynchronous system polynomial-time complexity distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming

引用

MATHEMATICAL PROGRAMMING 2005年第1期102卷 1-24页

作者： Zhao, GY Natl Univ Singapore Dept Math Singapore 117543 Singapore

This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.

关键词： multi-stage stochastic nonlinear programming lagrangian dual self-concordant barrier interior point methods polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

On the sphere-decoding algorithm II. Generalizations, second-order statistics, and applications to communications

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2005年第8期53卷 2819-2834页

作者： Vikalo, H Hassibi, B CALTECH Dept Elect Engn Pasadena CA 91125 USA

In Part 1, we found a closed-form expression for the expected complexity of the sphere-decoding algorithm, both for the infinite and finite lattice. We continue the discussion in this paper by generalizing the results to the complex version of the problem and using the expected complexity expressions to determine situations where sphere decoding is practically feasible. In particular, we consider applications of sphere decoding to detection in multiantenna systems. We show that, for a wide range of signal-to-noise ratios (SNRs), rates, and numbers of antennas, the expected complexity is polynomial, in fact, often roughly cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can, in fact, be implemented in real-time-a result with many practical implications. To provide complexity information beyond the mean, we derive a closed-form expression for the variance of the complexity of sphere-decoding algorithm in a finite lattice. Furthermore, we consider the expected complexity of sphere decoding for channels with memory, where the lattice-generating matrix has a special Toeplitz structure. Results indicate that the expected complexity in this case is, too, polynomial over a wide range of SNRs, rates, data blocks, and channel impulse response lengths.

关键词： expected complexity frequency-selective channels multiple-antenna systems polynomial-time complexity sphere decoding wireless communications

来源：评论

学校读者我要写书评

暂无评论

Iterative decoding for MIMO channels via modified sphere decoding

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2004年第6期3卷 2299-2311页

作者： Vikalo, H Hassibi, B Kailath, T CALTECH Pasadena CA 91125 USA Stanford Univ Informat Syst Lab Stanford CA 94309 USA

In recent years, soft iterative decoding techniques have been shown to greatly improve the bit error rate performance of various communication systems. For multiantenna systems employing space-time codes, however, it is not clear what is the best way to obtain the soft information required of the iterative scheme with low complexity. In this paper, we propose a modification of the Fincke-Pohst (sphere decoding) algorithm to estimate the maximum a posteriori probability of the received symbol sequence. The new algorithm solves a nonlinear integer least squares problem and, over a wide range of rates and signal-to-noise ratios, has polynomial-time complexity. Performance of the algorithm, combined with convolutional, turbo, and low-density parity check codes, is demonstrated on several multiantenna channels. The results for systems that employ space-time modulation schemes seem to indicate that the best performing schemes are those that support the highest mutual information between the transmitted and received signals, rather than the best diversity gain.

关键词： expected complexity iterative decoding low-density parity check (LDPC) codes multiantenna systems polynomial-time complexity space-time codes sphere decoding turbo codes wireless communications

来源：评论

学校读者我要写书评

暂无评论

Infeasible-interior-point algorithm for a class of nonmonotone complementarity problems and its computational complexity

引用

Science China Mathematics 2001年第3期44卷 338-344页

作者：何尚录徐成贤 1. Department of Scientific Computing Science School Xi’an Jiaotong University 710049 Xi’an China

This paper presents an infeasible-interior-point algorithm for aclass of nonmonotone complementarity problems, and analyses its convergence and computational complexity. The results indicate that the proposed algorith... 详细信息

关键词： complementarity problem infeasible-interior-point algorithm polynomial-time complexity uniform P-function

来源：评论

学校读者我要写书评

暂无评论

Shuffle languages are in P

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期250卷 31-53页

作者： Jedrzejowicz, J Szepietowski, A Univ Gdansk Inst Math PL-80952 Gdansk Poland

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： complexity polynomial-time complexity shuffle languages shuffle automata

来源：评论

学校读者我要写书评

暂无评论

On complexity of matrix scaling

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 1999年 303卷 435-460页

作者： Nemirovski, A Rothblum, U Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

The Line Sum Scaling problem for a nonnegative matrix A is to find positive definite diagonal matrices Y, Z which result in prescribed row and column sums of the scaled matrix YAZ. The matrix Balancing problem for a nonegative square matrix A is to find a positive definite diagonal Matrix X such that the row sums in the scaled matrix XAX are equal to the corresponding column sums. We demonstrate that epsilon-versions of both these problems, same as those of other scaling problems for nonnegative multiindex arrays, can be reduced to a specific Geometric Programming problem. For the latter problem, we develop a polynomial-time algorithm, thus deriving polynomial time solvability of a number of generic scaling problems for nonnegative multiindex arrays. Our results extend those previously known for the problems of matrix balancing [3] and of double-stochastic scaling of a square nonnegative matrix [2]. (C) 1999 Published by Elsevier Science Inc. All rights reserved.

关键词： matrix scaling matrix balancing polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

Following a ''balanced'' trajectory from an infeasible point to an optimal linear programming solution with a polynomial-time algorithm

引用

MATHEMATICS OF OPERATIONS RESEARCH 1996年第4期21卷 839-859页

作者： Freund, RM Sloan School of Management Massachusetts Inst. of Technology Cambridge MA 02139-4307 50 Memorial Drive E53-361 United States

This paper is concerned with the problem of following a trajectory from an infeasible starting point directly to an optimal solution of the linear programming problem. A class of trajectories for the problem is defined, based on the notion of a beta-balanced solution to the problem. Given a prespecified positive balancing constant beta, an infeasible solution x is said to be beta-balanced if the optimal value gap is less than or equal to beta times the infeasibility gap. Mathematically, this can be written as c(T)x - z* less than or equal to beta xi(T)x, where the linear form xi(T)x is the Phase I objective function and z* is the optimal objective value of the linear program. The concept of a beta-balanced solution is used to define a class of trajectories from an infeasible point to an optimal solution of a given linear program. Each trajectory has the properly that all points on or near the trajectory (in a suitable metric) are beta-balanced. The main thrust of the paper is the development of an algorithm that traces a given beta-balanced trajectory from a starting point near the trajectory to an optimal solution to the given linear programming problem in polynomial time. More specifically, the algorithm allows for fixed improvement in the bound on the Phase I and the Phase II objectives in O(n) Newton steps.

关键词： linear program interior-point algorithm polynomial-time complexity trajectory method Newton's method

来源：评论

学校读者我要写书评

暂无评论

Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs

引用

ANNALS OF OPERATIONS RESEARCH 1996年第1期62卷 1-28页

作者： Kojima, M TOKYO INST TECHNOL DEPT MATH & COMP SCIMEGURO KUTOKYO 152JAPAN

The primal-dual infeasible-interior-point algorithm is known as one of the most efficient computational methods for linear programs. Recently, a polynomial-time computational complexity bound was established for special variants of the algorithm. However, they impose severe restrictions on initial points and require a common step length in the primal and dual spaces. This paper presents some basic lemmas that bring great flexibility and improvement into such restrictions on initial points and step lengths, and discusses their extensions to linear and nonlinear monotone complementarity problems.

关键词： linear program interior point method initial point step length complementarity problem polynomial-time complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：