一类线性约束矩阵不等式及其最小二乘问题

本文主要考虑一类线性矩阵不等式及其最小二乘问题,它等价于相应的矩阵不等式最小非负偏差问题.之前相关文献提出了求解该类最小非负偏差问题的迭代方法,但该方法在每步迭代过程中需要精确求解一个约束最小二乘子问题,因此对规模较大的问题,整个迭代过程需要耗费巨大的计算量.为了提高计算效率,本文在现有算法的基础上,提出了一类修正迭代方法.该方法在每步迭代过程中利用有限步的矩阵型LSQR方法求解一个低维矩阵Krylov子空间上的约束最小二乘子问题,降低了整个迭代所需的计算量.进一步运用投影定理以及相关的矩阵分析方法证明了该修正算法的收敛性,最后通过数值例子验证了本文的理论结果以及算法的有效性.     

Scaled Optimal Path Trust-Region Algorithm

Trust-region algorithms solve a trust-region subproblem at each iteration. Among the methods solving the subproblem, the optimal path algorithm obtains the solution to the subproblem in full-dimensional space by using the eigenvalues and eigenvectors of the system. Although the idea is attractive, the existing optimal path method seems impractical because, in addition to factorization, it requires either the calculation of the full eigensystem of a matrix or repeated factorizations of matrices at each iteration. In this paper, we propose a scaled optimal path trust-region algorithm. The algorithm finds a solution of the subproblem in full-dimensional space by just one Bunch–Parlett factorization for symmetric matrices at each iteration and by using the resulting unit lower triangular factor to scale the variables in the problem. A scaled optimal path can then be formed easily. The algorithm has good convergence properties under commonly used conditions. Computational results for small-scale and large-scale optimization problems are presented which show that the algorithm is robust and effective.     

基于判别超图和非负矩阵分解的人脸识别方法

非负矩阵分解是一种流行的数据表示方法,已广泛应用于图像处理和模式识别等问题.但是非负矩阵分解忽略了数据的几何结构. 而现有的基于简单图的学习方法只考虑了图像的成对信息,并且对计算相似度时的参数选择非常敏感. 超图学习方法可以有效地解决这些问题. 超图利用超边将多个顶点相连接用以表示图像的高维结构信息. 然而, 现有的大部分超图学习方法都是无判别的学习方法.为了提高识别效果, 提出了基于具有判别信息的超图和非负矩阵分解方法的新模型, 利用交替方向法进行迭代求解新模型, 并结合最近邻方法进行人脸识别. 在几个常用标准人脸图像数据库上进行实验, 实验结果表明提出的方法是有效的.     

The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

一类单调变分不等式的非精确交替方向法

交替方向法适合于求解大规模问题.该文对于一类变分不等式提出了一种新的交替方向法.在每步迭代计算中,新方法提出了易于计算的子问题,该子问题由强单调的线性变分不等式和良态的非线性方程系统构成.基于子问题的精确求解,该文证明了算法的收敛性.进一步,又提出了一类非精确交替方向法,每步迭代计算只需非精确求解子问题.在一定的非精确条件下,算法的收敛性得以证明.     

一类不可微二次规划逆问题

本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确...     

Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization

At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.     

Active-Set Projected Trust-Region Algorithm for Box-Constrained Nonsmooth Equations

In this paper, by means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.     

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

A Decomposition Method for a Unilateral Contact Problem with Tresca Friction Arising in Electro-elastostatics

This article is concerned with the numerical modeling of unilateral contact problems in an electro-elastic material with Tresca friction law and electrical conductivity condition. First, we prove the existence and uniqueness of the weak solution of the model. Rather than deriving a solution method for the full coupled problem, we present and study a successive iterative (decomposition) method. The idea is to solve successively a displacement subproblem and an electric potential subproblem in block Gauss-Seidel fashion. The displacement subproblem leads to a constraint non-differentiable (convex) minimization problem for which we propose an augmented Lagrangian algorithm. The electric potential unknown is computed explicitly using the Riesz's representation theorem. The convergence of the iterative decomposition method is proved. Some numerical experiments are carried out to illustrate the performances of the proposed algorithm.     

