Block-CoordinateGradientDescentmethod_贪婪块坐标下降算法资源-CSDN文库

5星 · 超过95%的资源需积分: 49 78 浏览量 2012-03-15 20:54:23 上传评论收藏 506KB PDF 举报

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n2/) iterations with an -optimal solution. If P is separable, then the Gauss- Southwell-q rule is implementable in O(n) operations when m = 1 and in O(n2) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m = 1, ### Block-Coordinate Gradient Descent Method #### 概述本文主要介绍了一种称为块坐标梯度下降(Block-Coordinate Gradient Descent, BCGD)的方法，该方法用于解决带有线性等式约束条件的非光滑可分离优化问题。具体地，考虑最小化一个由平滑函数\(f\)和凸函数\(P\)的加权和构成的目标函数，其中目标函数受\(m\)个线性等式的约束。BCGD方法通过选择一个基于Gauss-Southwell-q规则的坐标块来实现迭代更新。 #### 方法原理 **问题定义** 设有一个优化问题，其目标是最小化\(n\)个实变量的加权和，形式为： \[ \min_{x \in \mathbb{R}^n} F_c(x) \triangleq f(x) + cQ(x), \] 其中\(c > 0\)且 \[ Q(x) \triangleq P(x) + \delta_C(x), \] 这里\(f: \mathbb{R}^n \rightarrow \mathbb{R}\)是一个连续可微的平滑函数，\(P: \mathbb{R}^n \rightarrow \mathbb{R} \cup \{+\infty\}\)是凸函数，\(\delta_C\)表示特征函数，\(C\)是满足\(m\)个线性等式约束的闭集。即，对于某个矩阵\(A \in \mathbb{R}^{m \times n}\)和向量\(b \in \mathbb{R}^m\)，我们有 \[ C \triangleq \{x \in \mathbb{R}^n | Ax = b\}. \] **BCGD方法** 该方法通过迭代更新来逼近最优解，每次迭代选择一个坐标块，并根据该块上的梯度进行更新。坐标块的选择依据Gauss-Southwell-q规则，该规则基于预测的充分下降程度来决定。当\(P\)是可分离的，即可以写成\(n\)个独立项之和时，Gauss-Southwell-q规则可以有效地实现。特别地，当\(m = 1\)时，该规则可以在\(O(n)\)的时间复杂度内实现；而当\(m > 1\)时，则在\(O(n^2)\)的时间复杂度内实现。 #### 收敛性与复杂度分析 **收敛性** 对于BCGD方法，可以证明它具有全局收敛到一阶驻点的性质。此外，在局部误差界假设下，该方法还具有线性的收敛率。 **复杂度** 如果函数\(f\)是凸的并且梯度是Lipschitz连续的，则BCGD方法可以在\(O(n^2/\epsilon)\)次迭代后找到一个\(\epsilon\)-最优解。这个结果对于支持向量机(Support Vector Machines, SVM)训练来说尤其有意义，因为在SVM训练中\(f\)是凸二次的，\(P\)是可分离的，并且只有\(m = 1\)个线性约束条件。此时，BCGD方法的复杂度与已知的最佳分解方法相当。 #### 特殊情况：支持向量机训练在支持向量机训练这一特殊情况下，\(f\)是一个凸二次函数，\(P\)是可分离的，并且只存在一个线性等式约束。在这种情况下，BCGD方法不仅有效而且高效。它的复杂度与目前最佳的分解方法相似，这表明BCGD方法在处理这类问题时非常有竞争力。 #### 扩展应用：双层优化问题如果\(f\)是凸的，可以通过逐渐减少\(P\)的权重至零的方式将BCGD方法扩展应用于双层优化问题。即，最小化\(P\)在\(f + \delta_X\)的极小值集上，其中\(X\)表示可行集的闭包。这种扩展在最小1-范数解的最大似然估计中有应用。 #### 结论 BCGD方法是一种有效的优化算法，适用于带有线性等式约束的非光滑可分离优化问题。它具有良好的理论保证，包括全局收敛性和线性收敛率，并且在支持向量机训练等特殊情况下表现出优秀的性能。此外，该方法还可以通过适当的修改应用于更广泛的优化问题中，如双层优化问题。这些特性使得BCGD成为解决这类优化问题的强大工具。

资源推荐

