Group decision making methods based on intuitionistic fuzzy soft matrices

Soft set theory was originally proposed by Molodtsov as a general mathematical tool for dealing with uncertainty in 1999. Recently, researches of decision making based on soft sets have got some progress, but few people consider multi-experts situation. As such, this paper discusses multi-experts group decision making problems. Firstly, we give a concept of intuitionistic fuzzy soft matrix (IFSM) and prove some relevant properties of IFSM. Then, an adjustable approach is presented by means of median level soft set and p-quantile level soft set for dealing with decision making problems based on IFSM. Thirdly, we study aggregation methods of IFSM, give two kinds of aggregation operators and methods that how to determine experts’ weights under different situation with programming models, four corresponding algorithms have been proposed, too. Finally, a practical example has been demonstrated the reasonability and efficiency of these new algorithms.     

About the generalized LM-inverse and the weighted Moore-Penrose inverse

The recursive method for computing the generalized LM-inverse of a constant rectangular matrix augmented by a column vector is proposed in Udwadia and Phohomsiri (2007) [16] and [17]. The corresponding algorithm for the sequential determination of the generalized LM-inverse is established in the present paper. We prove that the introduced algorithm for computing the generalized LM-inverse and the algorithm for the computation of the weighted Moore-Penrose inverse developed by Wang and Chen (1986) in [23] are equivalent algorithms. Both of the algorithms are implemented in the present paper using the package MATHEMATICA. Several rational test matrices and randomly generated constant matrices are tested and the CPU time is compared and discussed.     

A Newton-based method for the calculation of the distance to instability

In this paper, a new fast algorithm for the computation of the distance of a stable matrix to the unstable matrices is provided. The method uses Newton’s method to find a two-dimensional Jordan block corresponding to a pure imaginary eigenvalue in a certain two-parameter Hamiltonian eigenvalue problem introduced by Byers [R. Byers, A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. Sci. Statist. Comput. 9 (1988) 875-881]. This local method is augmented by a test step, previously used by other authors, to produce a global method. Numerical results are presented for several examples and comparison is made with the methods of Boyd and Balakrishnan [S. Boyd, V. Balakrishnan, A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its L_∞-norm, Systems Control Lett. 15 (1990) 1-7] and He and Watson [C. He, G.A. Watson, An algorithm for computing the distance to instability, SIAM J. Matrix Anal. Appl. 20 (1999) 101-116].     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning

We consider interstage dependent stochastic linear programs where both the random right-hand side and the model of the underlying stochastic process have a special structure. Namely, for equality constraints (resp. inequality constraints) the right-hand side is an affine function (resp. a given function b _t ) of the process value for the current time step t. As for m-th component of the process at time step t, it depends on previous values of the process through a function h _tm . For this type of problem, to obtain an approximate policy under some assumptions for functions b _t and h _tm , we detail a stochastic dual dynamic programming algorithm. Our analysis includes some enhancements of this algorithm such as the definition of a state vector of minimal size, the computation of feasibility cuts without the assumption of relatively complete recourse, as well as efficient formulas for sharing optimality and feasibility cuts between nodes of the same stage. The algorithm is given for both a non-risk-averse and a risk-averse model. We finally provide preliminary results comparing the performances of the recourse functions corresponding to these two models for a real-life application.     

An alternate implementation of Goldfarb's minimization algorithm

Goldfarb's algorithm, which is one of the most successful methods for minimizing a function of several variables subject to linear constraints, uses a single matrix to keep second derivative information and to ensure that search directions satisfy any active constraints. In the original version of the algorithm this matrix is full, but by making a change of variables so that the active constraints become bounds on vector components, this matrix is transformed so that the dimension of its non-zero part is only the number of variablesless the number of active constraints. It is shown how this transformation may be used to give a version of the algorithm that usually provides a good saving in the amount of computation over the original version. Also it allows the use of sparse matrix techniques to take advantage of zeros in the matrix of linear constraints. Thus the method described can be regarded as an extension of linear programming to allow a non-linear objective function.     

Differentiation of generalized inverses for rational and polynomial matrices

Our basic motivation is a direct method for computing the gradient of the pseudo-inverse of well-conditioned system with respect to a scalar, proposed in [13] by Layton. In the present paper we combine the Layton’s method together with the representation of the Moore-Penrose inverse of one-variable polynomial matrix from [24] and developed an algorithm for computing the gradient of the Moore-Penrose inverse for one-variable polynomial matrix. Moreover, using the representation of various types of pseudo-inverses from [26], based on the Grevile’s partitioning method, we derive more general algorithms for computing {1}, {1, 3} and {1, 4} inverses of one-variable rational and polynomial matrices. Introduced algorithms are implemented in the programming language MATHEMATICA. Illustrative examples on analytical matrices are presented.     

Linear programming system identification

