Search

International audience; In this paper we propose a family of affine scaling interior point algorithms, called galpv4, using a primal approach, based on a large class of differential barrier functions. We show that these algorithms are in fact an extension and generalization of the classical affine scaling algorithm based on the well-known log barrier function. After carrying out a complete convergence analysis, we select some of these algorithms for comparison with the classical affine scaling algorithm, performed with the help of the familiar Netlib test set.

In this paper, an Improved Affine-Scaling Interior Point Algorithm for Linear Programming has been proposed. Computational results of selected practical problems affirming the proposed algorithm have been provided. The proposed algorithm is accurate, faster and therefore reduces the number of iterations required to obtain an optimal solution of a given Linear Programming problem as compared to the already existing Affine-Scaling Interior Point Algorithm. The algorithm can be very useful for development of faster software packages for solving linear programming problems using the interior-point methods.

Chen and Zhang [Sci. China, Ser. A, 45, 1390–1397 (2002)] introduced an affine scaling trust region algorithm for linearly constrained optimization and analyzed its global convergence. In this paper, we derive a new affine scaling trust region algorithm with dwindling filter for linearly constrained optimization. Different from Chen and Zhang’s work, the trial points generated by the new algorithm are accepted if they improve the objective function or improve the first order necessary optimality conditions. Under mild conditions, we discuss both the global and local convergence of the new algorithm. Preliminary numerical results are reported.

