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.

Checking weak and strong optimality of the solution to interval convex quadratic program

In this paper,we investigate three canonical forms of interval convex quadratic pro-gramming problems.Necessary and suficient conditions for checking weak and strong optimality of given vector corresponding to various forms of feasible region,are established respectively.By using the concept of feasible direction,these conditions are formulated in the form of linear systems with both equations and inequalities.In addition,we provide two specific examples to illustrate the efficiency of the conditions.

A Wide Neighborhood Arc-Search Interior-Point Algorithm for Convex Quadratic Programming

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^0）~TS^0/ε）） which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.

PREDICTOR-CORRECTOR ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING WITH UPPER BOUNDS

Predictor-corrector algorithm for linear programming, proposed by Mizuno et al.([1]), becomes the best well known in the interior point methods. The purpose of this paper is to extend these results in two directions. First, we modify the algorithm in order to solve convex quadratic programming with upper bounds. Second, we replace the corrector step with an iteration of Monteiro and Adler's algorithm([2]). With these modifications, the duality gap is reduced by a constant factor after each corrector step for convex quadratic programming. It is shown that the new algorithm has a O(root nL)-iteration complexity.

Stochastic level-value approximation for quadratic integer convex programming

We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

A Numerical Methodology for Enforcing Maximum Principles and the Non-Negative Constraint for Transient Diffusion Equations

Transient diffusion equations arise in many branches of engineering and applied sciences(e.g.,heat transfer and mass transfer),and are parabolic partial differential equations.It is well-known that these equations satisfy important mathematical properties like maximum principles and the non-negative constraint,which have implications in mathematical modeling.However,existing numerical formulations for these types of equations do not,in general,satisfy maximum principles and the nonnegative constraint.In this paper,we present a methodology for enforcing maximum principles and the non-negative constraint for transient anisotropic diffusion equation.The proposed methodology is based on the method of horizontal lines in which the time is discretized first.This results in solving steady anisotropic diffusion equation with decay equation at every discrete time-level.We also present other plausible temporal discretizations,and illustrate their shortcomings in meeting maximum principles and the non-negative constraint.The proposedmethodology can handle general computational grids with no additional restrictions on the time-step.We illustrate the performance and accuracy of the proposed methodology using representative numerical examples.We also perform a numerical convergence analysis of the proposed methodology.For comparison,we also present the results from the standard singlefield semi-discrete formulation and the results froma popular software package,which all will violate maximum principles and the non-negative constraint.

A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM

This paper indicates the possible difficulties for applying the interior point method to NPcomplete problems,transforms an NP-complete problem into a nonconvex quadratic program and then develops some convexity theories for it. Lastly it proposes an algorithm which uses Karmarkar's algorithm as a subroutine. The finite convergence of this algorithm is also proved.

Arc-search in numerical optimization

Determining the search direction and the search step are the two main steps of the nonlinear optimization algorithm,in which the derivatives of the objective and constraint functions are used to determine the search direction,the one-dimensional search and the trust domain methods are used to determine the step length along the search direction.One dimensional line search has been widely discussed in various textbooks and references.However,there is a lessknown techniquearc-search method,which is relatively new and may generate more efficient algorithms in some cases.In this paper,we will survey this technique,discuss its applications in different optimization problems,and explain its potential improvements over traditional line search method.

A Feasible Decomposition Method for Constrained Equations and Its Application to Complementarity Problems

In this paper, by analyzing the propositions of solution of the convex quadratic programming with nonnegative constraints, we propose a feasible decomposition method for constrained equations. Under mild conditions, the global convergence can be obtained. The method is applied to the complementary problems. Numerical results are also given to show the efficiency of the proposed method.