A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming （SOCP） by using the Alizadeh- Haeberly-Overton （AHO） search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an -approximate solution of an SOCP in at most O（√n ln（ε0/ε）） iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

A predictor-corrector interior-point algorithmfor monotone variational inequality problems

Mehrotra's recent suggestion of a predictor corrector variant of primal dual interior point method for linear programming is currently the interior point method of choice for linear programming. In this work the authors give a predictor corrector interior point algorithm for monotone variational inequality problems. The algorithm was proved to be equivalent to a level 1 perturbed composite Newton method. Computations in the algorithm do not require the initial iteration to be feasible. Numerical results of experiments are presented.

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.

Predictor-corrector interior-point algorithm for linearly constrained convex programming

Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.

NEW FIXED POINT THEOREMS OF CONDENSING MAPPINGS SATISFYING THE INTERIOR CONDITION IN BANACH SPACES

In this paper, based on a basic result on condensing mappings satisfying the interior condition, some new fixed point theorems of the condensing mappings of this kind are obtained. As a result, the famous Altman＇s theorem, Roth＇s theorem and Petryshyn＇s theorem are extended to condensing mappings satisfying the interior condition.

Several Inequalities Involving Two Simplexes and Interior Points

This article establishes several new geometric inequalities, which refer to the lengthes of the edges of a simplex and interior point, height, lateral area, and the circumradius of another simplex.

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions, we propose a combined homotopy infeasible interior-point method （CHIIP） for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.

Penalized interior point approach for constrained nonlinear programming

A penalized interior point approach for constrained nonlinear programming is examined in this work. To overcome the difficulty of initialization for the interior point method, a problem equivalent to the primal problem via incorporating an auxiliary variable is constructed. A combined approach of logarithm barrier and quadratic penalty function is proposed to solve the problem. Based on Newton＇s method, the global convergence of interior point and line search algorithm is proven. Only a finite number of iterations is required to reach an approximate optimal solution. Numerical tests are given to show the effectiveness of the method.

Element-free Galerkin method for free vibration of rectangular plates with interior elastic point supports and elastically restrained edges

The element-free Galerkin method is proposed to solve free vibration of rectangular plates with finite interior elastic point supports and elastically restrained edges.Based on the extended Hamilton＇s principle for the elastic dynamics system,the dimensionless equations of motion of rectangular plates with finite interior elastic point supports and the edge elastically restrained are established using the element-free Galerkin method.Through numerical calculation,curves of the natural frequency of thin plates with three edges simply supported and one edge elastically restrained,and three edges clamped and the other edge elastically restrained versus the spring constant,locations of elastic point support and the elastic stiffness of edge elastically restrained are obtained.Effects of elastic point supports and edge elastically restrained on the free vibration characteristics of the thin plates are analyzed.

An Improved Affine-Scaling Interior Point Algorithm for Linear Programming

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.

Dynamic economic dispatch combining network flow and interior point method

Under the environment of electric power market, economic dispatch (ED) problem should consider network constraints, unit ramp rates, besides the basic constraints. For this problem, it is important to establish the effective model and algorithm. This paper examines the decoupled conditions that affect the solution optimality to this problem. It proposes an effective model and solution method. Based on the look-ahead technique, it finds the number of time intervals to guarantee the solution optimality. Next, an efficient technique for finding the optimal solution via the interior point methods is described. Test cases, which include dispatching six units over 5 time intervals on the IEEE 30 test system with line flows and ramp constraints are presented. Results indicate that the computational effort as measured by iteration counts or execution time varies only modestly with the problem size.

A new primal-dual interior-point algorithm for convex quadratic optimization

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization （CQO） based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method （IPM） to O（√n log nlog n/e）, which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.

A class of polynomial primal-dual interior-point algorithms for semidefinite optimization

In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.

Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

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/ε） in large-updates case.

Primal-Dual Interior-Point Algorithms with Dynamic Step-Size Based on Kernel Functions for Linear Programming

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 serf-regular functions and non-serf-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 dynaraic step size are more efficient than those with fixed step size.

A New Infeasible Interior-point Method for Linear Complementarity Problem Based on Full Newton Step

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

A Note on the Existence of a Specified Number of Interior Points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let h（κ） be the smallest integer such that every set of points in the plane, no three collinear, with at least h（κ） interior points, has a subset of points with exactly κ or κ ＋ 1 interior points of P. We prove that h（5）=11.