共查询到18条相似文献,搜索用时 171 毫秒
1.
针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效. 相似文献
2.
3.
低秩矩阵补全问题作为一类在机器学习和图像处理等信息科学领域中都十分重要的问题已被广泛研究.一阶原始-对偶算法是求解该问题的经典算法之一.然而实际应用中处理的数据往往是大规模的.针对大规模矩阵补全问题,本文在原始-对偶算法的框架下,应用变步长校正技术,提出了一种改进的求解矩阵补全问题的原始-对偶算法.该算法在每一步迭代过程中,首先利用原始-对偶算法对原始变量和对偶变量进行更新,然后采用变步长校正技术对这两块变量进行进一步的校正更新.在一定的假设条件下,证明了新算法的全局收敛性.最后通过求解随机低秩矩阵补全问题及图像修复的实例验证新算法的有效性. 相似文献
4.
仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解Gram矩阵核范数极小化问题的一阶算法-改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子Tv来求解低秩Gram矩阵的恢复问题.同时,还引入Barzilai-Borwein技术进行参数的选取,提高了算法的收敛速度.数值实验显示算法不仅能够很快地将低秩Gram矩阵精确地恢复出来,对于一些非低秩矩阵的恢复问题也能得出较好的结果. 相似文献
5.
6.
7.
《运筹学学报》2020,(3)
低秩稀疏矩阵优化问题是一类带有组合性质的非凸非光滑优化问题.由于零模与秩函数的重要性和特殊性,这类NP-难矩阵优化问题的模型与算法研究在过去十几年里取得了长足发展。本文从稀疏矩阵优化问题、低秩矩阵优化问题、低秩加稀疏矩阵优化问题、以及低秩张量优化问题四个方面来综述其研究现状;其中,对稀疏矩阵优化问题,主要以稀疏逆协方差矩阵估计和列稀疏矩阵优化问题为典例进行概述,而对低秩矩阵优化问题,主要从凸松弛和因子分解法两个角度来概述秩约束优化和秩(正则)极小化问题的模型与算法研究。最后,总结了低秩稀疏矩阵优化研究中的一些关键与挑战问题,并提出了一些可以探讨的问题。 相似文献
8.
9.
本文提出了一种解无约束优化问题的新的非单调自适应信赖域方法.这种方法借助于目标函数的海赛矩阵的近似数量矩阵来确定信赖域半径.在通常的条件下,给出了新算法的全局收敛性以及局部超线性收敛的结果,数值试验验证了新的非单调方法的有效性. 相似文献
10.
11.
Tie Ni 《Applied mathematics and computation》2010,216(7):2207-3378
The smoothing-type algorithm has been successfully applied to solve various optimization problems. In general, the smoothing-type algorithm is designed based on some monotone line search. However, in order to achieve better numerical results, the non-monotone line search technique has been used in the numerical computations of some smoothing-type algorithms. In this paper, we propose a smoothing-type algorithm for solving the nonlinear complementarity problem with a non-monotone line search. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The preliminary numerical results are also reported. 相似文献
12.
In this paper, we propose a regularized version of the generalized
NCP-function proposed by Hu, Huang and Chen [J. Comput. Appl. Math., 230 (2009),
pp. 69-82]. Based on
this regularized function, we propose a semismooth Newton method for
solving nonlinear complementarity problems, where a non-monotone
line search scheme is used. In particular, we show that the proposed
non-monotone method is globally and locally superlinearly
convergent under suitable assumptions. We test the
proposed method by solving the test problems from MCPLIB.
Numerical experiments indicate that this algorithm has better
numerical performance in the case of $p=5$ and $\theta\in[0.25,075]$ than other cases. 相似文献
13.
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm 总被引:1,自引:0,他引:1
The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions??a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed. 相似文献
14.
Peng Wang Chengde Lin Xiaobo Yang Shengwu Xiong 《Journal of Applied Analysis & Computation》2020,10(3):1024-1037
Recovering low-rank and sparse matrix from a given matrix arises in many applications, such as image processing, video background substraction, and so on. The 3-block alternating direction method of multipliers (ADMM) has been applied successfully to solve convex problems with 3-block variables. However, the existing sufficient conditions to guarantee the convergence of the 3-block ADMM usually require the penalty parameter $\gamma$ to satisfy a certain bound, which may affect the performance of solving the large scale problem in practice. In this paper, we propose the 3-block ADMM to recover low-rank and sparse matrix from noisy observations. In theory, we prove that the 3-block ADMM is convergent when the penalty parameters satisfy a certain condition and the objective function value sequences generated by 3-block ADMM converge to the optimal value. Numerical experiments verify that proposed method can achieve higher performance than existing methods in terms of both efficiency and accuracy. 相似文献
15.
A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization 总被引:3,自引:0,他引:3
Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient. 相似文献
16.
倪勤 《高等学校计算数学学报(英文版)》1997,(1)
In this paper we report a sparse truncated Newton algorithm for handling large-scale simple bound nonlinear constrained minimixation problem. The truncated Newton method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At each iterative level, the search direction consists of three parts, one of which is a subspace truncated Newton direction, the other two are subspace gradient and modified gradient directions. The subspace truncated Newton direction is obtained by solving a sparse system of linear equations. The global convergence and quadratic convergence rate of the algorithm are proved and some numerical tests are given. 相似文献
17.
Zisheng Liu Jicheng Li Guo Li Jianchao Bai Xuenian Liu 《Journal of Applied Analysis & Computation》2017,7(2):600-616
The robust principal component analysis (RPCA) model is a popular method for solving problems with the nuclear norm and $\ell_1$ norm. However, it is time-consuming since in general one has to use the singular value decomposition in each iteration. In this paper, we introduce a novel model to reformulate the existed model by making use of low-rank matrix factorization to surrogate the nuclear norm for the sparse and low-rank decomposition problem. In such case we apply the Penalty Function Method (PFM) and Augmented Lagrangian Multipliers Method (ALMM) to solve this new non-convex optimization problem. Theoretically, corresponding to our methods, the convergence analysis is given respectively. Compared with classical RPCA, some practical numerical examples are simulated to show that our methods are much better than RPCA. 相似文献
18.
《Journal of Computational and Applied Mathematics》2005,175(2):335-353
The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices. 相似文献