一类凸优化的混合下降算法

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

一种惯性邻近的Peaceman-Rachford分裂方法

严格压缩的Peaceman-Rachford(PR)分裂方法是一种收敛速度快于交替方向乘子法的求解线性约束可分离凸优化问题的有效方法.最近提出的半邻近PR分裂方法是严格压缩的PR分裂方法的一种改进方法.基于惯性邻近交替方向乘子法的思想,本文进一步改进了半邻近PR分裂方法,提出了一种惯性邻近PR分裂方法.该方法利用前两次产生的迭代点来产生新的迭代点,可以加速半邻近PR分裂方法的收敛.本文提出的方法具有一般性,它包含严格压缩的PR分裂方法和半邻近PR分裂方法作为特殊情形.在一定的假设下,本文证明了该算法产生的迭代序列的渐进可行性及函数值的收敛性,进而得到了迭代序列的全局收敛性.最后,本文通过数值试验说明了算法的有效性.     

非凸约束优化的随机近似算法

在人工智能、科学计算等领域,众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂,同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来,结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类:基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结,简要地介绍相关算法的设计思想和基本的理论性质,如渐近收敛性理论、复杂度理论等。     

二次规划的内椭球算法

对于标准型的凸二次规划问题本文给出了一个新算法，算法的一每步迭代，利用内椭球的思想来近似求解一个线性质规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ＾２），每一步迭代所需计算量为Ｏ（ｎ＾３）。其中ｎ为变量个数，Ｌ为问题的输入长度。     

集值优化问题在有效意义下的最优性条件

本文在赋范空间中,讨论集值优化问题的有效元导数型最优性条件.当目标映射和约束映射的下方向导数存在时,在近似锥次类凸假设下利用有效点的性质和凸集分离定理得到了集值优化问题有效元导数型Kuhn-Thcker必要条件,在可微Г-拟凸性的假设下得到了Kuhn-Tucker最优性充分条件;此外利用集值映射沿弱方向锥的导数的特性给出了有效解最优性的另一种刻画.     

我和乘子交替方向法20年

1997 年, 交通网络分析方面的问题把我引进乘子交替方向法(ADMM)的研究领域. 近10 年来, 原本用来求解变分不等式的ADMM在优化计算中被广泛采用, 影响越来越大. 这里总结了20 年来我们在ADMM 方面的工作, 特别是近10 年 ADMM 在凸优化分裂收缩算法方面的进展. 梳理主要结果, 说清来龙去脉. 文章利用变分不等式的形式研究凸优化的ADMM 类算法, 论及的所有方法都能纳入一个简单的预测-校正统一框架. 在统一框架下证明算法的收缩性质特别简单. 通读, 有利于了解ADMM类算法的概貌. 仔细阅读, 也许就掌握了根据实际问题需要构造分裂算法的基本技巧. 也要清醒地看到, ADMM类算法源自增广拉格朗日乘子法 (ALM) 和邻近点 (PPA)算法, 它只是便于利用问题的可分离结构, 并没有消除 ALM和PPA等一阶算法固有的缺点.     

Armijo线性搜索下的多步下降算法

本文研究无约束优化问题.利用前面多步迭代点的信息产生下降方向以及Armijo线性搜索产生步长,得到了一类新的多步下降算法,并且在较弱条件下证明了算法具有全局收敛性和线性收敛速率.初步的数值试验表明算法是有效的.     

三个可分离算子凸优化的线性化方法

本文研究了三个可分离算子不含交叉变量的线性约束凸优化问题.利用定制的邻近点算法,对其变分不等式子问题进行线性化处理,并增加一邻近点项,使其子问题成为易于运算的单调线性变分不等式,得到了线性化定制的邻近点算法,并证明了全局收敛性,推广了文献中的研究结果.     

面向全局优化基于分形的混合混沌优化算法

Julia集具有分形结构,一旦确定吸引域边界上任一点,就可通向任一个吸引周期点的吸引域.Newton-Raphson法利用此性质可计算方程所有根,并可精确计算BFGS法和共轭梯度法中下降方向步长,将两种算法分别与混沌优化算法结合,因而从新的视角建立一种融合分形理论的混合混沌优化算法.研究表明,所提出算法的计算效率高于利用Wolf一维不精确搜索求得步长的混合算法,而且混合混沌BFGS算法的优化能力优于混合混沌共轭梯度算法,也说明BFGS的局部搜索能力比共轭梯度法强.     

DC函数优化问题的非精确邻近点算法

本文对DC函数(即两凸函数之差)的最小化问题提出了一个非精确邻近点算法,并证明此算法的下降性和全局收敛性.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

A Hybrid Approximate Extragradient – Proximal Point Algorithm Using the Enlargement of a Maximal Monotone Operator

We propose a modification of the classical extragradient and proximal point algorithms for finding a zero of a maximal monotone operator in a Hilbert space. At each iteration of the method, an approximate extragradient-type step is performed using information obtained from an approximate solution of a proximal point subproblem. The algorithm is of a hybrid type, as it combines steps of the extragradient and proximal methods. Furthermore, the algorithm uses elements in the enlargement (proposed by Burachik, Iusem and Svaiter) of the operator defining the problem. One of the important features of our approach is that it allows significant relaxation of tolerance requirements imposed on the solution of proximal point subproblems. This yields a more practical proximal-algorithm-based framework. Weak global convergence and local linear rate of convergence are established under suitable assumptions. It is further demonstrated that the modified forward-backward splitting algorithm of Tseng falls within the presented general framework.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

Equilibrium programming using proximal-like algorithms

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncooperative games, and variational inequalities. Under a monotonicity hypothesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation requires two proximal steps, possibly using Bregman functions. One step serves to predict the next point; the other helps to correct the new prediction. To enhance practical applicability we tolerate numerical errors. Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

An APPA-based descent method with optimal step-sizes for monotone variational inequalities

To solve monotone variational inequalities, some existing APPA-based descent methods utilize the iterates generated by the well-known approximate proximal point algorithms (APPA) to construct descent directions. This paper aims at improving these APPA-based descent methods by incorporating optimal step-sizes in both the extra-gradient steps and the descent steps. Global convergence is proved under mild assumptions. The superiority to existing methods is verified both theoretically and computationally.     

一个基于近似下降方向的免梯度算法

本构造一个求解非线性无约束优化问题的免梯度算法，该算法基于传统的模矢法，每次不成功迭代后，充分利用已有迭代点的信息，构造近似下降方向，产生新的迭代点。在较弱条件下，算法是总体收敛的。通过数值实验与传统模矢法相比，计算量明显减少。