Search

We report experiments of an implementation of a primal–dual interior point algorithm 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 interior point algorithm 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. [ABSTRACT FROM AUTHOR]

In this paper, a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed. The algorithm employs a kernel function with a linear growth term to derive the search direction, and by introducing new technical results and selecting suitable parameters, we prove that the iteration bound of the algorithm is as good as best-known polynomial complexity of interior-point methods. Furthermore, numerical results illustrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O( nlog(( x ) s /ε)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient. [ABSTRACT FROM AUTHOR]

In this paper, we propose a short-step feasible full-Newton step path-following interior-point algorithm (IPA) for monotone linear complementarity problems (LCPs). The proposed IPA uses the technique of algebraic equivalent transformation (AET) induced by an univariate function to transform the centering equations which defines the central-path. By applying Newton's method to the modified system of the central-path of LCP, a new Newton search direction is obtained. Under new appropriate defaults of the threshold τ which defines the size of the neighborhood of the central-path and of θ which determines the decrease in the barrier parameter, we prove that the IPA is well-defined and converges locally quadratically to a solution of the monotone LCPs. Moreover, we derive its iteration bound, namely, O(√nlog n\ϵ) O n log n ε $ \mathcal{O}\left(\sqrt{n}\mathrm{log}\frac{n}{\epsilon }\right)$ which coincides with the best-known iteration bound for such algorithms. Finally, some numerical results are presented to show its efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be $$O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)$$. This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided. [ABSTRACT FROM AUTHOR]

This paper establishes the polynomial convergence of a new class of path-following methods for linear complementarity problems (LCP) whose search directions are obtained by applying Newton's method to the central path equation Xz = μe; Mx - c = z: Specifically, we show that the short-step path-following methods based on the L∞ norm neighborhood and the semilong-step path-following methods based on the L∞ seminorm neighborhood have the iteration-complexity bounds of O(n), respectively. [ABSTRACT FROM AUTHOR]

In this paper we propose a class of new large-update primal-dual interior-point algorithms for P( κ) 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( κ) complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, 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. [ABSTRACT FROM AUTHOR]

In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization (LCCO) is presented. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, only full-Newton steps are used. Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O(√ nlog n/ε). [ABSTRACT FROM AUTHOR]

This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function. [ABSTRACT FROM AUTHOR]

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O( nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function where x is the vector of primal variables and s is the vector of dual slack variables, and q = n + $$\sqrt n $$ . The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O( $$\sqrt n $$ L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function where q = n + $$\sqrt n $$ . We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameter q in the following sense. Suppose that q = n + n where t⩾0. Then the algorithm will solve the linear program in O( n L) iterations, where r = max{ t, 1 − t}. Thus the value of t that minimizes the complexity bound is t = 1/2, yielding Ye's O( $$\sqrt n $$ L) iteration bound. [ABSTRACT FROM AUTHOR]

In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. We show that if a strictly feasible starting point is available, then the new algorithm has O (n3/4log/n/ε) iteration complexity. [ABSTRACT FROM AUTHOR]

The paper deals with a variant of the interior-point method for the minimization of strictly quadratic objective function subject to simple bounds and separable quadratic inequality constraints. Such minimizations arise from the finite element approximation of contact problems of linear elasticity with friction in three space dimensions. The main goal of the paper is the convergence analysis of the algorithm and its implementation. The optimal preconditioners for solving ill-conditioned inner linear systems are proposed. Numerical experiments illustrate the computational efficiency for large-scale problems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of a simple locally kernel function. As an application, we present a full-step interior-point algorithm for second-order cone optimization (SOCO). The algorithm uses the simple locally kernel function to determine the search direction and define the neighbourhood of central path. The full step used in the algorithm has local quadratic convergence property according to the proximity function which is constructed by the simple locally kernel function. We derive the iteration complexity for the algorithm and obtain the best-known iteration bound for SOCO. [ABSTRACT FROM AUTHOR]

In this paper, we present a new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones by employing the framework of Euclidean Jordan algebras. At each iteration, we use only full Nesterov and Todd steps. The currently best known iteration bound for small-update method, namely, $O(\sqrt{r}\log{\frac{r}{\varepsilon}})$, is obtained, where r denotes the rank of the associated Euclidean Jordan algebra and ε the desired accuracy. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis for linear, convex quadratic and semidefinite optimizations. [ABSTRACT FROM AUTHOR]

Interior-point methods (IPMs) for linear optimization (LO) and semidefinite optimization (SDO) have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods (IPMs) for semidefinite optimization (SDO) is designed. And the iteration complexity of the algorithm as O( n 3/4 log n/∈) with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O( n log n/te) in large-updates case. [ABSTRACT FROM AUTHOR]

In this paper, we present a new large-update interior-point algorithm for $$P_*(\kappa )$$ -linear complementarity problem. The new algorithm is based on a trigonometric kernel function which differs from the existing kernel functions in which it has a double barrier term. By a simple analysis, we show that the new algorithm enjoys $${ O}((1+2\kappa )n^\frac{2}{3}\log \frac{n}{\varepsilon })$$ iteration complexity. This complexity estimate improves a result from El Ghami et al. (Optim Theory Decis Mak Oper Res Appl 31: 331-349, 2013) and matches the currently best known complexity result for $$P_*(\kappa )$$ -linear complementarity problem based on trigonometric kernel functions. [ABSTRACT FROM AUTHOR]

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 interior points, 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. [ABSTRACT FROM AUTHOR]

A stable symmetrization of the linear systems arising in interior-point methods for solving linear programs is introduced. A comparison of the condition numbers of the resulting interior-point linear systems with other commonly used approaches indicates that the new approach may be best suitable for an iterative solution. It is shown that there is a natural generalization of this symmetrization to the Nesterov-Todd (NT) search direction for solving semidefinite programs. The generalization includes a novel pivoting strategy to minimize the norm of the right and side and heavily relies on the symmetry properties of the NT direction. The search directions generated by iterative solvers typically have fairly low relative accuracy. Nevertheless, in some preliminary numerical examples, a suitably adapted interior-point approach results in a rather small number of outer iterations. [ABSTRACT FROM AUTHOR]

SUMMARY Determining the load-bearing capacity of engineering structures is essential for their design. In the case of varying thermo-mechanical loading beyond the elastic limit, the statical shakedown analysis constitutes a particularly suitable tool for this. The application of the statical shakedown theorem, however, leads to a nonlinear convex optimization problem, which is typically characterized by large numbers of variables and constraints. In the present work, this optimization problem is solved by a primal-dual interior-point algorithm, which shows a remarkable performance due to its problem-tailored formulation. Nevertheless, the solution procedure remains still a demanding task from computational point of view. Thus, the aim of this paper is to tackle the task of solving large-scale problems by use of a new so-called selective algorithm. This algorithm detects automatically the plastically most affected zones within the structure, which have the highest influence on the solution. The entire system is then reduced to a substructure consisting of these zones, based upon which a new optimization problem can be set up, which is solved with significantly less effort. Consequently, the running time decreases drastically, as is shown by application to numerical examples from the field of power plant engineering. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

This article presents a mixture three-parameter Weibull distribution to model wind speed data. The parameters are estimated by using maximum likelihood (ML) method in which the maximization problem is regarded as a nonlinear programming with only inequality constraints and is solved numerically by the interior-point method. By applying this model to four lattice-point wind speed sequences extracted from National Centers for Environmental Prediction (NCEP) reanalysis data, it is observed that the mixture three-parameter Weibull distribution model proposed in this paper provides a better fit than the existing Weibull models for the analysis of wind speed data under study. [ABSTRACT FROM AUTHOR]

A v-gap optimisation-based frequency-domain identification method is proposed to estimate a nominal normalised right graph symbol for errors-in-variables models. The proposed method follows the similar identification idea from a previous research work but with improved computational efficiency using interior-point (IP) algorithms. By imposing an inner function constraint instead of frequency point-wise constraints to normalise the graph symbol, the number of involved equality constraints for the v-gap optimisation is related to the nominal model order instead of the data length. As a consequence, the computational complexity of the proposed IP-based identification algorithm is much lower than that of linear matrix inequalities-based algorithms. Due to the fact that the data length is typically much larger than the finite nominal model order, the number of saved equality constraints is close to that of the employed data points. Finally, two numerical simulation examples are given to verify the proposed identification method. [ABSTRACT FROM AUTHOR]

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming (LP) problems. The algorithms are based on a few kernel functions, including both self-regular functions and non-self-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynamic step size are more efficient than those with fixed step size. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of following a trajectory from an infeasible starting point directly to an optimal solution of the linear programming problem. A class of trajectories for the problem is defined, based on the notion of a β-balanced solution to the problem. Given a prespecified positive balancing constant β, an infeasible solution x is said to be β-balanced if the optimal value gap is less than or equal to β times the infeasibility gap. Mathematically, this can be written as cTx - Z* ≤ βξTx, where the linear form ξTx is the Phase I objective function and z* is the optimal objective value of the linear program. The concept of a /3-balanced solution is used to define a class of trajectories from an infeasible point to an optimal solution of a given linear program. Each trajectory has the property that all points on or near the trajectory (in a suitable metric) are /3-balanced. The main thrust of the paper is the development of an algorithm that traces a given β-balanced trajectory from a starting point near the trajectory to an optimal solution to the given linear programming problem in polynomial time. More specifically, the algorithm allows for fixed improvement in the bound on the Phase I and the Phase II objectives in 0(n) Newton steps. [ABSTRACT FROM AUTHOR]

In this paper we show that the primal-dual Dikin affine scaling algorithm for linear programming of Jansen. Roos and Terlaky enhances an asymptotical $$O(\sqrt n L)$$ complexity by using corrector steps. We also show that the result remains valid when the method is applied to positive semi-definite linear complementarity problems. [ABSTRACT FROM AUTHOR]

As in many primal-dual interior-point algorithms, a primal-dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence. [ABSTRACT FROM AUTHOR]

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this 'interior point' philosophy can be adapted to the linear ℓ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide a globally and ultimately quadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim. [ABSTRACT FROM AUTHOR]

The load bearing capacity of engineering structures subjected to varying thermo-mechanical loading can be determined most conveniently by shakedown analysis. Admittedly, if limited kinematical hardening is considered, shakedown analysis is, as yet, restricted to either one or two independently varying loads. In consequence, the aim of this paper is to extend existing formulations for arbitrary numbers of loading, which is inevitable for most technical applications. For this, limited kinematical hardening was incorporated into Melan’s shakedown theorem by means of a two-surface model covering both alternating plasticity and ratcheting, generalized to n -dimensional loading spaces. As a result, the three-dimensional shakedown domain accounting for hardening is presented for a flanged pipe subjected to thermo-mechanical loading. [ABSTRACT FROM AUTHOR]

Abstract: In this paper a class of polynomial interior-point algorithms for the Cartesian second-order cone linear complementarity problem based on a parametric kernel function, with parameters and , are presented. The proposed parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and the -center for the algorithms. Moreover, the currently best known iteration bounds for the large- and small-update methods, namely, and , are obtained, respectively, which reduce the gap between the practical behavior of the algorithms and its theoretical performance results. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, , where N denotes the number of second-order cones in the problem formulation and the desired accuracy. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new primal-dual interior-point algorithm for solving a special case of convex quadratic semi-definite optimization based on a parametric kernel function. The proposed parametric kernel function is used both for determining the search directions and for measuring the distance between the given iterate and the -center for the algorithm. These properties enable us to derive the currently best known iteration bounds for the algorithm with large- and small-update methods, namely, and , respectively, which reduce the gap between the practical behavior of the algorithm and its theoretical performance results. [Copyright &y& Elsevier]

Abstract: In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, , which is as good as the linear analogue. [Copyright &y& Elsevier]

This paper aims at the analysis of the VdP heartbeat mathematical model. We have analysed the conditionality of a mathematical model which represents the oscillatory behaviour of the heart. A novel neuroevolutionary approach is chosen to analyse the mathematical model. The characteristics of the cardiac pulse of the heart are examined by considering two major scenarios with sixteen different cases. Artificial neural networks (ANNs) are constructed to obtain the best solutions for the heartbeat model. Unknown weights are finely tuned by a combination of a global search technique the Harris Hawks Optimizer (HHO) and a local search technique the Interior Point Algorithm (IPA). Stable behaviour of solutions obtained by considering different cases demonstrates that the model under consideration is well-conditioned. The accuracy of our novel procedure is established by getting the lowest residual errors in our solution for all cases. Graphical and statistical analysis are added to further elaborate the accuracy of our approach.