一种求解合作博弈最公平核心的非精确平行分裂算法

针对合作博弈核心和Shapley值的特点, 将最公平核心问题转化为带有两个变 量的可分离凸优化问题, 引入结构变分不等式的算子分裂方法框架, 提出了求解最公平核心的一种非精确平行分裂算法. 而且, 该算法充分利用了所求解问题的可行域的简单闭凸性, 子问题的非精确求解是容易的. 最后, 简单算例的数值实验表明了算法的收敛性和有效性.     

一种求解两两合作轮流博弈问题的混合分裂算法

提出了一种求解两两合作轮流博弈的四人博弈问题的混合分裂算法.为了模拟实际博弈过程,该算法由两个组内平行分裂算法和一个组间交替极小化算法构成.算法允许对博弈子问题非精确求解,反映了实际博弈中参与人的有限理性,即允许参与人在博弈过程中出现满足一定条件的误差.在适当条件下,证明了所提出的混合分裂算法全局地收敛到所考虑博弈的Nash平衡.     

解一类结构变分不等式问题的非精确并行交替方向法

带线性约束的具有两分块结构的单调变分不等式问题, 出现在许多现代应用中, 如交通和经济问题等. 基于该问题良好的可分结构, 分裂型算法被广泛研究用于其求解. 提出新的带回代的非精确并行交替方向法解该类问题, 在每一步迭代中,首先以并行模式通过投影得到预测点, 然后对其校正得到下一步的迭代点. 在压缩型算法的理论框架下, 在适当条件下证明了所提算法的全局收敛性. 数值结果表明了算法的有效性. 此外, 该算法可推广到求解具有多分块结构的问题.     

多重集非凸分裂可行问题的非精确均值投影算法

在本文中,我们引入了非精确均值投影算法来求解多重集非凸分裂可行问题,其中这些非凸集合为半代数邻近正则集合.通过借助著名的Kurdyka-Lojasiewicz不等式理论,我们建立了算法的收敛性.     

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

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

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

本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确求解过程中发现其仍是目标函数可分离变量的凸优化问题,由于其变量都是矩阵,所以采用适合多个矩阵变量的交替方向法求解,通过引入新的变量,使其每个子问题的解都具有显示表达式.最后给出采用的G-ADMM法求解本文问题的数值实验.数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题.     

基于信赖域技术的处理带线性约束优化的内点算法

基于信赖域技术,本文提出了一个求解带线性等式和非负约束优化问题的内点算法,其特点是:为了求得搜索方向,算法在每一步迭代时仅需要求解一线性方程组系统,从而避免了求解带信赖域界的子问题,然后利用非精确的Armijo线搜索法来得到下一个迭代内点. 从数值计算的观点来看,这种技巧可减少计算量.在适当的条件下,文中还证明了该算法所产生的迭代序列的每一个聚点都是原问题的KKT点.     

求解单调包含问题的惯性混合非精确邻近点算法

本文提出了求解单调包含问题的一类新的惯性混合非精确邻近点算法(简记为iHIPPA)在适当的参数假设下,我们证明了求解单调包含问题的iHIPPA所产生点列的弱收敛性,获得了iHIPPA的非渐近收敛率为■及iHIPPA的遍历迭代复杂性为O(1/k).作为应用,我们还建立了求解单调变分包含问题的惯性邻近收缩算法,求解广义变分不等式问题的惯性投影邻近点算法,及求解原始一对偶问题的惯性非精确调比部分逆算法产生点列的收敛性及相应算法的非渐近收敛率及遍历迭代复杂性.本文结果推广和改进了文献中的相应结论.最后,本文应用新的惯性交替方向乘子法用以求解LASSO问题,而且一些初步的试验结果表明了新的算法的优越性.     

非精确信赖域类型算法及收敛性分析

在求解大规模数据的优化问题时,由于数据规模和维数较大,传统的算法效率较低.本文通过采用非精确梯度和非精确Hessian矩阵来降低计算成本,提出了非精确信赖域算法和非精确自适应三次正则化算法.在一定条件下,证明了算法有限步停止,并估计了算法迭代的复杂度.特别地,我们分析了采用随机抽样时算法在给定概率下的复杂度.最后,通过二分类问题的数值求解,比较了本文提出的随机信赖域算法,随机自适应三次正则化算法和已有算法收敛效率.数值结果表明在相同精度下,本文提出的算法效率更高,并且随机自适应三次正则化算法的效率优于随机信赖域算法.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

