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

2nd International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM)

作者： Korotkiy, V. A. Usmanova, E. A. Khmarova, L. I. South Ural State Univ Chelyabinsk Russia

ISBN: (纸本)9781509013227

The algorithm of geometrically accurate construction of the main axes of second-order curve passing through the given points and tangent to the given lines is considered. The known projective properties of second-order curves are used in the algorithm. On the basis of a projective algorithm, the program has been created with the Autolisp programming language. The program allows automatic determining the metrics and algebraic equation rations of the second-order curve determined by any combination of points and tangents. The program is used for construction of smooth dynamic contours composed of sections of the second-order curves. Smooth curves may have common tangents at the points of connection (first-order smoothness) or common radiuses of curvature (second-order smoothness). The algorithm of the dynamic connection of second-order curves based on the construction of homology linking constructible curve with the curvature circle has been developed. The algorithm allows solving the problem of synthesis - construction of the secondorder curve that has a predetermined curvature at this point. The four-point dynamic connection of second-order curves is considered. This connection provides the third-order smoothness. The examples of the construction of a smooth compound curve and pusher with the dynamic profile of the second-order smoothness are given.

关键词： projective algorithm order of smoothness curvature radius homology derivation pencil of circles second-order curve construction program

来源：评论

学校读者我要写书评

暂无评论

Shallow, deep and very deep cuts in the analytic center cutting plane method

引用

MATHEMATICAL PROGRAMMING 1999年第1期84卷 89-103页

作者： Goffin, JL Vial, JP McGill Univ Fac Management Gerad Montreal PQ H3A 1G5 Canada Univ Geneva Logilab CH-1211 Geneva 4 Switzerland

The analytic center cutting plane (ACCPM) methods aims to solve nondifferentiable convex problems. The technique consists of building an increasingly refined polyhedral approximation of the solution set. The linear inequalities that define the approximation are generated by an oracle as hyperplanes separating a query point from the solution set. In ACCPM, the query point is the analytic center, or an approximation of it, for the current polyhedral relaxation. A primal projective algorithm is used to recover feasibility and then centrality. In this paper we show that the cut doe's not need to go through the query point: it can be deep or shallow. The primal framework leads to a simple analysis of the potential variation, which shows that the inequality needed for convergence of the algorithm is in fact attained at the first iterate of the feasibility step.

关键词： projective algorithm analytic center cutting plane method

来源：评论

学校读者我要写书评

暂无评论

A path-following version of the Todd-Burrell procedure for linear programming

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 1997年第2期46卷 153-167页

作者： Vial, JP Univ Geneva LOGILAB Management Studies CH-1211 Geneva 4 Switzerland

We propose a path-following version of the Todd-Burrell procedure to solve linear programming problems with an unknown optimal value. The path-following scheme is not restricted to Karmarkar's primal step;it can a... 详细信息

关键词： projective algorithm path-following interior point method

来源：评论

学校读者我要写书评

暂无评论

SHORT STEPS WITH KARMARKARS projective algorithm FOR LINEAR-PROGRAMMING

引用

SIAM JOURNAL ON OPTIMIZATION 1994年第1期4卷 193-207页

作者： GOFFIN, JL VIAL, JP MCGILL UNIV FAC MANAGEMENTMONTREAL H3A 165PQCANADA DEPT ECON COMMERCIALE & IND CH-1211 GENEVA 4SWITZERLAND

A path-following, or short-step, version of Karmarkar's algorithm is proposed. When the first term of Karmarkar's potential function is given the weight (n + n(delta)), with delta greater than or equal to 0, the algorithm converges in O(n(max{delta/2,1-delta/2})L) iterations. The best convergence result O(root nL) is achieved for delta = 1. Two proofs of convergence are given: one based on duality gap reductions and the other on potential reductions. The weighted version of the standard projective algorithm is also analyzed. It is interpreted as a max-step algorithm. It is known to converge in at most O((n + n(delta))L) iterations. The reduction of the duality gap when an updating of the lower bound is performed is studied. It is shown to be of a multiplicative factor at most equal to 1 - n(delta)/(n + n(delta))(1 - theta), where 0 < theta < 1 is a fixed parameter in the algorithm. It is deduced from it that the total number of updates of the lower bound in the weighted projective algorithm is at most O(n(1-delta))L) for 0 less than or equal to delta less than or equal to 1.

