On the convergence of row-modification algorithm for matrix projections

This paper proposes an algorithm for matrix minimum-distance projection, with respect to a metric induced from an inner product that is the sum of inner products of column vectors, onto the collection of all matrices with their rows restricted in closed convex sets. This algorithm produces a sequence of matrices by modifying a matrix row by row, over and over again. It is shown that the sequence is convergent, and it converges to the desired projection. The implementation of the algorithm for multivariate isotonic regressions and numerical examples are also presented in the paper.     

Numerical methods for solving some matrix feasibility problems

In this paper, we design two numerical methods for solving some matrix feasibility problems, which arise in the quantum information science. By making use of the structured properties of linear constraints and the minimization theorem of symmetric matrix on manifold, the projection formulas of a matrix onto the feasible sets are given, and then the relaxed alternating projection algorithm and alternating projection algorithm on manifolds are designed to solve these problems. Numerical examples show that the new methods are feasible and effective.     

Accelerated reflection projection algorithm and its application to the LMI problem

We discuss accelerated version of the alternating projection method which can be applied to solve the linear matrix inequality (LMI) problem. The alternating projection method is a well-known algorithm for the convex feasibility problem, and has many generalizations and extensions. Bauschke and Kruk proposed a reflection projection algorithm for computing a point in the intersection of an obtuse cone and a closed convex set. We carry on this research in two directions. First, we present an accelerated version of the reflection projection algorithm, and prove its weak convergence in a Hilbert space; second, we prove the finite termination of an algorithm which is based on the proposed algorithm and provide an explicit upper bound for the required number of iterations under certain assumptions. Numerical experiments for the LMI problem are provided to demonstrate the effectiveness and merits of the proposed algorithms.     

A variable-metric variant of the Karmarkar algorithm for linear programming

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company.     

Geometrically convergent projection method in matrix games

We propose a method which evaluates the solution of a matrix game. We reduce the problem of the search for the solution to a convex feasibility problem for which we present a method of projection onto an acute cone. The algorithm converges geometrically. At each iteration, we apply a combinatorial algorithm in order to evaluate the projection onto the standard simplex.     

Degradation modeling with subpopulation heterogeneities based on the inverse Gaussian process

This study proposes a random effects model based on inverse Gaussian process, where the mixture normal distribution is used to account for both unit-specific and subpopulation-specific heterogeneities. The proposed model can capture heterogeneities due to subpopulations in the same population or the units from different batches. A new Expectation-Maximization (EM) algorithm is developed for point estimation and the bias-corrected bootstrap is used for interval estimation. We show that the EM algorithm updates the parameters based on the gradient of the loglikelihood function via a projection matrix. In addition, the convergence rate depends on the condition number that can be obtained by the projection matrix and the Hessian matrix of the loglikelihood function. A simulation study is conducted to assess the proposed model and the inference methods, and two real degradation datasets are analyzed for illustration.     

互补约束数学规划问题的一个广义梯度投影罚算法

结合罚函数思想和广义梯度投影技术,提出求解非线性互补约束数学规划问题的一个广义梯度投影罚算法.首先,通过扰动技术和广义互补函数,将原问题转化为序列带参数的近似的标准非线性规划;其次,利用广义梯度投影矩阵构造搜索方向的显式表达式.一个特殊的罚函数作为效益函数,而且搜索方向能保证效益函数的下降性.在适当的假设条件下算法具有全局收敛性.     

A globally convergent non-interior point algorithm with full Newton step for second-order cone programming

A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of A to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.     

用正交投影迭代法求矩阵方程AXA~H=B的Hermite解

本文讨论了矩阵方程AXAH=B的Hermite解及其最佳逼近的正交投影迭代法,证明了算法的收敛性,得到收敛速率的估计式.通过数值试验也检验了算法的有效性.     

Ellipsoid projection method in matrix games

A problem of calculating a solution of a zero-sum matrix game is considered in the paper The problem of search of a solution is reduced to a constrained convex minimization problem for which an ellipsoid projection algorithm is used. The algorithm generates an ?-optimal solution of the game in a polynomial time     

凸约束非光滑方程组一个新的谱梯度投影算法

基于寻找分离超平面的三种经典线搜索技术,本文提出了一种自适应线搜索技术.结合谱梯度投影法,提出了凸约束非光滑单调方程组的一个谱梯度投影算法.该算法不需要计算和存储任何矩阵,因而适合求解大规模非光滑的非线性单调方程组.在较弱的条件下,证明了方法的全局收敛性,并分析了算法的收敛率.数值试验结果表明算法是有效的和鲁棒的.     

On the application of alternating projection under the constraint of linear matrix inequalities