We define a version of the Inverse Linear Programming problem that we call Linear Programming System Identification. This version of the problem seeks to identify both the objective function coefficient vector and the constraint matrix of a linear programming problem that best fits a set of observed vector pairs. One vector is that of actual decisions that we call outputs. These are regarded as approximations of optimal decision vectors. The other vector consists of the inputs or resources actually used to produce the corresponding outputs. We propose an algorithm for approximating the maximum likelihood solution. The major limitation of the method is the computation of exact volumes of convex polytopes. A numerical illustration is given for simulated data.     

Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices

This report may be considered as a non-trivial extension of an unpublished report by William Kahan (Accurate Eigenvalues of a symmetric tri-diagonal matrix, Technical Report CS 41, Computer Science Department, Stanford University, 1966). His interplay between matrix theory and computer arithmetic led to the development of algorithms for computing accurate eigenvalues and singular values. His report is generally considered as the precursor for the development of IEEE standard 754 for binary arithmetic. This standard has been universally adopted by virtually all PC, workstation and midrange hardware manufactures and tens of billions of such machines have been produced. Now we use the features in this standard to improve the original algorithm.In this paper, we describe an algorithm in floating-point arithmetic to compute the exact inertia of a real symmetric (shifted) tridiagonal matrix. The inertia, denoted by the integer triplet (π, ν, ζ), is defined as the number of positive, negative and zero eigenvalues of a real symmetric (or complex Hermitian) matrix and the adjective exact refers to the eigenvalues computed in exact arithmetic. This requires the floating-point computation of the diagonal matrix D of the LDL^t factorization of the shifted tridiagonal matrix T − τI with +∞ and −∞ rounding modes defined in IEEE 754 standard. We are not aware of any other algorithm which gives the exact answer to a numerical problem when implemented in floating-point arithmetic in standard working precisions. The guaranteed intervals for eigenvalues are obtained by bisection or multisection with this exact inertia information. Similarly, using the Golub-Kahan form, guaranteed intervals for singular values of bidiagonal matrices can be computed. The diameter of the eigenvalue (singular value) intervals depends on the number of shifts with inconsistent inertia in two rounding modes. Our algorithm not only guarantees the accuracy of the solutions but is also consistent across different IEEE 754 standard compliant architectures. The unprecedented accuracy provided by our algorithms could be also used to debug and validate standard floating-point algorithms for computation of eigenvalues (singular values). Accurate eigenvalues (singular values) are also required by certain algorithms to compute accurate eigenvectors (singular vectors).We demonstrate the accuracy of our algorithms by using standard matrix examples. For the Wilkinson matrix, the eigenvalues (in IEEE double precision) are very accurate with an (open) interval diameter of 6 ulps (units of the last place held of the mantissa) for one of the eigenvalues and lesser (down to 2 ulps) for others. These results are consistent across many architectures including Intel, AMD, SGI and DEC Alpha. However, by enabling IEEE double extended precision arithmetic in Intel/AMD 32-bit architectures at no extra computational cost, the (open) interval diameters were reduced to one ulp, which is the best possible solution for this problem. We have also computed the eigenvalues of a tridiagonal matrix which manifests in Gauss-Laguerre quadrature and the results are extremely good in double extended precision but less so in double precision. To demonstrate the accuracy of computed singular values, we have also computed the eigenvalues of the Kac₃₀ matrix, which is the Golub-Kahan form of a bidiagonal matrix. The tridiagonal matrix has known integer eigenvalues. The bidiagonal Cholesky factor of the Gauss-Laguerre tridiagonal is also included in the singular value study.     

Efficiency of weak greedy algorithms for m-term approximations

We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm(WTGA) and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,1p∞,we show that the WTGA realizes the order of the best m-term approximation.Finally,we compare the efficiency of the weak Chebyshev greedy algorithm(WCGA) with the thresholding greedy algorithm(TGA) when applying them to quasi-greedy bases in L_p,1≤p∞,by establishing the corresponding Lebesgue-type inequalities.It seems that when p2 the WCGA is better than the TGA.     

Convex hull properties and algorithms

Convex hull (CH) is widely used in computer graphic, image processing, CAD/CAM, and pattern recognition. We investigate CH properties and derive new properties: (1) CH vertices’ coordinates monotonically increase or decrease, (2) The edge slopes monotonically decrease. Using these properties, we proposed two algorithms, i.e., CH algorithm for planar point set, and CH algorithm for two available CHs. The main ideas of the proposed algorithms are as follows. A planar point set is divided into several subsets by the extreme points, and vertices in these subsets are then separately calculated. During the computation, the CH properties are used to eliminate concave points. This can reduce the computational cost and then improves the speed. Our first algorithm can extract CH with O(nlogn) time, which is the lower bound of planar CH extraction, and the second algorithm can obtain CH with O(m+n) time at the worst case.     

Structured FISTA for image restoration

