Search

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.

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.

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.

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.

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.

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.