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

International Symposium on Low Power Electronics and Design

作者： Chinnery, DG Keutzer, K Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)1595931376

Most circuit sizing tools calculate the tradeoff between each gate's delay and power or area, and then greedily change the gate with the best tradeoff. We show this is suboptimal. Instead we use a linear program to minimize circuit power. The linear program provides a fast and simultaneous analysis of how each gate affects gates it has a path to. Our approach reduces power by up to 30% compared to commercial software, with a 0.13um library. The runtime for posing and solving the linear program scales linearly with circuit size.

关键词： delay linear program power sizing

来源：评论

学校读者我要写书评

暂无评论

A Homogeneous Smoothing-type Algorithm for Symmetric Cone linear programs

引用

Acta Mathematicae Applicatae Sinica 2014年第3期30卷 647-662页

作者： Wei-Zhe GU Zheng-Hai HUANG Department of Mathematics School of ScienceTianjin University

In this paper, we investigate a smoothing-type algorithm for solving the symmetric cone linear program （（SCLP） for short） by making use of an augmented system of its optimality conditions. The algorithm only needs to solve one system of linear equations and to perform one line search at each iteration. It is proved that the algorithm is globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, the algorithm may correctly detect solvability of （SCLP）. Furthermore, if （SCLP） has a solution, then the algorithm will generate a solution of （SCLP）, and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of （SCLP）.

关键词： linear program symmetric cone Euclidean Jordan algebra smoothing algorithm global conver-gence

来源：评论

学校读者我要写书评

暂无评论

SHARP LIPSCHITZ-CONSTANTS FOR BASIC OPTIMAL-SOLUTIONS AND BASIC FEASIBLE SOLUTIONS OF linear-programS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1994年第1期32卷 140-153页

作者： LI, W Old Dominion Univ Norfolk VA United States

The main purpose of this paper is to give Lipschitz constants for basic optimal solutions (or vertices of solution sets) and basic feasible solutions (or vertices of feasible sets) of linear programs with respect to right-hand side perturbations. The Lipschitz constants are given in terms of norms of pseudoinverses Of submatrices of the matrices involved, and are sharp under very general assumptions. There are two mathematical principles involved in deriving the Lipschitz constants: (1) the local upper Lipschitz constant of a Hausdorff lower semicontinuous mapping is equal to the Lipschitz constant of the mapping and (2) the Lipschitz constant of a finite-set-valued mapping can be inherited by its continuous submappings. Moreover, it is proved that any Lipschitz constant for basic feasible solutions can be used as an Lipschitz constant for basic optimal solutions, feasible solutions, and optimal solutions.

关键词： SHARP LIPSCHITZ CONSTANT linear program (BASIC) OPTIMAL SOLUTION (BASIC) FEASIBLE SOLUTION LOWER SEMICONTINUOUS MAPPING LOCALLY UPPER LIPSCHITZ CONTINUOUS MAPPING PSEUDOINVERSE

来源：评论

学校读者我要写书评

暂无评论

A linear programming formulation and approximation algorithms for the metric labeling problem

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2005年第3期18卷 608-625页

作者： Chekuri, C Khanna, S Naor, J Zosin, L Bell Labs Lucent Technol Murray Hill NJ 07974 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel NEC Res Inst Princeton NJ 08540 USA

We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616-630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448-455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652-658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric, thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of 2 + root 2 similar or equal to 3.414 for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric.

关键词： metric labeling linear program approximation algorithm truncated linear metric

来源：评论

学校读者我要写书评

暂无评论

A PATH-FOLLOWING ALGORITHM FOR linear-programMING USING QUADRATIC AND LOGARITHMIC PENALTY-FUNCTIONS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1993年第6期31卷 1578-1598页

作者： TSENG, P MIT INFORMAT & DECIS SYST LABCAMBRIDGEMA 02139 MIT CTR INTELLIGENT CONTROL SYSTCAMBRIDGEMA 02139

Motivated by a recent work of Setiono, a path-following algorithm for linear programming using both logarithmic and quadratic penalty functions is proposed. In the algorithm, a logarithmic and a quadratic penalty is placed on, respectively, the nonnegativity constraints and an arbitrary subset of the equality constraints;Newton's method is applied to solve the penalized problem, and after each Newton step the penalty parameters are decreased. This algorithm maintains neither primal nor dual feasibility and does not require a Phase I. It is shown that if the initial iterate is chosen appropriately and the penalty parameters are decreased to zero in a particular way, then the algorithm is linearly convergent. Numerical results are also presented suggesting that the algorithm may be competitive with interior point algorithms in practice, requiring typically between 30-45 iterations to accurately solve each Netlib problem tested.

关键词： linear program PATH-FOLLOWING NEWTON STEP PENALTY FUNCTION

来源：评论

学校读者我要写书评

暂无评论

Convergence and error bound for perturbation of linear programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1999年第1-3期13卷 221-230页

作者： Tseng, P Univ Washington Dept Math Seattle WA 98195 USA

