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

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

非光滑凸优化问题的一个非精确梯度镜面下降算法

本文提出一个求解非光滑凸优化问题非精确梯度镜面下降算法.该算法是Allen-Zhu2016年提出求解光滑凸优化问题梯度镜面下降算法的推广,而且该算法允许目标函数中光滑部分梯度计算和非光滑部分邻近算子计算都存在误差,并且在适当条件下分析了该算法函数值序列的O(1/(k²))收敛速度,这里k表示迭代数.最后关于Lasso问题和Logistic问题的数值结果表明该算法是有效的.     

非凸不可分优化线性近似Bregman型Peaceman-Rachford分裂算法

基于Peaceman-Rachford分裂算法,结合线性近似技术和Bregman距离,本文提出一种线性近似Bregman型Peaceman-Rachford分裂算法,用于求解目标函数带不可分结构的线性约束非凸优化问题.在常规假设下,得到算法的全局收敛性.在效益函数满足Kurdyka-Lojasiewicz性质前提下,论证算法的强收敛性.当KurdykaLojasiewicz性质关联函数为特殊结构时,分析并获得算法的收敛率结果.最后,初步数值试验说明算法有数值有效性.     

修正乘子交替方向法求解三个可分离算子的凸优化

指出直接推广的经典乘子交替方向法对三个算子的问题不能保证收敛的原因, 并且给出将其改造成收敛算法的相应策略. 同时, 在一个统一框架下, 证明了修正的乘子交替方向法的收敛性和遍历意义下具有O(1/t)~收敛速率.     

一个结构型凸优化问题的分裂算法

考虑带线性约束的三块变量的凸优化模型,目标函数是可分的三个函数和.给出了一个新的分裂算法.首先,对每个块变量解极小化增广拉格朗日函数.然后,通过一个校正步得到新的迭代点.证明了新算法的整体收敛性和O(1/t)的收敛阶.     

两分块非凸优化Peaceman-Rachford分裂序列二次规划双步长算法

本文研究大规模两分块非凸约束优化的分解降维算法,提出Peaceman-Rachford (PR)分裂序列二次规划双步长求解方法.本文主要工作和贡献如下:(1)借助PR分裂算法思想将传统二次规划(quadratic programming, QP)子问题的增广Lagrange问题分解为两个小规模QP子问题;(2)通过求解小规模QP产生搜索方向;(3)以增广Lagrange函数为效益函数,沿搜索方向先后进行Armijo线搜索产生双迭代步长,在较弱的条件下保证了算法的全局收敛性、强收敛性和合理的迭代复杂性,克服了Maratos效应;(4)提出乘子新的对称型修正技术;(5)基于一类数学模型和电力系统经济调度模型以及?₂正则二分类问题,对算法进行大量中等规模的比较数值实验,验证了算法的有效性.     

均衡及约束凸优化问题公共解的一般迭代算法

梯度投影法在解决约束凸极小化问题中起到了重要的作用. 基于Tian的一般迭代算法, 本文将梯度投影法和平均算子方法相结合, 首次提出隐式和显式的复合迭代算法, 寻求均衡问题和约束凸极小化问题的公共解. 在适当条件下, 获得了强收敛定理.     

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

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

广义非凸变分不等式解的存在性与投影算法

本文运用Banach压缩映象原理和投影技巧研究一类新的广义非凸变分不等式问题解的存在唯一性,并在非凸集上建立一个逼近广义非凸变分不等式解的三步投影算法,在一定条件下证明了该投影算法所产生的迭代序列的收敛性.     

关于结构型单调变分不等式的平行分裂增广Lagrangian方法的O(1/t)阶收敛性(英文)

最近,何[3]证明了投影收缩算法的O(1/t)阶收敛性.受此启发,本文证明了结构型单调变分不等式的平行分裂增广Lagrangian方法的O(1/t)阶收敛性.     

A partial inexact alternating direction method for structured variational inequalities

In this article, a new method is proposed for solving a class of structured variational inequalities (SVIs). The proposed method is referred to as the partial inexact proximal alternating direction (piPAD) method. In the method, two subproblems are solved independently. One is handled by an inexact proximal point method and the other is solved directly. This feature is the major difference between the proposed method and some existing alternating direction-like methods. The convergence of the piPAD method is proved. Two examples of the modern convex optimization problem arising from engineering and information sciences, which can be reformulated into the encountered SVIs, are presented to demonstrate the applicability of the piPAD method. Also, some preliminary numerical results are reported to validate the feasibility and efficiency of the piPAD method.     

An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures

Splitting methods have been extensively studied in the context of convex programming and variational inequalities with separable structures. Recently, a parallel splitting method based on the augmented Lagrangian method (abbreviated as PSALM) was proposed in He (Comput. Optim. Appl. 42:195?C212, 2009) for solving variational inequalities with separable structures. In this paper, we propose the inexact version of the PSALM approach, which solves the resulting subproblems of PSALM approximately by an inexact proximal point method. For the inexact PSALM, the resulting proximal subproblems have closed-form solutions when the proximal parameters and inexact terms are chosen appropriately. We show the efficiency of the inexact PSALM numerically by some preliminary numerical experiments.     

An ADM-based splitting method for separable convex programming

We consider the convex minimization problem with linear constraints and a block-separable objective function which is represented as the sum of three functions without coupled variables. To solve this model, it is empirically effective to extend straightforwardly the alternating direction method of multipliers (ADM for short). But, the convergence of this straightforward extension of ADM is still not proved theoretically. Based on ADM’s straightforward extension, this paper presents a new splitting method for the model under consideration, which is empirically competitive to the straightforward extension of ADM and meanwhile the global convergence can be proved under standard assumptions. At each iteration, the new method corrects the output of the straightforward extension of ADM by some slight correction computation to generate a new iterate. Thus, the implementation of the new method is almost as easy as that of ADM’s straightforward extension. We show the numerical efficiency of the new method by some applications in the areas of image processing and statistics.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

An exterior point method for the convex programming problem

This paper gives a proof of convergence of an iterative method for maximizing a concave function subject to inequality constraints involving convex functions. The linear programming problem is an important special case. The primary feature is that each iteration is very simple computationally, involving only one of the constraints. Although the paper is theoretical in nature, some numerical results are included.The author wishes to express his gratitude to Ms. A. Dunham, who provided a great deal of assistance in carrying out the computations presented in this paper.     

A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.