资源详情

资源评论

J Optim Theory Appl (2009) 140: 513–535

DOI 10.1007/s10957-008-9458-3

Block-Coordinate Gradient Descent Method

for Linearly Constrained Nonsmooth Separable

Optimization

P. Tseng ·S. Yun

Published online: 30 September 2008

Abstract We consider the problem of minimizing the weighted sum of a smooth

function f and a convex function P of n real variables subject to m linear equality

constraints. We propose a block-coordinate gradient descent method for solving this

problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on suf-

ﬁcient predicted descent. We establish global convergence to ﬁrst-order stationarity

for this method and, under a local error bound assumption, linear rate of conver-

gence. If f is convex with Lipschitz continuous gradient, then the method terminates

in O(n

/) iterations with an -optimal solution. If P is separable, then the Gauss-

Southwell-q rule is implementable in O(n) operations when m = 1 and in O(n

)

operations when m>1. In the special case of support vector machines training, for

which f is convex quadratic, P is separable, and m = 1, this complexity bound is

comparable to the best known bound for decomposition methods. If f is convex,

then, by gradually reducing the weight on P to zero, the method can be adapted to

solve the bilevel problem of minimizing P over the set of minima of f +δ

, where

X denotes the closure of the feasible set. This has application in the least 1-norm

solution of maximum-likelihood estimation.

Keywords Nonsmooth optimization · Linear constraints · Support vector

machines · Bilevel optimization ·

-regularization · Coordinate gradient descent ·

Global convergence ·Linear convergence rate · Complexity bound

Communicated by A. Miele.

This research was supported by the National Science Foundation, Grant No. DMS-0511283.

P. T se n g (



)

Department of Mathematics, University of Washington, Seattle, WA, USA

e-mail: tseng@math.washington.edu

S. Yun

Department of Mathematics, National University of Singapore, Singapore, Republic of Singapore

e-mail: matys@nus.edu.sg

514 J Optim Theory Appl (2009) 140: 513–535

1 Introduction

We consider a class of constrained nonsmooth optimization problems of the form

min

x∈

(x)

def

= f(x)+cQ(x), (1)

where c>0,

Q(x)

def



P(x), if Ax =b,

∞, else,

P :

→(−∞, ∞]is a proper, convex, lower semicontinuous (lsc) function [1], A ∈



m×n

, b ∈

, and f is real-valued and smooth (i.e., continuously differentiable) on

an open subset of 

containing dom Q ={x | Q(x) < ∞}. We assume dom Q = ∅.

Then Q is proper, convex, lsc, and Q is polyhedral whenever P is polyhedral. The

objective function F

is in general nonsmooth and nonconvex. Of particular interest

is the case when m is small, n is large, and P is separable, i.e.,

P(x)=



j=1

), (2)

for some proper, convex, lsc functions P

:→(−∞, ∞]. However, Q is not sepa-

rable due to the constraints Ax =b (unless m =0).

The problem (1) with P separable is quite general and includes as special cases

problems of box-constrained smooth optimization and, more generally, nonsmooth

separable optimization (m = 0) [2–6], as well as monotropic optimization (f ≡ 0)

[7], and linearly constrained smooth optimization (P is the indicator function for a

box) [8–11]. In applications arising in signal denoising, image processing, and data

classiﬁcation, the problem is often large scale (n ≥10000) and P may be nonsmooth

to induce solution sparsity; see [12–19] and references therein. Such applications in-

clude Basis Pursuit/Lasso (f is convex quadratic, P is the 1-norm, m = 0) [13, 14,

16] and support vector machine (SVM) training (f is quadratic, P is the indicator

function for a box, m = 1) [20, 21]. Methods that update x one coordinate block at

a time are well suited to solve these problems, due to their low computational cost

per iteration and ease of implementation and parallelization. Such methods include

(block) SOR methods for ﬁnding sparse representation of signals and decomposition

methods for SVM training; see [8, 16, 17, 19–28] and references therein. Recently,

block-coordinate gradient descent (CGD) methods were proposed in [6] for solving

the case of m =

0 and then extended in [29] for linearly constrained smooth opti-

mization. These methods approximate f by a quadratic at the current iterate x, apply

block-coordinate descent to generate a feasible descent direction d, and then update

x by performing an inexact line search along d. Numerical experiences in [6, 29, 30]

