Relaxed Stability Criteria for Time-Delay Systems:A Novel Quadratic Function Convex Approximation Approach

This paper develops a quadratic function convex approximation approach to deal with the negative definite problem of the quadratic function induced by stability analysis of linear systems with time-varying delays.By introducing two adjustable parameters and two free variables,a novel convex function greater than or equal to the quadratic function is constructed,regardless of the sign of the coefficient in the quadratic term.The developed lemma can also be degenerated into the existing quadratic function negative-determination(QFND)lemma and relaxed QFND lemma respectively,by setting two adjustable parameters and two free variables as some particular values.Moreover,for a linear system with time-varying delays,a relaxed stability criterion is established via our developed lemma,together with the quivalent reciprocal combination technique and the Bessel-Legendre inequality.As a result,the conservatism can be reduced via the proposed approach in the context of constructing Lyapunov-Krasovskii functionals for the stability analysis of linear time-varying delay systems.Finally,the superiority of our results is illustrated through three numerical examples.

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

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.

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 Large-update Interior-point Algorithm for Convex Quadratic Semi-definite Optimization Based on a New Kernel Function

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be O（√n（logn）2 log e/n）. This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and in optimization fields. Some computational results recent kernel functions introduced by some authors have been provided.

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.

A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

In this paper,we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems.Using the Nesterov–Todd direction as the search direction,we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm.Although the algorithm belongs to the class of large-step interior-point algorithms,its complexity coincides with the best iteration bound for short-step interior-point algorithms.The algorithm is also implemented to demonstrate that it 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.

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.

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

TWO NOVEL GRADIENT METHODS WITH OPTIMAL STEP SIZES

In this work we introduce two new Barzilai and Borwein-like steps sizes for the classical gradient method for strictly convex quadratic optimization problems.The proposed step sizes employ second-order information in order to obtain faster gradient-type methods.Both step sizes are derived from two unconstrained optimization models that involve approximate information of the Hessian of the objective function.A convergence analysis of the proposed algorithm is provided.Some numerical experiments are performed in order to compare the efficiency and effectiveness of the proposed methods with similar methods in the literature.Experimentally,it is observed that our proposals accelerate the gradient method at nearly no extra computational cost,which makes our proposal a good alternative to solve large-scale problems.

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.