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

On the complexity of computing estimates of condition measures of a conic linear system

MATHEMATICS OF OPERATIONS RESEARCH 2003年第4期28卷 625-648页

作者： Freund, RM Vera, JR MIT Sloan Sch Management Cambridge MA 02142 USA Catholic Univ Chile Sch Engn Dept Ind & Syst Engn Santiago Chile

Condition numbers based on the "distance to ill-posedness" rho(d) have been shown to play a crucial role in the theoretical complexity of solving convex optimization models. In this paper, we present two algorithms and corresponding complexity analysis for computing estimates of rho(d) for a finite-dimensional convex feasibility problem P(d) in standard primal form: find x that satisfies Ax=b, x is an element of C-X, where d=(A,b) is the data for the problem P(d). Under one choice of norms for the m- and n-dimensional spaces, the problem of estimating rho(d) is hard (co-NP complete even when C-X=r(+)(N)). However, when the norms are suitably chosen, the problem becomes much easier: We can estimate rho(d) to within a constant factor of its true value with complexity bounds that are linear in ln(C(d)) (where C(d) is the condition number of the data d for P(d)), plus other quantities that arise naturally in consideration of the problem P(d). The first algorithm is an interior-point algorithm, and the second algorithm is a variant of the ellipsoid algorithm. The main conclusion of this work is that when the norms are suitably chosen, computing an estimate of the condition measures of P(d) is essentially not much harder than computing a solution of P(d) itself.

关键词： complexity of linear programming semidefinite programming interior-point methods conditioning complexity theory error analysis

来源：评论

学校读者我要写书评

暂无评论

On the complexity of linear programming under finite precision arithmetic

引用

MATHEMATICAL programming 1998年第1期80卷 91-123页

作者： Vera, JR Univ Chile Dept Ind Engn Santiago Chile Cornell Univ Sch Operat Res & Ind Engn Ithaca NY 14853 USA

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the "conditioning" of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of "good" numerical behavior of the logarithmic barrier method, in the sense that a problem instance "twice as hard" as the other from the numerical point of view, requires only at most twice as much precision to be solved. (C) 1998 The Mathematical programming Society, Inc, Published by Elsevier Science B.V.

关键词： complexity of linear programming interior point methods conditioning error analysis

来源：评论

学校读者我要写书评

暂无评论

Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system

引用

MATHEMATICAL programming 1999年第2期86卷 225-260页

作者： Freund, RM Vera, JR Catholic Univ Chile Dept Ind & Syst Engn Santiago Chile MIT OR Ctr Cambridge MA 02139 USA

A conic linear system is a system of the form P(d) : find x that solves b - Ax is an element of C-Y, x is an element of C-X, where CX and Cy are closed convex cones, and the data for the system is d = (A, b). This system is "well-posed" to the extent that (small) changes in the data (A, b) do not alter the status of the system (the system remains solvable or not). Renegar defined the "distance to ill-posedness", rho(d), to be the smallest change in the data Delta d = (Delta A, Delta b) for which the system P(d + Delta d) is "ill-posed", i.e., d + Delta d is hi the intersection of the closure of feasible and infeasible instances d' = (A', b') of P(.). Renegar also defined the "condition measure" of the data instance d as C(d) := parallel to d parallel to/rho(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equations. This study presents two categories of results related to rho(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of rho(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of rho(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from me origin, where the ratio R/r satisfies R/r less than or equal to c(1)C(d), and such that r greater than or equal to c(2)/C9(d) and R less than or equal t

关键词： complexity of linear programming infinite programming interior point methods conditioning error analysis

来源：评论

学校读者我要写书评

暂无评论

On the complexity of solving feasible linear programs specified with approximate data

引用

SIAM JOURNAL ON OPTIMIZATION 1999年第4期9卷 1010-1040页

作者： Filipowski, S Boeing Co Seattle WA 98124 USA

The problem of solving linear programs specified with approximate data is considered. Algorithms are given for linear programs having both general inequality and nonnegativity constraints and for linear programs having only general inequality constraints. Given approximate data for the actual (unknown) instance, the algorithms use knowledge that the instance in question is primal feasible to reduce the data precision necessary to give an approximation to the solution set of the actual instance when the actual instance has an optimal solution. In some cases, problem instances that would otherwise require perfect precision to solve can now be solved with approximate data because of the knowledge of primal feasibility. The algorithms are computationally efficient. Furthermore, the algorithms require not much more data accuracy than the minimum amount necessary to give an approximate solution of a desired accuracy when the actual instance has an optimal solution. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.

关键词： complexity of linear programming approximate data approximate solutions condition measures knowledge

来源：评论

学校读者我要写书评

暂无评论

On the complexity of solving sparse symmetric linear programs specified with approximate data

引用

MATHEMATICS OF OPERATIONS RESEARCH 1997年第4期22卷 769-792页

作者： Filipowski, S

An algorithm that solves symmetric linear programs specified with approximate data is given. The algorithm uses knowledge that several of the constraint matrix coefficients of the actual (unknown) instance are equal to zero to reduce the data precision necessary to solve the instance in question. The algorithm is computationally efficient and requires not much more data accuracy than the minimum amount necessary to solve the actual instance. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.

关键词： complexity of linear programming approximate data approximate solutions condition measures sparsity knowledge

来源：评论

学校读者我要写书评

暂无评论

Ill-posedness and the complexity of deciding existence of solutions to linear programs

引用

SIAM JOURNAL ON OPTIMIZATION 1996年第3期6卷 549-569页

作者： Vera, JR Department of Industrial Engineering University of Chile Santiago República 701 Chile

We discuss efficient algorithms for deciding existence of solutions to linear programs specified with approximate data. This is important in applications where only an approximation to the real data of the problem is available for computation, or where rounding errors prevent the use of exact numbers. The algorithms are efficient from the point of view of computation and needed data, requiring excessive computation and an excessively precise approximation only for nearly ill-posed instances. We illustrate how the proximity to ill-posedness measures the ''conditioning'' of the problem and plays an important role in the complexity analysis. This work is one step toward the understanding of ill-posedness in optimization problems and the development of a general complexity theory of problem solving with approximate data.

关键词： theory of linear programming complexity of linear programming conditioning

来源：评论

学校读者我要写书评

暂无评论

On the complexity of solving feasible systems of linear inequalities specified with approximate data

引用

MATHEMATICAL programming 1995年第3期71卷 259-288页

作者： Filipowski, S Department of Industrial and Manufacturing Systems Engineering Iowa State University Ames United States

An algorithm that gives an approximate solution of a desired accuracy to a system of linear inequalities specified with approximate data is presented. It uses knowledge that the actual instance is feasible to reduce the data precision necessary to give an approximate solution to the actual instance. in some cases, this additional information allows problem instances that are ill-posed without the knowledge of feasibility to be solved. The algorithm is computationally efficient and requires not much more data accuracy than the minimal amount necessary to give an approximate solution of the desired accuracy. This work aids in the development of a computational complexity theory that uses approximate data and knowledge.

关键词： complexity of linear programming approximate data approximate solutions condition measures knowledge

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：