A polynomial path-following interior point algorithm for general linear complementarity problems

Linear Complementarity Problems (LCPs) belong to the class of \mathbbNP{\mathbb{NP}} -complete problems. Therefore we cannot expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Our aim is to construct interior point algorithms which, according to the duality theorem in EP (Existentially Polynomial-time) form, in polynomial time either give a solution of the original problem or detects the lack of property P_*([(k)\tilde]){\mathcal{P}_*(\tilde\kappa)} , with arbitrary large, but apriori fixed [(k)\tilde]{\tilde\kappa}). In the latter case, the algorithms give a polynomial size certificate depending on parameter [(k)\tilde]{\tilde{\kappa}} , the initial interior point and the input size of the LCP). We give the general idea of an EP-modification of interior point algorithms and adapt this modification to long-step path-following interior point algorithms.     

Compound matrices: properties,numerical issues and analytical computations

This paper studies the possibility to calculate efficiently compounds of real matrices which have a special form or structure. The usefulness of such an effort lies in the fact that the computation of compound matrices, which is generally noneffective due to its high complexity, is encountered in several applications. A new approach for computing the Singular Value Decompositions (SVD’s) of the compounds of a matrix is proposed by establishing the equality (up to a permutation) between the compounds of the SVD of a matrix and the SVD’s of the compounds of the matrix. The superiority of the new idea over the standard method is demonstrated. Similar approaches with some limitations can be adopted for other matrix factorizations, too. Furthermore, formulas for the n − 1 compounds of Hadamard matrices are derived, which dodge the strenuous computations of the respective numerous large determinants. Finally, a combinatorial counting technique for finding the compounds of diagonal matrices is illustrated.      

An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity

Infeasible interior point methods have been very popular and effective. In this paper, we propose a predictor–corrector infeasible interior point algorithm for convex quadratic programming, and we prove its convergence and analyze its complexity. The algorithm has the polynomial numerical complexity with O(nL)-iteration.     

To Solving Multiparameter Problems of Algebra. 4. The AB-Algorithm and its Applications

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 127–143.     

To solving problems of algebra for two-parameter matrices. III

The paper continues the series of papers devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices of general form. It considers linearization methods, which allow one to reduce the problem of solving an equation F(λ, μ)x = 0 with a polynomial two-parameter matrix F(λ, μ) to solving an equation of the form D(λ, μ)y = 0, where D(λ, μ) = A(μ)-λB(μ) is a pencil of polynomial matrices. Consistent pencils and their application to solving spectral problems for the matrix F(λ, μ) are discussed. The notion of reducing subspace is generalized to the case of a pencil of polynomial matrices. An algorithm for transforming a general pencil of polynomial matrices to a quasitriangular pencil is suggested. For a pencil with multiple eigenvalues, algorithms for computing the Jordan chains of vectors are developed. Bibliography: 8 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 166–207.     

一个求解水平线性互补问题的高阶可行内点算法的多项式复杂性

最近,Zhao和Sun提出了一个求解sufficient线性互补问题的高阶不可行内点算法.不需要严格互补解条件,他们的算法获得了高阶局部收敛率,但他们的文章没有报告多项式复杂性结果.本文我们考虑他们所给算法的一个简化版本,即考虑求解单调水平线性互补问题的一个高阶可行内点算法.我们证明了算法的迭代复杂性是     

Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices

We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.     

An acceleration method for Ten Berge et al.’s algorithm for orthogonal INDSCAL

INDSCAL (INdividual Differences SCALing) is a useful technique for investigating both common and unique aspects of K similarity data matrices. The model postulates a common stimulus configuration in a low-dimensional Euclidean space, while representing differences among the K data matrices by differential weighting of dimensions by different data sources. Since Carroll and Chang proposed their algorithm for INDSCAL, several issues have been raised: non-symmetric solutions, negative saliency weights, and the degeneracy problem. Orthogonal INDSCAL (O-INDSCAL) which imposes orthogonality constraints on the matrix of stimulus configuration has been proposed to overcome some of these difficulties. Two algorithms have been proposed for O-INDSCAL, one by Ten Berge, Knol, and Kiers, and the other by Trendafilov. In this paper, an acceleration technique called minimal polynomial extrapolation is incorporated in Ten Berge et al.’s algorithm. Simulation studies are conducted to compare the performance of the three algorithms (Ten Berge et al.’s original algorithm, the accelerated algorithm, and Trendafilov’s). Possible extensions of the accelerated algorithm to similar situations are also suggested.     

Pivoting in Linear Complementarity: Two Polynomial-Time Cases

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty’s least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris’s highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Computing the Invariant Polynomials of a Polynomial Matrix. II

