A collocation method for the numerical solution of a two dimensional integral equation using a quadratic spline quasi-interpolant

In this paper, we propose an interesting method for approximating the solution of a two dimensional second kind equation with a smooth kernel using a bivariate quadratic spline quasi-interpolant (abbr. QI) defined on a uniform criss-cross triangulation of a bounded rectangle. We study the approximation errors of this method together with its Sloan’s iterated version and we illustrate the theoretical results by some numerical examples.     

A FPTAS for computing a symmetric Leontief competitive economy equilibrium

In this paper, we consider a linear complementarity problem (LCP) arisen from the Nash and Arrow–Debreu competitive economy equilibria where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for approximating a complementary solution, although the LCP solution set can be non-convex or non-connected. Our method is based on approximating a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with a new improved running time complexity ${{O}((\frac{n^4}{\epsilon})\log\log(\frac{1}{\epsilon}))}$ arithmetic operation in accuracy ${\epsilon \in (0,1)}$ . We also report preliminary computational results which show that the method is highly effective. Applications in competitive market model problems with other utility functions are also presented, including global trading and dynamic spectrum management problems.     

The finite criss-cross method for hyperbolic programming

In this paper the finite criss-cross method is generalized to solve hyperbolic (fractional linear) programming problems. Just as in the case of linear or quadratic programming the criss-cross method can be initialized with any, not necessarily feasible basic solution. It is known that if the feasible region of the problem is unbounded then some of the known algorithms fail to solve the problem. Our criss-cross algorithm does not have such drawback. Finiteness of the procedure is proved under the usual mild assumptions. Some small numerical examples illustrate the main features of the algorithm and show that our method generates different iterates than other earlier published methods.     

A Non-Interior Continuation Algorithm for the P0 or P* LCP with Strong Global and Local Convergence Properties

We propose a non-interior continuation algorithm for the solution of the linear complementarity problem (LCP) with a P₀ matrix. The proposed algorithm differentiates itself from the current continuation algorithms by combining good global convergence properties with good local convergence properties under unified conditions. Specifically, it is shown that the proposed algorithm is globally convergent under an assumption which may be satisfied even if the solution set of the LCP is unbounded. Moreover, the algorithm is globally linearly and locally superlinearly convergent under a nonsingularity assumption. If the matrix in the LCP is a P_* matrix, then the above results can be strengthened to include global linear and local quadratic convergence under a strict complementary condition without the nonsingularity assumption.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

A GENERALIZATION OF FINSLER'S THEOREM FOR QUADRATIC INEQUALITIES AND EQUALITIES

ABSTRACT

A generalization is given of Finsler's theorem on the positivity of a quadratic form subject to a quadratic equality. The generalized result is, under a certain assumption, a set of necessary and sufficient conditions for non-negativity of a quadratic form subject to an arbitrary number of quadratic inequality and equality constraints. Certain properties of matrix inverses are deduced using the conditions.     

An enumerative method for the solution of linear complementarity problems

In this paper an enumerative method for the solution of the Linear Complementarity Problem (LCP) is presented. This algorithm either finds all the solutions of any general LCP (that is, no assumption is made concerning the class of the matrix), or it establishes that no such solution exists. The method is extended to the Second Linear Complementarity Problem (SLCP), A new problem which has been introduced for the solution of a general quadratic program.     

On solving Linear Complementarity Problems by DC programming and DCA

In this paper, we consider four optimization models for solving the Linear Complementarity (LCP) Problems. They are all formulated as DC (Difference of Convex functions) programs for which the unified DC programming and DCA (DC Algorithms) are applied. The resulting DCA are simple: they consist of solving either successive linear programs, or successive convex quadratic programs, or simply the projection of points on \mathbbR₊²ⁿ\mathbb{R}_{+}^{2n}. Numerical experiments on several test problems illustrate the efficiency of the proposed approaches in terms of the quality of the obtained solutions, the speed of convergence, and so on. Moreover, the comparative results with Lemke algorithm, a well known method for the LCP, show that DCA outperforms the Lemke method.     

Abel’s integral operator: sparse representation based on multiwavelets