In this paper, alternating projection under the constraint oflinear matrix inequalities (LMIs) is investigated to solve thefollowing two problems: finding the intersection of severalconvex LMI sets and designing an output-feedback stabilizingcontroller. Each problem is formulated as a quadratic optimizationproblem under LMI constraints. A numerical algorithm based onthe concept of alternating projection is proposed. The algorithmis demonstrated using a vertical-strip pole-assignment example.     

Spectral behaviour of GMRES applied to singular systems

The purpose of this paper is to develop a spectral analysis of the Hessenberg matrix obtained by the GMRES algorithm used for solving a linear system with a singular matrix. We prove that the singularity of the Hessenberg matrix depends on the nature of A and some other criteria such as the zero eigenvalue multiplicity and the projection of the initial residual on particular subspaces. We also show some new results about the distinct kinds of breakdown which may occur in the algorithm when the system is singular.      

Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming

A classical method for solving the variational inequality problem is the projection algorithm. We show that existing convergence results for this algorithm follow from one given by Gabay for a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Moreover, we extend the projection algorithm to solveany monotone affine variational inequality problem. When applied to linear complementarity problems, we obtain a matrix splitting algorithm that is simple and, for linear/quadratic programs, massively parallelizable. Unlike existing matrix splitting algorithms, this algorithm converges under no additional assumption on the problem. When applied to generalized linear/quadratic programs, we obtain a decomposition method that, unlike existing decomposition methods, can simultaneously dualize the linear constraints and diagonalize the cost function. This method gives rise to highly parallelizable algorithms for solving a problem of deterministic control in discrete time and for computing the orthogonal projection onto the intersection of convex sets.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation under grant NSF-ECS-8519058.Thanks are due to Professor J.-S. Pang for his helpful comments.     

Analysis on Newton projection method for the split feasibility problem

In this paper, based on a merit function of the split feasibility problem (SFP), we present a Newton projection method for solving it and analyze the convergence properties of the method. The merit function is differentiable and convex. But its gradient is a linear composite function of the projection operator, so it is nonsmooth in general. We prove that the sequence of iterates converges globally to a solution of the SFP as long as the regularization parameter matrix in the algorithm is chosen properly. Especially, under some local assumptions which are necessary for the case where the projection operator is nonsmooth, we prove that the sequence of iterates generated by the algorithm superlinearly converges to a regular solution of the SFP. Finally, some numerical results are presented.     

求解结构矩阵低秩逼近的交替投影方法

结构矩阵低秩逼近在图像压缩、计算机代数和语音编码中有广泛应用.首先给出了几类结构矩阵的投影公式,再利用交替投影方法计算结构矩阵低秩逼近问题.数值试验表明新方法是可行的.     

Deriving Karmarkar’s LP algorithm using angular projection matrix

Understanding Karmarkar’s algorithm is both desirable and necessary for its efficient implementation, for further improvement and for carrying out complexity analysis. In this report an algorithm based on the concept of angular projection matrix, to solve linear programming problems is derived. Surprisingly, this algorithm coincides with the affine version of Karmarkar’s algorithm.     

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.     

Minimizing Quadratic Functions Subject to Bound Constraints with the Rate of Convergence and Finite Termination

A new active set based algorithm is proposed that uses the conjugate gradient method to explore the face of the feasible region defined by the current iterate and the reduced gradient projection with the fixed steplength to expand the active set. The precision of approximate solutions of the auxiliary unconstrained problems is controlled by the norm of violation of the Karush-Kuhn-Tucker conditions at active constraints and the scalar product of the reduced gradient with the reduced gradient projection. The modifications were exploited to find the rate of convergence in terms of the spectral condition number of the Hessian matrix, to prove its finite termination property even for problems whose solution does not satisfy the strict complementarity condition, and to avoid any backtracking at the cost of evaluation of an upper bound for the spectral radius of the Hessian matrix. The performance of the algorithm is illustrated on solution of the inner obstacle problems. The result is an important ingredient in development of scalable algorithms for numerical solution of elliptic variational inequalities.     

The variable projection algorithm in time-resolved spectroscopy,microscopy and mass spectrometry applications

Nonlinear least squares optimization problems in which the parameters can be partitioned into two sets such that optimal estimates of parameters in one set are easy to solve for given fixed values of the parameters in the other set are common in practice. Particularly ubiquitous are data fitting problems in which the model function is a linear combination of nonlinear functions, which may be addressed with the variable projection algorithm due to Golub and Pereyra. In this paper we review variable projection, with special emphasis on its application to matrix data. The generalization of the algorithm to separable problems in which the linear coefficients of the nonlinear functions are subject to constraints is also discussed. Variable projection has been instrumental for model-based data analysis in multi-way spectroscopy, time-resolved microscopy and gas or liquid chromatography mass spectrometry, and we give an overview of applications in these domains, illustrated by brief case studies.