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-orde...
详细信息
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.
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 in...
详细信息
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.
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...
详细信息
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 also be implemented with a dual Newton step or with a primal-dual step.
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, t...
详细信息
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.
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 a...
详细信息
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.
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 ...
详细信息
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.
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 sear...
详细信息
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.
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 ...
详细信息
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.
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 sequenc...
详细信息
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.
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. T...
详细信息
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).
暂无评论