suggest that the CGD methods can be effective in practice.

In this paper, we extend the CGD methods in [6, 29] to solve the general prob-

lem (1). As in [6, 29], we choose the coordinate block according to a Gauss-

Southwell-q rule and choose the stepsize according to an Armijo-like rule; see (7)

and (10). (In [6], a Gauss-Seidel rule and a Gauss-Southwell-r rule for choosing the

J Optim Theory Appl (2009) 140: 513–535 515

coordinate block are also considered. We do not consider them here for reasons to

be explained in Sect. 8.) Our main contributions are three-fold. First, we show that,

in the case where P is separable and piecewise-linear/quadratic with O(1) pieces,

the Gauss-Southwell-q rule is implementable in O(n) operations when m =1 and in

O(n

) operations when m>1; see Sect. 6. This is based on conformal realization [7,

Sect. 10B], [31] of a diagonally scaled gradient “projection” direction, and extends

the procedure in [29, Sect. 6] for linearly constrained smooth optimization. The re-

sulting method uses only O(n) operations per iteration when m = 1, P is separable

and piecewise-linear/quadratic with O(1) pieces (e.g., 1-norm), and f is quadratic

or has a partially separable structure; see the end of Sect. 6. Second, we show that,

for any >0, the CGD method terminates in O(n

/) iterations with an -optimal

solution, assuming f is convex with Lipschitz continuous gradient; see Theorem 5.1.

This is the ﬁrst complexity bound for a CGD method. When specialized to the train-

ing of SVM (m = 1, P is the indicator function for a box



j=1

], and f is

quadratic), the resulting complexity bound of



b

max



 max



0, log



init

) −min

(x))

max



operations for achieving -optimality, where b

max

=max

1≤j≤n

−l

) and  is the

maximum norm of the 2 ×2 principal submatrices of ∇

f(x), is comparable to the

currently best bounds for decomposition methods [26, 32, 33]; see Sect. 6 for details.

In addition, the method achieves global convergence to ﬁrst-order stationarity and,

under a local error bound assumption, linear rate of convergence; see Theorems 4.1

and 4.2. This generalizes [6, Theorem 3] and [29, Theorem 5.1] for the cases of m =0

and linearly constrained smooth optimization. Third, when f is convex and under a

mild assumption on Q, we show that, by gradually decreasing c towards zero at a

suitable rate during the execution of the CGD method, we can solve the following

bilevel problem:

min

x∈S

Q(x), (3)

where S

denotes the set of minima of f over X, where X denotes the closure of

domQ. This problem arises, for example, in the least 1-norm solution of a least

square problem or a maximum likelihood estimation problem [16, 17].

In our notation, 

denotes the space of n-dimensional real column vectors,

de-

notes transpose. For any x ∈

, x

denotes the j th component of x, x

denotes the

subvector of x comprising x

, j ∈ J, and x

= (



j=1

)

1/p

for 1 ≤p<∞

and x

∞

= max

|. For simplicity, we write x=x

. For any nonempty

J ⊆ N ={1,...,n}, |J| denotes the cardinality of J. For any symmetric matrices

H,D ∈

n×n

, we write H  D (respectively, H D) to mean that H −D is positive

semideﬁnite (respectively, positive deﬁnite). H

=[H

]

i,j∈J

denotes the princi-

pal submatrix of H indexed by J. λ

min

(H ) and λ

max

(H ) denote the minimum and

maximum eigenvalues of H . We denote by I the identity matrix and by 0 the matrix

of zero entries. Unless otherwise speciﬁed, {x

} denotes the sequence x

,....

516 J Optim Theory Appl (2009) 140: 513–535

2 (Block) Coordinate Gradient Descent Method

In this section, we describe our method for solving (1). As in [6, 29], we use ∇f(x)to

build a quadratic approximation of f at x and apply coordinate descent to generate

a feasible descent direction d at x. More precisely, we choose a nonempty subset

J ⊆N, a symmetric matrix H ∈

n×n

, and move x along the direction

(x;J)

def

= argmin

d∈



∇f(x)

d +

Hd +cQ(x +d) |d

=0 ∀j/∈J



. (4)

Here d

(x;J) depends on H through H

only. To ensure that d

(x;J) is well

deﬁned, we assume that H

