In this article, we extend kernel-based interior point algorithms for linear programming to convex quadratic programming overs second-order cones. By means of Jordan algebras, we establish the iteration complexity for...
详细信息
ISBN:
(纸本)9781467376822
In this article, we extend kernel-based interior point algorithms for linear programming to convex quadratic programming overs second-order cones. By means of Jordan algebras, we establish the iteration complexity for long-and short-step interior-point methods, namely, O (3 root N-2 log N/epsilon) and O (root N log N/epsilon), respectively. These results coincide with the ones obtained in the linear programming case.
It has been shown [8] that numerous interior-pointalgorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In th...
详细信息
It has been shown [8] that numerous interior-pointalgorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.
We show that most interior-pointalgorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following al...
详细信息
We show that most interior-pointalgorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.
We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic rea...
详细信息
We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.
This paper presents a general method for exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applic...
详细信息
This paper presents a general method for exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make intermittent contact, such as in dynamic simulations and in haptic interactions. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem. We use an interiorpoint method to solve the optimization problem and demonstrate that, for general convex objects represented as implicit surfaces, interiorpoint approaches are globally convergent, and fast in practice. Further, they provide polynomial-time guarantees for implicit surface objects when the implicit surfaces have self-concordant barrier functions. We use a primal-dual interiorpoint algorithm that solves the Karush-Kuhn-Tucker (KKT) conditions obtained from the convex programming formulation. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n(1.5)), where n is the number of constraints. We present implementation results for example implicit surface objects, including polyhedra, quadrics, and generalizations of quadrics such as superquadrics and hyperquadrics, as well as intersections of these surfaces. We demonstrate that in practice, the algorithm takes time linear in the number of constraints, and that distance computation rates of about 1 kHz can be achieved. We also extend the approach to proximity queries between deforming convex objects. Finally, we show that continuous collision detection for linearly translating objects can be performed by solving two related convex optimization problems. For polyhedra and quadrics, we establish that the computational complexity of this problem is also O(n(1.5)).
In this paper, we investigate a new primal-dual long-step interiorpoint algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-s...
详细信息
In this paper, we investigate a new primal-dual long-step interiorpoint algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.
An important issue in the implementation of interior point algorithms for linear programming is the recovery of an optimal basic solution from an optimal interiorpoint solution. In this paper we describe a method for...
详细信息
An important issue in the implementation of interior point algorithms for linear programming is the recovery of an optimal basic solution from an optimal interiorpoint solution. In this paper we describe a method for recovering such a solution. Our implementation links a high-performance interiorpoint code (OBI) with a high-performance simplex code (CPLEX). Results of our computational tests indicate that basis recovery can be done quickly and efficiently.
A linear programming interiorpoint algorithm is proposed for the solution of the problem of coordinating directional overcurrent relays in interconnected power systems considering definite time backup relaying. The p...
详细信息
A linear programming interiorpoint algorithm is proposed for the solution of the problem of coordinating directional overcurrent relays in interconnected power systems considering definite time backup relaying. The proposed algorithm is a variation of the primal-dual approach that uses multiple correctors of centrality. Pre-solution problem filtering simplification techniques are used prior to the application of the linear programming algorithm. Results are presented for the application of the methodology on a realistic test case, a 115-69 kV power system with 108 buses, 86 lines, 61 transformers, and 97 directional overcurrent relays. Optimal solutions are found in an automatic fashion, using the algorithm for the settings of the ground relays as well as for the phase relays. The application of the pre-solution problem simplification techniques is highly recommended, resulting in a significant reduction of the size and complexity of the linear programming problem to be solved. The interiorpoint approach reaches a feasible point in the close vicinity of the final optimal result in only one or two iterations. This fact represents an advantage for on-line applications. The proposed methodology and in particular the use of the presolve problem simplification techniques is shown as a new valuable tool for the setting of directional overcurrent relays in interconnected power systems. (C) 2001 Elsevier Science Ltd. All rights reserved.
Nonlinear image deblurring procedures based on probabilistic considerations have been widely investigated in the literature. This approach leads to model the deblurring problem as a large scale optimization problem, w...
详细信息
Nonlinear image deblurring procedures based on probabilistic considerations have been widely investigated in the literature. This approach leads to model the deblurring problem as a large scale optimization problem, with a nonlinear, convex objective function and non-negativity constraints on the sign of the variables. The interiorpoint methods have shown in the last years to be very reliable in nonlinear programs. In this paper we propose an inexact Newton interiorpoint (IP) algorithm designed for the solution of the deblurring problem. The numerical experience compares the IP method with another state-of-the-art method, the Lucy Richardson algorithm, and shows a significant improvement of the processing time. (C) 2009 Elsevier B.V. All rights reserved.
A simple interiorpoint method is proposed for solving a system of linear equations subject to nonnegativity constraints. The direction of update is defined by projection of the current solution on a linear manifold d...
详细信息
A simple interiorpoint method is proposed for solving a system of linear equations subject to nonnegativity constraints. The direction of update is defined by projection of the current solution on a linear manifold defined by the equations. Infeasibility is discussed and extension for free and bounded variables is presented. As an application, we consider linear programming problems and a comparison with a state-of-the-art primal-dual infeasible interiorpoint code is presented. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论