关键词： LINEAR PROGRAMMING INTERIOR POINT METHOD projective algorithm PATH FOLLOWING

来源：评论

学校读者我要写书评

暂无评论

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 THE COMPUTATION OF WEIGHTED ANALYTIC CENTERS AND DUAL ELLIPSOIDS WITH THE projective algorithm

引用

MATHEMATICAL PROGRAMMING 1993年第1期60卷 81-92页

作者： GOFFIN, JL VIAL, JP UNIV GENEVA DEPT ECON COMMERCIALE & IND CH-1211 GENEVA 4 SWITZERLAND

The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimum. The minimization of this potential when the lower bound is kept fixed, yields a primal and a dual feasible solution. The dual solution is the weighted analytic center of a certain dual polytope. Finally one exhibits a pair of homothetic dual ellipsoids that extends results obtained by Sonnevend, Todd, Ye, Freund and Anstreicher.

关键词： projective algorithm ANALYTIC CENTERS DUAL ELLIPSOIDS

来源：评论

学校读者我要写书评

暂无评论

ON ANSTREICHERS COMBINED PHASE-I PHASE-II projective algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1992年第1期55卷 1-15页

作者： TODD, MJ 1. School of Operations Research and Industrial Engineering College of Engineering Cornell University 14853 Ithaca NY USA

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.

关键词： LINEAR PROGRAMMING INTERIOR-POINT METHOD projective algorithm COMBINING PHASE-I PHASE-II

来源：评论

学校读者我要写书评

暂无评论

DECOMPOSITION AND NONDIFFERENTIABLE OPTIMIZATION WITH THE projective algorithm

引用

MANAGEMENT SCIENCE 1992年第2期38卷 284-302页

作者： GOFFIN, JL HAURIE, A VIAL, JP ECOLE HAUTES ETUD COMMERCIALES MONTREAL GERADMONTREALQUEBECCANADA UNIV GENEVA DEPT ECON COMMERCIALE & INDCH-1211 GENEVA 4SWITZERLAND

This paper deals with an application of a variant of Karmarkar's projective algorithm for linear programming to the solution of a generic nondifferentiable minimization problem. This problem is closely related to the Dantzig-Wolfe decomposition technique used in large-scale convex programming. The proposed method is based on a column generation technique defining a sequence of primal linear programming maximization problems. Associated with each problem one defines a weighted potential function which is minimized using a variant of the projective algorithm. When a point close to the minimum of the potential function is reached, a corresponding point in the dual space is constructed, which is close to the analytic center of a polytope containing the solution set of the nondifferentiable optimization problem. An admissible cut of the polytope, corresponding to a new supporting hyperplane of the epigraph of the function of minimize, is then generated at this approximate analytic center. In the primal space this new cut translates into a new column for the associated linear programming problem. The algorithm has performed well on a set of convex nondifferentiable programming problems.

关键词： projective algorithm INTERIOR POINT METHOD CUTTING PLANE DECOMPOSITION NONDIFFERENTIABLE OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

A PRIMAL projective INTERIOR POINT METHOD FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1991年第1期51卷 17-43页

作者： GOLDFARB, D XIAO, D 1. Department of Industrial Engineering and Operations Research Columbia University 10027 New York NY USA

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.

关键词： INTERIOR POINT METHODS LINEAR PROGRAMMING FRACTIONAL LINEAR PROGRAMMING projective algorithm KARMARKARS algorithm POLYNOMIAL-TYPE algorithm

来源：评论

学校读者我要写书评

暂无评论

SEARCH DIRECTIONS FOR INTERIOR LINEAR-PROGRAMMING METHODS

引用

algorithmICA 1991年第2期6卷 153-181页

作者： GONZAGA, CC 1. Department of Electrical Engineering and Computer Sciences University of California 94720 Berkeley CA USA

Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure. We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).

关键词： KARMARKAR algorithm LINEAR PROGRAMMING projective algorithm CONICAL PROJECTION INTERIOR METHODS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：