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.

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.

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 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.

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 new primal-dual path-following interior-point algorithm for linearly constrained convex optimization

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(√n log n /ε).

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.

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.

A CORRECTOR-PREDICTOR ARC SEARCH INTERIOR-POINT ALGORITHM FOR SYMMETRIC OPTIMIZATION

In this paper, a corrector-predictor interior-point algorithm is proposed for sym- metric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iter- ates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algo- rithm is shown and it is proved that the algorithm has the complexity bound O （√τL） for the well-known Nesterov-Todd search direction and O （τL） for the xs and sx search directions.

A Modified Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

This paper proposes a new full Nesterov-Todd(NT) step infeasible interior-point algorithm for semidefinite programming. Our algorithm uses a specific kernel function, which is adopted by Liu and Sun, to deduce the feasibility step. By using the step, it is remarkable that in each iteration of the algorithm it needs only one full-NT step, and can obtain an iterate approximate to the central path. Moreover, it is proved that the iterative bound corresponds with the known optimal one for semidefinite optimization problems.

A POSITIVE INTERIOR-POINT ALGORITHM FOR NONLINEAR COMPLEMENTARITY PROBLEMS

A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.

Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.

A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

In this paper, we propose a new infeasible interior-point algorithm with full NesterovTodd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. We used a specific kernel function to induce the feasibility step. The analysis is more simplified. The iteration bound coincides with the currently best known bound for infeasible interior-point methods.

Interior-point algorithm based on general kernel function for monotone linear complementarity problem

A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.

Interior-Point Methods Applied to the Predispatch Problem of a Hydroelectric System with Scheduled Line Manipulations

Transmission line manipulations in a power system are necessary for the execution of preventative or corrective main- tenance in a network, thus ensuring the stability of the system. In this study, primal-dual interior-point methods are used to minimize costs and losses in the generation and transmission of the predispatch active power flow in a hydroelectric system with previously scheduled line manipulations for preventative maintenance, over a period of twenty-four hours. The matrix structure of this problem and the modification that it imposes on the system is also broached in this study. From the computational standpoint, the effort required to solve a problem with or without line manipulations is similar, and the reasons for this are also discussed in this study. Computational results sustain our findings.

Airborne gravimetry data sparse reconstruction via L1-norm convex quadratic programming

In practice, airborne gravimetry is a sub-Nyquist sampling method because of the restrictions imposed by national boundaries, financial cost, and database size. In this study, we analyze the sparsity of airborne gravimetry data by using the discrete Fourier transform and propose a reconstruction method based on the theory of compressed sensing for large- scale gravity anomaly data. Consequently, the reconstruction of the gravity anomaly data is transformed to a Ll-norm convex quadratic programming problem. We combine the preconditioned conjugate gradient algorithm （PCG） and the improved interior-point method （IPM） to solve the convex quadratic programming problem. Furthermore, a flight test was carried out with the homegrown strapdown airborne gravimeter SGA-WZ. Subsequently, we reconstructed the gravity anomaly data of the flight test, and then, we compared the proposed method with the linear interpolation method, which is commonly used in airborne gravimetry. The test results show that the PCG-IPM algorithm can be used to reconstruct large-scale gravity anomaly data with higher accuracy and more effectiveness than the linear interpolation method.

Two new predictor-corrector algorithms for second-order cone programming

Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms, two interior-point predictor-corrector algorithms for the second-order cone programming （SOCP） are presented. The two algorithms use the Newton direction and the Euler direction as the predictor directions, respectively. The corrector directions belong to the category of the Alizadeh-Haeberly-Overton （AHO） directions. These algorithms are suitable to the cases of feasible and infeasible interior iterative points. A simpler neighborhood of the central path for the SOCP is proposed, which is the pivotal difference from other interior-point predictor-corrector algorithms. Under some assumptions, the algorithms possess the global, linear, and quadratic convergence. The complexity bound O（rln（εo/ε）） is obtained, where r denotes the number of the second-order cones in the SOCP problem. The numerical results show that the proposed algorithms are effective.

Power System Reactive Power Optimization Based on Fuzzy Formulation and Interior Point Filter Algorithm

Considering the soft constraint characteristics of voltage constraints, the Interior-Point Filter Algorithm is applied to solve the formulation of fuzzy model for the power system reactive power optimization with a large number of equality and inequality constraints. Based on the primal-dual interior-point algorithm, the algorithm maintains an updating “filter” at each iteration in order to decide whether to admit correction of iteration point which can avoid effectively oscillation due to the conflict between the decrease of objective function and the satisfaction of constraints and ensure the global convergence. Moreover, the “filter” improves computational efficiency because it filters the unnecessary iteration points. The calculation results of a practical power system indicate that the algorithm can effectively deal with the large number of inequality constraints of the fuzzy model of reactive power optimization and satisfy the requirement of online calculation which realizes to decrease the network loss and maintain specified margins of voltage.

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.