论文标题
分析用于凸复合优化的Frank-Wolfe方法，涉及对数障碍
Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier
论文作者
论文摘要
我们提出并分析了一种用于复合优化问题$（p）的新的广义弗兰克 - 沃尔夫方法：{\ min} _ {x \ in \ mathbb {r}^n} \; f（\ mathsf {a} x） + h（x）$，其中$ f $是$θ$ -logarithMarithmos-logarithmos-均匀的自信屏障，$ \ mathsf {a} $是线性操作员，函数$ h $ h $具有界限，但可能不太平滑。 We show that our generalized Frank-Wolfe method requires $O((δ_0 + θ+ R_h)\ln(δ_0) + (θ+ R_h)^2/\varepsilon)$ iterations to produce an $\varepsilon$-approximate solution, where $δ_0$ denotes the initial optimality gap and $R_h$ is the variation of $h$ on its domain.该结果建立了$θ$ logarithMarithmanty均匀障碍与Frank-Wolfe方法之间的某些内在连接。当专门针对$ d $ - 最佳的设计问题时，我们实际上是通过使用弗兰克·沃尔夫（Frank-Wolfe）方法和精确的线路搜索来恢复哈奇扬（Khachiyan）获得的复杂性。我们还研究了$（p）$的（Fenchel）双重问题，我们表明我们的新方法等同于适用于双重问题的自适应步骤尺寸的镜像下降方法。尽管双重目标函数是非lipschitz，并且具有无限的域，但即使双重目标函数，这使我们能够为镜下下降法提供迭代复杂性界限。此外，我们提出的计算实验表明，我们广义的弗兰克 - 沃尔夫方法对泊松图像进行电视正则化问题以及模拟宠物问题实例的潜在有用性。
We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem $(P):{\min}_{x\in\mathbb{R}^n}\; f(\mathsf{A} x) + h(x)$, where $f$ is a $θ$-logarithmically-homogeneous self-concordant barrier, $\mathsf{A}$ is a linear operator and the function $h$ has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires $O((δ_0 + θ+ R_h)\ln(δ_0) + (θ+ R_h)^2/\varepsilon)$ iterations to produce an $\varepsilon$-approximate solution, where $δ_0$ denotes the initial optimality gap and $R_h$ is the variation of $h$ on its domain. This result establishes certain intrinsic connections between $θ$-logarithmically homogeneous barriers and the Frank-Wolfe method. When specialized to the $D$-optimal design problem, we essentially recover the complexity obtained by Khachiyan using the Frank-Wolfe method with exact line-search. We also study the (Fenchel) dual problem of $(P)$, and we show that our new method is equivalent to an adaptive-step-size mirror descent method applied to the dual problem. This enables us to provide iteration complexity bounds for the mirror descent method despite even though the dual objective function is non-Lipschitz and has unbounded domain. In addition, we present computational experiments that point to the potential usefulness of our generalized Frank-Wolfe method on Poisson image de-blurring problems with TV regularization, and on simulated PET problem instances.