In various penalty/smoothing approaches to solving a linear program, one regularizes the problem by adding to the linear cost function a separable nonlinear function multiplied by a small positive parameter. Popular choices of this nonlinear function include the quadratic function, the logarithm function, and the x ln(x)-entropy function. Furthermore, the solutions generated by such approaches may satisfy the linear constraints only inexactly and thus are optimal solutions of the regularized problem with a perturbed right-hand side. We give a general condition for such an optimal solution to converge to an optimal solution of the original problem as the perturbation parameter tends to zero. In the case where the nonlinear function is strictly convex, we further derive a local (error) bound on the distance from such an optimal solution to the limiting optimal solution of the original problem, expressed in terms of the perturbation parameter.

关键词： linear program perturbation convergence error bound

来源：评论

学校读者我要写书评

暂无评论

A review of computation of mathematically rigorous bounds on optima of linear programs

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第3期68卷 677-683页

作者： Guilbeau, Jared T. Hossain, Md. Istiaq Karhbet, Sam D. Kearfott, Ralph Baker Sanusi, Temitope S. Zhao, Lihong Univ Louisiana POB 4-1010 Lafayette LA 70504 USA

linear program solvers sometimes fail to find a good approximation to the optimum value, without indicating possible failure. However, it may be important to know how close the value such solvers return is to an actual optimum, or even to obtain mathematically rigorous bounds on the optimum. In a seminal 2004 paper, Neumaier and Shcherbina, propose a method by which such rigorous lower bounds can be computed;we now have significant experience with this method. Here, we review the technique. We point out typographical errors in two formulas in the original publication, and illustrate their impact. Separately, implementers and practitioners can also easily make errors. To help implementers avoid such problems, we cite a technical report where we explain things to mind and where we present rigorous bounds corresponding to alternative formulations of the linear program.

关键词： linear program Interval computations Mathematically rigorous lower bounds Branch and bound Relaxation Global optimization

来源：评论

学校读者我要写书评

暂无评论

A GLOBALLY CONVERGENT PROBABILITY-ONE HOMOTOPY FOR linear programS WITH linear COMPLEMENTARITY CONSTRAINTS

引用

SIAM JOURNAL ON OPTIMIZATION 2013年第2期23卷 1167-1188页

作者： Watson, Layne T. Billups, Stephen C. Mitchell, John E. Easterling, David R. Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Virginia Polytech Inst & State Univ Dept Math Blacksburg VA 24061 USA Univ Colorado Dept Math Denver CO 80217 USA Rensselaer Polytech Inst Dept Math Sci Troy NY 12180 USA

A solution of the standard formulation of a linear program with linear complementarity constraints (LPCC) does not satisfy a constraint qualification. A family of relaxations of an LPCC, associated with a probability-one homotopy map, proposed here is shown to have several desirable properties. The homotopy map is nonlinear, replacing all the constraints with nonlinear relaxations of NCP functions. Under mild existence and rank assumptions, (1) the LPCC relaxations RLPCC(lambda) have a solution for 0 <= lambda <= 1;(2) RLPCC(1) is equivalent to LPCC;(3) the Kuhn-Tucker constraint qualification is satisfied at every local or global solution of RLPCC(lambda) for almost all 0 <= lambda < 1;(4) a point is a local solution of RLPCC(1) (and LPCC) if and only if it is a Kuhn-Tucker point for RLPCC(1);and (5) a homotopy algorithm can find a Kuhn-Tucker point for RLPCC(1). Since the homotopy map is a globally convergent probability-one homotopy, robust and efficient numerical algorithms exist to find solutions of RLPCC(1). Numerical results are included for some small problems.

关键词： complementarity constraint qualification globally convergent homotopy algorithm linear program probability-one homotopy

来源：评论

学校读者我要写书评

暂无评论

A QMR-based interior-point algorithm for solving linear programs

引用

MATHEMATICAL programMING 1997年第1期76卷 183-210页

作者： Freund, RW Jarre, F UNIV WURZBURG INST ANGEW MATH & STAT D-97074 WURZBURG GERMANY

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2 x 2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3 x 3-block systems to symmetric 2 x 2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.

关键词： linear program interior-point method symmetric indefinite linear system quasi-minimal residual iteration indefinite preconditioner

来源：评论

学校读者我要写书评

暂无评论

COBS: qualitatively constrained smoothing via linear programming

引用

COMPUTATIONAL STATISTICS 1999年第3期14卷 315-337页

作者： He, XM Ng, P Univ Illinois Dept Stat Champaign IL 61820 USA Natl Univ Singapore Dept Math Singapore 119260 Singapore Univ Illinois Dept Econ Champaign IL 61820 USA

Popular smoothing techniques generally have a difficult time accommodating qualitative constraints like monotonicity, convexity or boundary conditions on the fitted function. In this paper, we attempt to bring the problem of constrained spline smoothing to the foreground and describe the details of a constrained B-spline smoothing (COBS) algorithm that is being made available to S-plus users. Recent work of He & Shi (1998) considered a special case and showed that the L-1 projection of a smooth function into the space of B-splines provides a monotone smoother that is flexible, efficient and achieves the optimal rate of convergence. Several options and generalizations are included in COBS: it can handle small or large data sets either with user interaction or full automation. Three examples are provided to show how COBS works in a variety of real-world applications.

关键词： constraint information criterion knot selection linear program nonparametric regression regression quantile smoothing spline

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：