We report experiments of an implementation of a primal-dual interiorpointalgorithm for solving mechanical models of one-sided contact problems with Coulomb friction. The objective is to recover an optimal solution w...
详细信息
We report experiments of an implementation of a primal-dual interiorpointalgorithm for solving mechanical models of one-sided contact problems with Coulomb friction. The objective is to recover an optimal solution with high accuracy and as quickly as possible. These developments are part of the design of Siconos, an open-source software for modelling and simulating non-smooth dynamical systems. Currently, Siconos uses mainly first-order methods for the numerical solution of these systems. These methods are very robust, but suffer from a linear rate of convergence and are therefore too slow to find accurate solutions in a reasonable time. Our main objective is to apply second-order methods to speed up convergence. In this paper, we focus on solving a relaxed formulation of the initial mechanical model, corresponding to the optimality conditions of a convex quadratic minimization problem with second-order cone constraints. We will present in detail a primal-dual interiorpointalgorithm for solving this type of problem. The main difficulty in implementing this algorithm arises from the fact that at each iteration of the algorithm, a change of variable, called a scaling, has to be performed in order to guarantee the non-singularity of the linear system to be solved, as well as to recover a symmetric system. Although this scaling strategy is very nice from a theoretical point of view, it leads to an enormous deterioration of the conditioning of the linear system when approaching the optimal solution and therefore to all the numerical difficulties that result from it. We will describe in detail the numerical algebra that we have developed in our implementation, in order to overcome these problems of numerical instability. We will also present the solution of the models resulting from the problems of rolling friction, for which the cone of constraints is no longer self-dual like the Lorentz cone.
In this paper, we consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the wei...
详细信息
In this paper, we consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the weighted analytic centre of a polytope. We show that the problem has a dual of the same form and give complexity results for several different interior-point algorithms. We obtain an improved complexity result for certain cases by utilizing a combination of the volumetric and logarithmic barriers. As an application, we consider the complexity of solving the Eisenberg-Gale formulation of a Fisher equilibrium problem with linear utility functions.
An interior-point trust-region algorithm is proposed for minimization of a convex quadratic objective function over a general convex set. The algorithm uses a trust-region model to ensure descent on a suitable merit f...
详细信息
An interior-point trust-region algorithm is proposed for minimization of a convex quadratic objective function over a general convex set. The algorithm uses a trust-region model to ensure descent on a suitable merit function. The complexity of our algorithm is proved to be as good as the interior-point polynomial algorithm.
We introduce an interior-point algorithm for linear optimization, which is based on a new technique for determining search directions. This method consists of a new type of transformation on the centering equations of...
详细信息
We introduce an interior-point algorithm for linear optimization, which is based on a new technique for determining search directions. This method consists of a new type of transformation on the centering equations of the system which characterizes the central path. It can be shown that these new directions cannot be derived from usual kernel functions. Therefore, we extend the concept of the kernel functions, and we establish an equivalence between this approach and the proposed method for obtaining search directions. Moreover, we prove the polynomial complexity of the algorithm.
Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal-dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approxima...
详细信息
Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal-dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interiorpoints, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima-Megiddo-Mizuno algorithm ''solves'' the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop an O(nL)-iteration complexity result for a variant of the algorithm.
We propose new short-step interior-point algorithms (IPAs) for solving P.(? )-linear complementarity problems (LCPs). In order to define the search directions, we use the algebraic equivalent transformation (AET) tech...
详细信息
We propose new short-step interior-point algorithms (IPAs) for solving P.(? )-linear complementarity problems (LCPs). In order to define the search directions, we use the algebraic equivalent transformation (AET) technique of the system describing the central path. A novelty of the paper is that we introduce a whole, new class of AET functions for which a unified complexity analysis of the IPAs is presented. This class of functions differs from the ones used in the literature for determining search directions, like the class of concave functions determined by Haddou, Migot and Omer, self-regular functions, eligible kernel and self-concordant functions. We prove that the IPAs using any member ? of the new class of AET functions have polynomial iteration complexity in the size of the problem, in starting point's duality gap, in the accuracy parameter and in the parameter ?.
Lower-bound shakedown analysis leads to nonlinear convex optimization problems with large numbers of unknowns and constraints, the solution of which can be obtained efficiently by interior-point algorithms. The perfor...
详细信息
Lower-bound shakedown analysis leads to nonlinear convex optimization problems with large numbers of unknowns and constraints, the solution of which can be obtained efficiently by interior-point algorithms. The performance of these algorithms strongly depends on the choice of the starting point. In general, starting points should be located inside the feasible region. In addition, they should also be well centred. Although there exist several heuristics for the construction of suitable starting points, these are restricted, as long as only the mathematical procedure is considered without taking into account the nature of the underlying mechanical problem. Thus, in this article, a strategy is proposed for choosing appropriate starting points for interior-point algorithms applied to shakedown analysis. This strategy is based on both the mathematical characteristics and the physical meaning of the variables involved. The efficiency of the new method is illustrated by numerical examples from the field of power plant engineering.
In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.（k） nonlinear complementarity problem （NCP）, which are based on a class of kernel functions investigated by Bai et a...
详细信息
In this paper we propose a class of new large-update primal-dual interior-point algorithms for P.（k） nonlinear complementarity problem （NCP）, which are based on a class of kernel functions investigated by Bai et al. in their recent work for linear optimization （LO）. The arguments for the algorithms are followed as Peng et al.＇s for P.（n） complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.： Self-Regularity： A New Paradigm for Primal-Dual interior- pointalgorithms, Princeton University Press, Princeton, 2002]. It is worth mentioning that since this class of kernel functions includes a class of non-self-regular functions as special case, so our algorithms are different from Peng et al.＇s and the corresponding analysis is simpler than theirs. The ultimate goal of the paper is to show that the algorithms based on these functions have favorable polynomial complexity.
暂无评论