The paper considers the problem of computing the invariant polynomials of a general (regular or singular) one-parameter polynomial matrix. Two new direct methods for computing invariant polynomials, based on the W and V rank-factorization methods, are suggested. Each of the methods may be regarded as a method for successively exhausting roots of invariant polynomials from the matrix spectrum. Application of the methods to computing adjoint matrices for regular polynomial matrices, to finding the canonical decomposition into a product of regular matrices such that the characteristic polynomial of each of them coincides with the corresponding invariant polynomial, and to computing matrix eigenvectors associated with roots of its invariant polynomials are considered. Bibliography: 5 titles.     

Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Sets

This paper considers the following problem, which we call the largest common point set problem (LCP): given two point sets P and Q in the Euclidean plane, find a subset of P with the maximum cardinality that is congruent to some subset of Q . We introduce a combinatorial-geometric quantity λ(P, Q) , which we call the inner product of the distance-multiplicity vectors of P and Q , show its relevance to the complexity of various algorithms for LCP, and give a nontrivial upper bound on λ(P, Q) . We generalize this notion to higher dimensions, give some upper bounds on the quantity, and apply them to algorithms for LCP in higher dimensions. Along the way, we prove a new upper bound on the number of congruent triangles in a point set in four-dimensional space. Received July 17, 1997, and in revised form March 6, 1998.     

A note on regularity and positive definiteness of interval matrices

We present a sufficient regularity condition for interval matrices which generalizes two previously known ones. It is formulated in terms of positive definiteness of a certain point matrix, and can also be used for checking positive definiteness of interval matrices. Comparing it with Beeck’s strong regularity condition, we show by counterexamples that none of the two conditions is more general than the other one.     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

To Solving Multiparameter Problems of Algebra. 5. The ∇V-q Factorization Algorithm and its Applications

The algorithm of ∇V-factorization, suggested earlier for decomposing one- and two-parameter polynomial matrices of full row rank into a product of two matrices (a regular one, whose spectrum coincides with the finite regular spectrum of the original matrix, and a matrix of full row rank, whose singular spectrum coincides with the singular spectrum of the original matrix, whereas the regular spectrum is empty), is extended to the case of q-parameter (q ≥ 1) polynomial matrices. The algorithm of ∇V-q factorization is described, and its justification and properties for matrices with arbitrary number of parameters are presented. Applications of the algorithm to computing irreducible factorizations of q-parameter matrices, to determining a free basis of the null-space of polynomial solutions of a matrix, and to finding matrix divisors corresponding to divisors of its characteristic polynomial are considered. Bibliogrhaphy: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 144–153.     

Some Applications of a Bombieri-Type Theoremin Totally Real Number Fields

 The primary concern of this paper is to present three further applications of a multi-dimensional version of Bombieri’s theorem on primes in arithmetic progressions in the setting of a totally real algebraic number field K. First, we deal with the order of magnitude of a greatest (relative to its norm) prime ideal factor of , where the product runs over prime arguments ω of a given irreducible polynomial F which lie in a certain lattice point region. Then, we turn our attention to the problem about the occurrence of algebraic primes in a polynomial sequence generated by an irreducible polynomial of K with prime arguments. Finally, we give further contributions to the binary Goldbach problem in K.     

Polynomial time solvability of non-symmetric semidefinite programming

In this paper, we consider semidefinite programming with non-symmetric matrices, which is called non-symmetric semidefinite programming (NSDP). We convert such a problem into a linear program over symmetric cones, which is polynomial time solvable by interior point methods. Thus, the NSDP problem can be solved in polynomial time. Such a result corrects the corresponding result given in the literature. Similar methods can be applied to nonlinear programming with non-symmetric matrices.     

Polynomial interpolation of operators in Hilbert spaces

An operator polynomial is constructed as the limit of a smoothing polynomial as λ → ∞. Using its interpolation properties, necessary and sufficient conditions for the existence of a solution of the polynomial interpolation problem are found. The set of all interpolating polynomials in a Hilbert space is described. Bibliography:4 titles. Translated fromObchyslyuval’na ta Prykladna Matematyka, No. 77, 1993, pp. 44–54.     

The resultant approach to computing vector characteristics of multiparameter polynomial matrices

Known types of resultant matrices corresponding to one-parameter matrix polynomials are generalized to the multiparameter case. Based on the resultant approach suggested, methods for solving the following problems for multiparameter polynomial matrices are developed: computing a basis of the matrix range, computing a minimal basis of the right null-space, and constructing the Jordan chains and semilattices of vectors associated with a multiple spectrum point. In solving these problems, the original polynomial matrix is not transformed. Methods for solving other parametric problems of algebra can be developed on the basis of the method for computing a minimal basis of the null-space of a polynomial matrix. Issues concerning the optimality of computing the null-spaces of sparse resultant matrices and numerical precision are not considered. Bibliography: 19 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 182–214.