In this paper, the dimension function of a self-affine generalized scaling set associated with an n×n integral expansive dilation A is studied. More specifically, we consider the dimension function of an A-dilation generalized scaling set K assuming that K is a self-affine tile satisfying BK = (K+d1)[ (K + d2), where B = At , A is an n×n integral expansive matrix with |det A| = 2, and d1, d2 ∊ ℝn. We show that the dimension function of K must be constant if either n = 1 or 2 or one of the digits is 0, and that it is bounded by 2|K| for any n.

Analytical models of the actual structure often differ greatly from their as-built counterparts. Model updating techniques improve the predictions of the behavior of the actual structure by identifying and correcting the uncertain parameters of the analytical model. This paper presents a new model updating technique to improve the finite element analysis model by updating design parameters using strain measurement based on affine scaling interior Algorithm. Static strain measurements are more reliable and realistic than acceleration data in practice. Numerical examples are presented to study the application of the method.

In this paper we extend and improve the classical affine scaling interior-point Newton method for solving nonlinear optimization subject to linear inequality constraints in the absence of the strict complementarity assumption. Introducing a computationally efficient technique and employing an identification function for the definition of the new affine scaling matrix, we propose and analyze a new affine scaling interior-point Newton method which improves the Coleman and Li affine scaling matrix in [2] for solving the linear inequality constrained optimization. Local superlinear and quadratical convergence of the proposed algorithm is established under the strong second order sufficiency condition without assuming strict complementarity of the solution.

In this paper, we propose a new interior point algorithm for linear programming by combining the affine scaling algorithm and the primal path-following algorithm. We define a series of subproblems whose feasible region contracts toward the set of optimal solutions. In each iteration, we take a step in the steepest descent direction in a transformed space to reduce the objective value. Our preliminary computational results are very favorable.

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.

The affine scaling algorithm for linear programming involves a step-size parameter t that must be chosen in the interval (0,1). It is known that the algorithm converges to an optimal solution for values of $t \le 2/3$. In this paper we examine the behavior of the algorithm for values of t > 2/3. We show that for certain values of t in this range the algorithm can exhibit chaotic behavior.

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.

In this paper we consider the primal affine scaling method and show that, asymptotically, a step selection strategy exists which can be viewed as a predictor-corrector method. We investigate two step selection strategies. In the first, one corrector step is taken between each pair of predictor steps, and we call this the 2-step method. In the other two such steps are taken, which we call the 3-step method. We show that the 2-step method attains a superlinear rate of 1.5 while the 3-step method attains a quadratic convergence rate. This improves upon the work of Tsuchiya and Monteiro, who obtain a 2-step rate of 1.3.

In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.

Adler and Monteiro (1992) developed a parametric analysis approach that is naturally related to the geometry of the linear program. This approach is based on the availability of primal and dual optimal solutions satisfying strong complementarity. In this paper, we develop an alternative geometric approach for parametric analysis which does not require the strong complementarity condition. This parametric analysis approach is used to develop range and marginal analysis techniques which are suitable for interior point methods. Two approaches are developed, namely the LU factorization approach and the affine scaling approach.

In this paper we deal with global convergence of the affine scaling algorithm for strictly convex QP problems satisfying a dual nondegeneracy condition. By means of the local Karmarkar potential function which was successfully applied to demonstrate global convergence of the affine scaling algorithm for LP, we show global convergence of the algorithm when the step-size 1/8 is adopted without requiring any primal nondegeneracy condition.

This paper presents a multiobjective linear programming (MOLP) algorithm that is based on one variant of Karmarkar's interior-point algorithm known as the affine scaling primal algorithm. We show that by using convex combinations of individual projected gradients, we derive a combined direction along which we step toward the next iterate. We refer to the class of MOLP algorithms resulting from this variant as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.

Blur in images can be removed by solving a series of box‐constrained linear least‐squares problems. In this paper, we compare two recent approaches for solving these problems using affine‐scaling methods. Both approaches aim at solving a nonlinear system arising from the Karush‐Kuhn‐Tucker condition. One approach is to identify the active set and update the inactive components of the iterates by using a Newton‐like method. The other is to iteratively solve the nonlinear system entry‐wise by a Quasi‐Newton method.

This paper proposes a stochastic improvement method for a linear programming problem which has linear constraints that contain unknown coefficients. The unknown coefficients are estimated using multivariate regression analysis. We update the estimates of unknown coefficients as well as the solution by making use of an affine scaling method, whenever new statistical data are delivered. It is shown that this iteration of improvements finds the point that gives the optimal value with probability one, which is based on the fact that the consistency of the estimator assures that the estimated problem converges to the problem with true parameters.

In this paper, the authors address several issues in solving nonlinear optimal power flow (OPF) problems via sequential linear programming (SLP) with interior point (IP) methods. Two computationally effective IP methods are considered: dual affine scaling and primal-dual logarithmic barrier. A prototype code in Matlab/sup TM/ was developed and made available for educational purposes. By manipulating parameters, users can obtain insights into the issues of OPF solutions via SLP with IP methods.

In this paper, we explore the general structure of primal scaling interior point methods. Specifically, we are able to analyze the primal scaling path-following method, potential reduction method and low-complexity affine scaling method under one simple framework. We believe that this approach provides a simple but inside analysis to understand interior point methods.

In this chapter we will briefly discuss the IPMs mentioned in Section 1.3 and not treated in the previous chapters. First we will treat the path—following methods, especially the primal—dual path—following method, since the dual (primal) path—following methods are treated in the previous chapters. Then we discuss the affine scaling method, the projective and affine potential reduction methods. Following the literature, the methods are mainly described for the primal problem(LP)(the dual problem can be treated analogously). Some open problems will also be indicated. We will not give a detailed description of all these methods. (More detailed survey papers are [45], [55], [138] and [154].) Our aim is to show that all these methods rely on some common notions: they all use the central path somehow, and the search directions are all linear combinations of two characteristic vectors. These comparisons will be carried out in the last section.

This paper describes the implementation of some particular interior point methods within the programming package for solving linear programming problems on PC. Based on the primal version of the affine scaling methods, some algorithmic variants are described. The main emphasis is on the data structures and algorithms which allow economical and efficient solution of a quite large problems on the standard MS-DOS PC. Implementation issues particular to interior point methods, such as treatment of dense columns and bypassing the problem of inverting a badly conditioned matrix are also discussed. The code was already tested on several standard linear programming problems and showed encouraging performance.

This paper describes a modified Karmarkar algorithm for solving linear programming problems. This algorithm overcomes the problem of maintaining feasibility during the projective step and uses a constraint partitioning scheme which greatly improves the efficiency of the projective step. The new algorithm proves to be two to three times as fast as the IMSL FORTRAN subroutine ZX4LP in solving moderate size linear programs.