THE BERNSTEIN TYPE INEQUALITY AND SIMULTANEOUS APPROXIMATION BY INTERPOLATION POLYNOMIALS IN COMPLEX DOMAIN

In this paper we investigate simultaneous approximation for arbitrary system of nodes on smooth domain in complex plane. Some results which are better than those of known theorems are obtained.

QUASIPERIODICITY OF TRANSCENDENTAL MEROMORPHIC FUNCTIONS

This paper is devoted to considering the quasiperiodicity of complex differential polynomials,complex difference polynomials and complex delay-differential polynomials of certain types,and to studying the similarities and differences of quasiperiodicity compared to the corresponding properties of periodicity.

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.

COMPLEX WIENER-ITO CHAOS DECOMPOSITION REVISITED

In this article, some properties of complex Wiener-It? multiple integrals and complex Ornstein-Uhlenbeck operators and semigroups are obtained. Those include Stroock’s formula, Hu-Meyer formula, Clark-Ocone formula, and the hypercontractivity of complex Ornstein-Uhlenbeck semigroups. As an application, several expansions of the fourth moments of complex Wiener-It? multiple integrals are given.

Polynomial Complexity Bounds of Mehrotra-type Predictor-corrector Algorithms for Linear Programming over Symmetric Cones

We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small 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 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 CAPACITY EXPANSION PROBLEM WITH BUDGET CONSTRAINT AND BOTTLENECK LIMITATION

This paper considers a capacity expansion problem with budget constraint. Suppose each edge in the network has two attributes: capacity and the degree of difficulty. The difficulty degree of a tree T is the maximum. degree of difficulty of all edges in the tree and the cost for coping with the difficulty in a tree is a nondecreasing function about the difficulty degree of the tree. The authors need to increase capacities of some edges so that there is a spanning tree whose capacity can be increased to the maximum extent, meanwhile the total cost for increasing capacity as well as overcoming the difficulty in the spanning tree does not exceed a given budget D*. Suppose the cost for increasing capacity on each edge is a linear function about the increment of capacity, they transform this problem into solving some hybrid parametric spanning tree problems([1]) and propose a strongly polynomial algorithm.

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

L^q Inequalities and Operator Preserving Inequalities

Let Pn be the class of polynomials of degree at most n. Rather and Shah [15] proved that if P∈Pn and P（z） 6=0 in｜z｜〈1, then for every R〉0 and 0≤q〈∞,｜B[P（Rz）]｜q≤｜RnB[zn]＋λ0｜q｜1＋zn｜q ｜P（z）｜q, where B is a Bn-operator. In this paper, we prove some generalization of this result which in particular yield-s some known polynomial inequalities as special. We also consider an operator Dαwhich maps a polynomial P（z） into DαP（z）：=nP（z）＋（α-z）P′（z） and obtain exten-sions and generalizations of a number of well-known Lq inequalities.

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.

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.

New Mehrotra's second order predictor-corrector algorithm for P_*(κ) linear complementarity problems

It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra＇s second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O（4κ ＋ 3）√14κ ＋ 5 nlog（x0）Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.

NOVEL DECODING OF SQUARE QAM MODULATED MIMO SYSTEMS BASED ON TURBO MULTIUSER DETECTION

By introducing the bit-level multi-stream coded Layered Space-Time （LST） transmitter along with a novel iterative MultiStage Decoding （MSD） at the receiver, the paper shows how to achieve the near-capacity performance of the Multiple-Input Multiple-Output （MIMO） systems with square Quadrature Amplitude Modulation （QAM）. In the proposed iterative MSD scheme, the detection at each stage is equivalent to multiuser detection of synchronous Code Division Multiple Access （CDMA） multiuser systems with the aid of the binary representation of the transmitted symbols. Therefore, the optimal Soft-Input Soft-Output （SISO） multiuser detection and low-complexity SISO multiuser detection can be utilized herein. And the proposed scheme with low-complexity SISO multiuser detection has polynomial complexity in the number of transmit antennas M, the number of receive antennas N, and the number of bits per constellation point Me. Simulation results demonstrate that the proposed scheme has similar Bit Error Rate （BER） performance to that of the known Iterative Tree Search （ITS） detection.

ON THE COMPLEXITY OF A PL HOMOTOPY ALGORITHM FOR ZEROS OF POLYNOMIALS

A PL homotopy algorithm is modified to yield a polynomial-time result on its computational complexity.We prove that the cost of locating all zeros of a polynomial of degree n to an accuracy of ε(measured by the number of evaluations of the polynomial)grows no faster than O(max{n^4,n^3log_2(n/ε)}).This work is in response to a question raised in a paper by S.Smale as to the efficiency of piecewise linear methods in solving equations.In comparison with a few results reported,the algorithm under discussion is the only one providing correct multiplicities and the only one employing vector labelling.

A Parallel Algorithm for Finding Roots of a Complex Polynomial

A distribution theory of the roots of a polynomial and a parallel algorithm for finding roots of a complex polynomial based on that theory are developed in this paper. With high parallelism, the algorithm is an im- provement over the Wilf algorithm.

The Complexity of Checking Consistency of Pedigree Information and Related Problems

Consistency checking is a fundamental computational problem in genetics.Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.

Generalized Isochronous Centers for Complex Systems

In this paper, the definition of generalized isochronous center is given in order to study unitedly real isochronous center and linearizability of polynomial differential systems. An algorithm to compute generalized period constants is obtained, which is a good method to find the necessary conditions of generalized isochronous center for any rational resonance ratio. Its two linear recursive formulas are symbolic and easy to realize with computer algebraic system. The function of time-angle difference is introduced to prove the sufficient conditions. As the application, a class of real cubic Kolmogorov system is investigated and the generalized isochronous center conditions of the origin are obtained.

ON DIFFERENTIAL STRUCTURES OF POLYNOMIAL SPACES IN CONTROL THEORY

A valuable number of works has been published about Hurwitz and Schur polynomials in order to known better their properties. For example it is known that the sets of Hurwitz and Schur polynomials are open and no convex sets. Besides, the set of monic Schur polynomials is contractible. Now we study this set using ideas from differential topology, and we prove that the space of Schur complex polynomials with positive leading coefficient, and the space of Hurwitz complex polynomials which leading coefficient having positive real part, have structure of trivial vector bundle, and each space of （Schur complex and real, Hurwitz complex） polynomials has a differential structure diffeomorphic to some known spaces.