A Riemannian variant of the Fletcher–Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata

In this paper, we focus on the stochastic inverse eigenvalue problem with partial eigendata of constructing a stochastic matrix from the prescribed partial eigendata. A Riemannian variant of the Fletcher–Reeves conjugate gradient method is proposed for solving a general unconstrained minimization problem on a Riemannian manifold, and the corresponding global convergence is established under some assumptions. Then, we reformulate the inverse problem as a nonlinear least squares problem over a matrix oblique manifold, and the application of the proposed geometric method to the nonlinear least squares problem is investigated. The proposed geometric method is also applied to the case of prescribed entries and the case of column stochastic matrix. Finally, some numerical tests are reported to illustrate that the proposed geometric method is effective for solving the inverse problem.     

非线性l1问题的光滑近似算法

为非线性l1问题的求解构造了光滑逼近函数.首先将非线性l1问题转化为等价的不可微优化问题;其次通过两步提出光滑逼近函数的一般性构造方法;最后进行了数值仿真.文中介绍了光滑逼近函数的有关性质,指出相关文献已有的光滑函数方法是本文的特例,并证明了方法的收敛性及有效性.     

An optimization method for solving some differential algebraic equations

In this paper, the problem of differential algebraic equations has been solved via Chebyshev integral method combined with an optimization method. Two approaches are used based on the index of the problem: in the first, the proposed method is applied on the original problem and in the second, the index of the problem is decreased and the modified problem is solved. An optimization technique is proposed to solve the resulting algebraic equations. Numerical results are included to confirm the efficiency and accuracy of the method.     

A primal interior point method for the linear semidefinite programming problem

The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved.     

Derivative-Free Filter Simulated Annealing Method for Constrained Continuous Global Optimization

In this paper, a simulated-annealing-based method called Filter Simulated Annealing (FSA) method is proposed to deal with the constrained global optimization problem. The considered problem is reformulated so as to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the FSA method is applied to solve the reformulated problem. The FSA method invokes a multi-start diversification scheme in order to achieve an efficient exploration process. To deal with the considered problem, a filter-set-based procedure is built in the FSA structure. Finally, an intensification scheme is applied as a final stage of the proposed method in order to overcome the slow convergence of SA-based methods. The computational results obtained by the FSA method are promising and show a superior performance of the proposed method, which is a point-to-point method, against population-based methods.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

一类非线性两级整数规划问题的全局优化方法

本文研究了整数规划连续化的途径,对一类非线性两级整数规划问题的上级规划连续化以后采用模拟退火算法;其对应的下级规划问题采用离散搜索法求解,从而给出了求解一类非线性两级整数规划问题的一种全局优化算法,并通过算例验证了该算法是有效的.     

Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales

A new method for solving the problem of equivalence of linear unary recursive programs is proposed. The main idea behind this method is to reduce the equivalence problem to known problems on graphs and to problems in group theory. A class of program semantics is singled out for which the problem of the equivalence of the programs in question is solvable in polynomial time by the proposed method.     

Riemannian Newton-type methods for joint diagonalization on the Stiefel manifold with application to independent component analysis

The joint approximate diagonalization of non-commuting symmetric matrices is an important process in independent component analysis. This problem can be formulated as an optimization problem on the Stiefel manifold that can be solved using Riemannian optimization techniques. Among the available optimization techniques, this study utilizes the Riemannian Newton’s method for the joint diagonalization problem on the Stiefel manifold, which has quadratic convergence. In particular, the resultant Newton’s equation can be effectively solved by means of the Kronecker product and the vec and veck operators, which reduce the dimension of the equation to that of the Stiefel manifold. Numerical experiments are performed to show that the proposed method improves the accuracy of the approximate solution to this problem. The proposed method is also applied to independent component analysis for the image separation problem. The proposed Newton method further leads to a novel and fast Riemannian trust-region Newton method for the joint diagonalization problem.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.