In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.     

Linear programming system identification: The general nonnegative parameters case

By linear programming system identification, we mean the problem of estimating the objective function coefficient vector π and the technological coefficient matrix A for a linear programming system that best explains a set of input–output vectors. Input vectors are regarded as available resources. Output vectors are compared to imputed optimal ones by a decisional efficiency measure and a likelihood function is constructed. In an earlier paper, we obtained results for a simplified version of the problem. In this paper, we propose a genetic algorithm approach for the general case in which π and A are of arbitrary finite dimensions and have nonnegative components. A method based on Householder transformations and Monte Carlo integration is used as an alternative to combinatorial algorithms for the extreme points and volumes of certain required convex polyhedral sets. The method exhibits excellent face validity for a published test data set in data envelopment analysis.     

Quadratic programming with M-Matrices

In this paper, we study the problem of quadratic programming with M-matrices. We describe (1) an effective algorithm for the case where the variables are subject to a lower-bound constraint, and (2) an analogous algorithm for the case where the variables are subject to lower-and-upper-bound constraints. We demonstrate the special monotone behavior of the iterate and gradient vectors. The result on the gradient vector is new. It leads us to consider a simple updating procedure which preserves the monotonicity of both vectors. The procedures uses the fact that an M-matrix has a nonnegative inverse. Two new algorithms are then constructed by incorporating this updating procedure into the two given algorithms. We give numerical examples which show that the new methods can be more efficient than the original ones.     

Computing the matrix sign and absolute value functions

We present two algorithms for the computation of the matrix sign and absolute value functions. Both algorithms avoid a complete diagonalisation of the matrix, but they however require some informations regarding the eigenvalues location. The first algorithm consists in a sequence of polynomial iterations based on appropriate estimates of the eigenvalues, and converging to the matrix sign if all the eigenvalues are real. Convergence is obtained within a finite number of steps when the eigenvalues are exactly known. Nevertheless, we present a second approach for the computation of the matrix sign and absolute value functions, when the eigenvalues are exactly known. This approach is based on the resolution of an interpolation problem, can handle the case of complex eigenvalues and appears to be faster than the iterative approach. To cite this article: M. Ndjinga, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

A perturbation analysis of the intrinsic conditioning of an approximate null vector computed with a SVD

Let A be an m ×n real matrix with singular values σ₁ ? ··· ? σ_n?1 ? σ_n ? 0. In cases where σ_n ? 0, the corresponding right singular vector υ_n is a natural choice to use for an approximate null vector ofA. Using an elementary perturbation analysis, we show that κ = σ₁/(σ_n?1 ? σ_n) provides a quantitative measure of the intrinsic conditioning of the computation of υ_n from A.     

Computing powers of arbitrary Hessenberg matrices

An efficient algorithm for the computation of powers of an n × n arbitrary lower Hessenberg matrix is presented. Numerical examples are used to show the computational details. A comparison of the algorithm with two other methods of matrix multiplication proposed by Brent and by Winograd is included. Related algorithms were proposed earlier by Datta and Datta for lower Hessenberg matrices with unit super-diagonal elements, and by Barnett for the companion matrix.     

Convergence analysis and performance of the extended artificial physics optimization algorithm

This paper presents extended artificial physics optimization (EAPO), a population-based, stochastic, evolutionary algorithm (EA) for multidimensional search and optimization. EAPO extends the physicomimetics-based Artificial Physics Optimization (APO) algorithm by including each individual’s best fitness history. Including the history improves EAPO’s search capability compared to APO. EAPO and APO invoke a gravitational metaphor in which the force of gravity may be attractive or repulsive, the aggregate effect of which is to move individuals toward local and global optima. A proof of convergence is presented that reveals the conditions under which EAPO is guaranteed to converge. Discrete-time linear system theory is used to develop a second-order difference equation for an individual’s stochastic position vector as a function of time step. Stable solutions require eigenvalues inside the unit circle, leading to explicit convergence criteria relating the run parameters {m_i, w, G}. EAPO is tested against several benchmark functions with excellent results. The algorithm converges more quickly than APO and with better diversity.     

The relaxed inexact projection methods for the split feasibility problem

In this paper we present several relaxed inexact projection methods for the split feasibility problem (SFP). Each iteration of the first proposed algorithm consists of a projection onto a halfspace containing the given closed convex set. The algorithm can be implemented easily and its global convergence to the solution can be established under suitable conditions. Moreover,we present some modifications of the relaxed inexact projection method with constant stepsize by adopting Armijo-like search. We furthermore present a variable-step relaxed inexact projection method which does not require the computation of the matrix inverses and the largest eigenvalue of the matrix A^TA, and the objective function can decrease sufficiently at each iteration. We show convergence of these modified algorithms under mild conditions. Finally, we perform some numerical experiments, which show the behavior of the algorithms proposed.