In this work, Abel’s integral operator is represented based on Alpert’s multiwavelets as a sparse matrix and then a non-linear Abel’s integral equation of the second kind is solved by multiwavelets Galerkin method. Nonlinearity and singularity make the numerical procedure more challenging. But the proposed scheme overcomes these problems. Convergence analysis is investigated and some numerical examples validated this analysis.

     

Bounds for the solution set of linear complementarity problems

We give here bounds for the feasible domain and the solution norm of Linear Complementarity Problems (LCP). These bounds are motivated by formulating the LCP as a global quadratic optimization problem and are characterized by the eigenstructure of the corresponding matrix. We prove boundedness of the feasible domain when the quadratic problem is concave, and give easily computable bounds for the solution norm for the convex case. We also obtain lower and upper bounds for the solution norm of the general nonconvex problem.     

A class of polynomially solvable linear complementarity problems

Although the general linear complementarity problem (LCP) is NP-complete, there are special classes that can be solved in polynomial time. One example is the type where the defining matrix is nondegenerate and for which the n-step property holds. In this paper we consider an extension of the property to the degenerate case by introducing the concept of an extended n-step vector and matrix. It is shown that the LCP defined by such a matrix is polynomially solvable as well.     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

一类变形的牛顿法求解矩阵平方根

提出一些改进的方法来计算矩阵A的平方根,也就是应用一些牛顿法的变形来解决二次矩阵方程．研究表明,改进的方法比牛顿算法和一些已有的牛顿算法的变形效果要好．通过迭代方法,举出一些数值例子说明改进的方法的性能．     

Numerical integration based on bivariate quadratic spline quasi-interpolants on bounded domains

In this paper we generate and study new cubature formulas based on spline quasi-interpolants defined as linear combinations of C ¹ bivariate quadratic B-splines on a rectangular domain Ω, endowed with a non-uniform criss-cross triangulation, with discrete linear functionals as coefficients. Such B-splines have their supports contained in Ω and there is no data point outside this domain. Numerical results illustrate the methods.     

Error bounds on the approximation of functions and partial derivatives by quadratic spline quasi-interpolants on non-uniform criss-cross triangulations of a rectangular domain

Given a non-uniform criss-cross triangulation of a rectangular domain Ω, we consider the approximation of a function f and its partial derivatives, by general C ¹ quadratic spline quasi-interpolants and their derivatives. We give error bounds in terms of the smoothness of f and the characteristics of the triangulation. Then, the preceding theoretical results are compared with similar results in the literature. Finally, several examples are proposed for illustrating various applications of the quasi-interpolants studied in the paper.     

Comparison of Two Methods for Superreplication

Abstract

We compare two methods for superreplication of options with convex pay-off functions. One method entails the overestimation of an unknown covariance matrix in the sense of quadratic forms. With this method the value of the superreplicating portfolio is given as the solution of a linear Black–Scholes BS-type equation. In the second method, the choice of quadratic form is made pointwise. This leads to a fully non-linear equation, the so-called Black–Scholes–Barenblatt (BSB) equation, for the value of the superreplicating portfolio. In general, this value is smaller for the second method than for the first method. We derive estimates for the difference between the initial values of the superreplicating strategies obtained using the two methods.     

Equivalent conditions for noncentral generalized Laplacianness and independence of matrix quadratic forms

Let Y be an n×p multivariate normal random matrix with general covariance Σ_Y and W be a symmetric matrix. In the present article, the property that a matrix quadratic form Y^′WY is distributed as a difference of two independent (noncentral) Wishart random matrices is called the (noncentral) generalized Laplacianness (GL). Then a set of algebraic results are obtained which will give the necessary and sufficient conditions for the (noncentral) GL of a matrix quadratic form. Further, two extensions of Cochran’s theorem concerning the (noncentral) GL and independence of a family of matrix quadratic forms are developed.     

On iterative methods for the quadratic matrix equation with M-matrix

In this paper, we consider Newton’s method and Bernoulli’s method for a quadratic matrix equation arising from an overdamped vibrating system. By introducing M-matrix to this equation, we provide a sufficient condition for the existence of the primary solution. Moreover, we show that Newton’s method and Bernoulli’s method with an initial zero matrix converge to the primary solvent under the proposed sufficient condition.     

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.