An alternating direction algorithm for matrix completion with nonnegative factors

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.     

Nonmonotonic trust region algorithm

A nonmonotonic trust region method for unconstrained optimization problems is presented. Although the method allows the sequence of values of the objective function to be nonmonotonic, convergence properties similar to those for the usual trust region method are proved under certain conditions, including conditions on the approximate solutions to the subproblem. To make the solution satisfy these conditions, an algorithm to solve the subproblem is also established. Finally, some numerical results are reported which show that the nonmonotonic trust region method is superior to the usual trust region method according to both the number of gradient evaluations and the number of function evaluations.The authors would like to thank Professor L. C. W. Dixon for his useful suggestions.     

An Iterative LP Algorithm for Quadratic Spatial Equilibria

This paper describes a partitioning algorithm based on the Benders decomposition to solve net import spatial equilibrium models. The method decomposes the problem into a linear master problem and a quadratic subproblem. It is shown that the quadratic subproblem is trivial, and the associated dual variables can be determined through ordinary calculus. Therefore, the quadratic spatial equilibrium problem is solved iteratively by using linear programming software.     

An efficient feasible SQP algorithm for inequality constrained optimization

In this paper, an efficient feasible SQP method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction. Per single iteration, it is only necessary to solve one QP subproblem and a system of linear equations with only a subset of the constraints estimated as active. In addition, its global and superlinear convergence are obtained under some suitable conditions.     

Solving Variational Inequality Problems with Linear Constraints by a Proximal Decomposition Algorithm

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.     

Augmented Lagrangian Methods for $p$-Harmonic Flows with the Generalized Penalization Terms and Application to Image Processing

In this paper, we propose a generalized penalization technique and a convex constraint minimization approach for the $p$-harmonic flow problem following the ideas in [Kang & March, IEEE T. Image Process., 16 (2007), 2251-2261]. We use fast algorithms to solve the subproblems, such as the dual projection methods, primal-dual methods and augmented Lagrangian methods. With a special penalization term, some special algorithms are presented. Numerical experiments are given to demonstrate the performance of the proposed methods. We successfully show that our algorithms are effective and efficient due to two reasons: the solver for subproblem is fast in essence and there is no need to solve the subproblem accurately (even 2 inner iterations of the subproblem are enough). It is also observed that better PSNR values are produced using the new algorithms.     

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

逻辑回归是经典的分类方法,广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有程。模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取,且一般是NP-难的.为了求解这类问题,提出了嵌套BB(Barzilai and Borwein)算法的分裂增广拉格朗日算法(SALM-BB).该算法在迭代中交替地求解一个无约束凸优化问题和一个带程。模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带程。模约束二次优化问题的精确解,并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明,相对于一阶算法SLEP,SALM-BB能够得到更低的平均逻辑损失和错分率.     

多周期公用工程系统运行的模型,优化方法与应用

针对多周期公用工程系统的运行优化问题，考虑了设备的启停费用的情况下。建立了混合整数非线性规划模型并证明了最优解的存在性。针对该运行优化问题本将其分解成若干子问题，然后利用改进的Hooke-Jeeves优化算法求解每个子问题。应用于具体实例，其数值结果与其它方法得到的相比。运行时间短，且更适合多周期公用工程问题的求解。     

An accelerated first-order method with complexity analysis for solving cubic regularization subproblems

Computational Optimization and Applications - We propose a first-order method to solve the cubic regularization subproblem (CRS) based on a novel reformulation. The reformulation is a constrained...     

高阶优化算法分析简介

高阶优化算法是利用目标函数的高阶导数信息进行优化的算法,是最优化领域中的一个新兴的研究方向.高阶算法具有更低的迭代复杂度,但是需要求解一个更难的子问题.主要介绍三种高阶算法,分别为求解凸问题的高阶加速张量算法和A-HPE框架下的最优张量算法,以及求解非凸问题的ARp算法.同时也介绍了怎样求解高阶算法的子问题.希望通过对高阶算法的介绍,引起更多学者的关注与重视.