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

Design of two-channel low-delay IIR nonuniform-division filter banks using L₁ error criteria

IEE PROCEEDINGS-VISION IMAGE AND SIGNAL PROCESSING 2002年第5期149卷 304-314页

作者： Lee, JH Chung, WH Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan

The design of a two-channel nonuniform-division filter (NDF) bank with infinite impulse response (IIR) analysis/synthesis filters and low group delay in the sense of L-1 error criteria is considered. The problem formulation results in a nonlinear optimisation problem. Based on a variant of karmarkar's algorithm, the optimisation problem is solved through a frequency sampling and iterative approximation technique to find the tap coefficients and the reflection coefficients for the numerator and the denominator of the IIR analysis filters. An efficient stabilisation procedure ensures that the reflection coefficients lie in (-1, 1). Simulation results are provided for illustration and comparison.

关键词： .design problem aliasing reflection group delay optimisation problem error criteria FIR filters numerator karmarkar algorithm IIR analysis filters NDF banks

来源：评论

学校读者我要写书评

暂无评论

ON THE NUMBER OF ITERATIONS OF karmarkar algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1993年第1期62卷 153-197页

作者： POWELL, MJD 1. Department of Applied Mathematics and Theoretical Physics University of Cambridge Silver Street CB3 9EW Cambridge England

karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a ''potential function'' by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple of n, where n is the number of inequality constraints. By considering a simple example that allows n to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by karmarkar's original algorithm can require about n/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.

关键词： COMPLEXITY ANALYSIS INTERIOR POINT METHODS karmarkar algorithm LINEAR PROGRAMMING SEMIINFINITE PROGRAMMING

来源：评论

学校读者我要写书评

暂无评论

UPDATING LOWER BOUNDS WHEN USING karmarkar PROJECTIVE algorithm FOR LINEAR-PROGRAMMING

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1993年第1期78卷 127-142页

作者： MITCHELL, JE 1. Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy New York

We give two results related to Gonzaga's recent paper showing that lower bounds derived from the Todd-Burrell update can be obtained by solving a one-variable linear programming problem involving the centering direction and the affine direction. We show how these results may be used to update the primal solution when using the dual affine variant of karmarkar's algorithm. This leads to a dual projective algorithm.

关键词： karmarkar algorithm LOWER BOUNDS LINEAR PROGRAMMING INTERIOR-POINT METHODS

来源：评论

学校读者我要写书评

暂无评论

A GLOBALLY CONVERGENT PRIMAL DUAL INTERIOR-POINT algorithm FOR CONVEX-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1994年第2期64卷 123-147页

作者： MONTEIRO, RDC 1. Systems and Industrial Engineering Department University of Arizona 85721 Tucson AZ USA

In this paper, we study the global convergence of a large class of primal-dual interior point algorithms for solving the linearly constrained convex programming problem. The algorithms in this class decrease the value of a primal-dual potential function and hence belong to the class of so-called potential reduction algorithms. An inexact line search based on Armijo stepsize rule is used to compute the stepsize. The directions used by the algorithms are the same as the ones used in primal-dual path following and potential reduction algorithms and a very mild condition on the choice of the ''centering parameter'' is assumed. The algorithms always keep primal and dual feasibility and, in contrast to the polynomial potential reduction algorithms, they do not need to drive the value of the potential function towards - infinity in order to converge. One of the techniques used in the convergence analysis of these algorithms has its root in nonlinear unconstrained optimization theory.

关键词： INTERIOR-POINT METHODS CONVEX PROGRAMMING karmarkar algorithm GLOBAL CONVERGENCE POTENTIAL FUNCTION POTENTIAL REDUCTION algorithmS ARMIJO STEPSIZE RULE

来源：评论

学校读者我要写书评

暂无评论

GENERALIZATION OF karmarkar algorithm TO CONVEX HOMOGENEOUS FUNCTIONS

引用

OPERATIONS RESEARCH LETTERS 1992年第2期11卷 93-98页

作者： KALANTARI, B Department of Computer Science Rutgers University New Brunswick NJ 08903 USA

Let phi be a convex homogeneous function of degree K>0 defined over the positive points of a subspace W of R(n), n greater-than-or-equal-to 2. Assume phi(x)>0 for some 00, there exists 0<x(d) is-an-element-of... 详细信息