is positive deﬁnite on Null(A

) (the null space of A

)

or, equivalently, B

0, where A

denotes the submatrix of A comprising

columns indexed by J and B

is a matrix whose columns form an orthonormal basis

for Null(A

). The direction (4) reduces to those used in [6, 29] when m =0orP is

the indicator function for a box.

First, we have the following generalization of [6, Lemma 1] and [29, Lemma 2.1],

showing that a nonzero d

(x;J) is a descent direction of F

at x. We include its

proof for completeness.

Lemma 2.1 Fo r a ny x ∈dom Q, nonempty J ⊆N and symmetric H ∈

n×n

with

0, let d =d

(x;J) and g =∇f(x). Then,

(x +αd) ≤F

(x) +α(g

d +cQ(x +d)−cQ(x)) +o(α), ∀α ∈ (0, 1], (5)

d +cQ(x +d)−cQ(x) ≤−d

Hd ≤−λ

min

)d

. (6)

Proof Inequality (5) and the ﬁrst inequality in (6) follow from [6, Lemma 1]. Since

∈Null(A

), so that d

y for some vector y,wehave

Hd =y

y ≥y

min

) =d

min

where the second equality uses B

= I . This proves the second inequality

in (6). 

We now describe formally the block-coordinate gradient descent (abbreviated as

CGD) method.

CGD Method

Choose x

∈domQ.Fork =0, 1, 2,..., generate x

k+1

from x

according to the

following iteration:

Step 1. Choose a nonempty J

⊆N and a symmetric H

∈

n×n

with

0.

Step 2. Solve (4) with x =x

, J =J

,H=H

to obtain d

Step 3. Choose a stepsize α

> 0 and set x

k+1

+α

剩余22页未读，继续阅读

评论收藏

内容反馈

snowwhitexiang

2014-02-27

文章确实很经典，非常值得看
moshe_tianxing

2014-05-20

文章很经典，帮助很大
lf200806410256

2014-05-14

很好！我正需要。
胡秀韬

2018-06-18

有用，个人感觉很好。
broken33333hf

2013-08-14

文章很经典，推荐下载

niedx2007

粉丝: 9
资源: 25

Block-Coordinate Gradient Descent method

最新资源

Block-Coordinate Gradient Descent method

Lasso-Coordinate-Descent:L1正则化解决LASSO回归问题的循环和随机坐标下降算法的实现

gradientDescent

递归下降算法

wechat-Coordinate-wechat-Coordinate.rar

google-api-services-coordinate-v1-rev43-1.16.0-rc.zip

worldwindjava源码-Geo-Coordinate-Conversion-Java:NASAWorldWind的坐标转换功能

matlab开发-coordinateTransformation

calculat-the-coordinate.rar_标定板

基于Springboot框架的destiny-coordinate后端模块设计源码

Laravel开发-coordinate

ABS-ER-Coordinate Systems-v2.pdf

Unity3D-Coordinate system coordination(Finished).rar

A Unified Algorithmic Framework for Block-Structured Optimization Involving

AdaBatch: Efficient Gradient Aggregation.pdf

local-coordinate-transform:基于最小二乘的lib将2d坐标转换为wgs84坐标，反之亦然

SFM--(local-coordinate-estimation).rar_3d sfm制作_MATLAB三维重建_SFM三维

coordinate-picker:将 div 转换为可以在其上选取坐标的 Google 地图的 JQuery 插件

C-coordinate-conversion-master.rar_conversion_pramscals_四参数七参数_四

is-valid-coordinate:验证坐标

ccd.rar_coordinate descent_descent

ecef-1.01-P2-.tar.gz

C-coordinate-conversion:C＃坐标转换程序4参数7参数

js-practice-coordinate:我做了一个简单的js练习示例

PlaceName-CoordinateTransformation:用于坐标和POI点的转换

Space-time--vector-coordinate-system.rar_matlab例程_WORD_

android-coordinate-layout:坐标布局= SuperSet（framelayout）视图在其他视图更改时响应

A theoretical and experimental study on no-guide light pen type 3D-coordinate measurement system

BitBlt方法应用事例

LiuGangKingston-Nestable-coordinate-system-for-TikZ-circuits

kinect-2-coordinate-mapping:使用 Kinect for Windows 版本 2 的坐标映射

最新资源