关键词： HOMOGENEOUS FUNCTIONS karmarkar algorithm

来源：评论

学校读者我要写书评

暂无评论

STRICT MONOTONICITY AND IMPROVED COMPLEXITY IN THE STANDARD FORM PROJECTIVE algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1993年第3期62卷 517-535页

作者： ANSTREICHER, KM UNIV CATHOLIQUE LOUVAIN CTR OPERAT RES & ECONOMETRB-1348 LOUVAINBELGIUM

In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve O(square-root n L) step complexity, opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.

关键词： LINEAR PROGRAMMING karmarkar algorithm PROJECTIVE algorithm STANDARD FORM

来源：评论

学校读者我要写书评

暂无评论

ON PARTIAL UPDATING IN A POTENTIAL REDUCTION LINEAR-PROGRAMMING algorithm OF KOJIMA, MIZUNO, AND YOSHISE

引用

algorithmICA 1993年第2期9卷 184-197页

作者： BOSCH, RA ANSTREICHER, KM 1. Department of Operations Research Yale University 06520 New Haven CT USA

We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.

关键词： LINEAR PROGRAMMING karmarkar algorithm POTENTIAL FUNCTION PRIMAL DUAL MODIFIED METHOD RANK-ONE UPDATES

来源：评论

学校读者我要写书评

暂无评论

CONVERGENCE BEHAVIOR OF karmarkar PROJECTIVE algorithm FOR SOLVING A SIMPLE LINEAR PROGRAM

引用

OPERATIONS RESEARCH LETTERS 1991年第7期10卷 389-393页

作者： KALISKI, JA YE, YY Department of Management Sciences The University of Iowa Iowa City IA 52242 USA

We describe the convergence behavior of karmarkar's projective algorithm for solving a simple linear program. We show that the algorithm requires at least n - 1 iterations to reach the optimal solution, while the simplex method may need one pivot step. Thus in the worst case, karmarkar's algorithm will require at least OMEGA(n) iterations to converge.

关键词： LINEAR PROGRAMMING karmarkar algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE CONTINUOUS TRAJECTORIES FOR A POTENTIAL REDUCTION algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICS OF OPERATIONS RESEARCH 1992年第1期17卷 225-253页

作者： MONTEIRO, RDC AT&T BELL LABS HOLMDELNJ 07733

For a possibly degenerate linear program min x{c(T)x;Ax = b, x greater-than-or-equal-to 0} (A is an m X n real matrix, b is-an-element-of R(m) and c is-an-element-to R(n)), whose optimal value is 0, we study the limiting behavior of the trajectories of the family of vector fields [GRAPHICS] for all values of q greater-than-or-equal-to n, where X is the diagonal matrix associated with x and P(AX) is the projection operator onto the null space of AX. A polynomial algorithm based on the directions PHI(q)(x) has been presented by Gonzaga [6] when q = n or q = n + square-root n . We show that all trajectories of PHI(q)(x) converge to the unique "center" of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of PHI(q)(x) approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value tau > 0 such that: for q > tau, "most" of the trajectories of PHI(q)(x) converge to the "center" tangentially to the optimal face and that the direction of approach of a trajectory of PHI(q)(x) depends on the initial condition;for q < tau (q = tau), the trajectories of PHI(q)(x) converge to the "center" along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.

关键词： INTERIOR POINT algorithmS LINEAR PROGRAMMING karmarkar algorithm CONTINUOUS TRAJECTORIES FOR LINEAR PROGRAMMING POTENTIAL REDUCTION algorithmS POTENTIAL FUNCTION

来源：评论

学校读者我要写书评

暂无评论

LONG STEPS IN AN O(N3L) algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1992年第3期54卷 251-265页

作者： ANSTREICHER, KM BOSCH, RA 1. Department of Operations Research Yale University 06520 New Haven CT USA

We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein-Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n3L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous "primal-only" initialization actually reduces the complexity to less than O(m1.5n1.5L).

关键词： LINEAR PROGRAMMING karmarkar algorithm POTENTIAL FUNCTION STANDARD FORM MODIFIED METHOD RANK-ONE UPDATES

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：