(@author bodonoghue) MATLAB script
Implements an Accelerated Proximal Gradient method
(Nesterov 2007, Beck and Teboulle 2009)
solves:
minimize f(x) + h(x)
over x \in R^dim_x
where f is smooth, convex - user supplies function to evaluate gradient of f
h is convex - user supplies function to evaluate the proximal operator of h
call as:
x = apg( grad_f, prox_h, dim_x, opts )
this takes in two function handles:
grad_f(v, opts) = df(v)/dv
(gradient of f at v)
prox_h(v, t, opts) = argmin_x ( t * h(x) + 1/2 * norm(x-v)^2 )
where t is the (scalar, positive) step size at that iteration
if h = 0, then use prox_h = [] or prox_h = @(x,t,opts)(x)
put all necessary function data in opts struct
each iteration of apg requires one gradient evaluation of f and one prox step with h
quits when:
norm( y(k) - x(k+1) ) < EPS * max( 1,norm( x(k+1) )
apg implements something similar to TFOCS step-size adaptation (Becker, Candes and Grant 2010)
and gradient-scheme adaptive restarting (O'Donoghue and Candes 2013)
see examples/ for usage instances
optional opts fields defined are below (with defaults)
to use defaults simply call apg with opts = []
X_INIT = zeros(dim_x,1); % initial starting point
USE_RESTART = true; % use adaptive restart scheme
MAX_ITERS = 2000; % maximum iterations before termination
EPS = 1e-6; % tolerance for termination
ALPHA = 1.01; % step-size growth factor
BETA = 0.5; % step-size shrinkage factor
QUIET = false; % if false writes out information every 100 iters
GEN_PLOTS = true; % if true generates plots of proximal gradient
USE_GRA = false; % if true uses unaccelerated proximal gradient descent
Example of usage:
function x = apg_lasso(A, b, rho, opts)
% uses apg to solve a lasso problem
%
% min_x (1/2)*sum_square(A*x - b) + rho * norm(x,1)
%
% rho is the L1-regularization weight
opts.A = A;
opts.b = b;
opts.rho = rho;
x = apg(@quad_grad, @soft_thresh, size(A,2), opts);
end
function g = quad_grad(x, opts)
g = opts.A'*(opts.A*x - opts.b);
end
function v = soft_thresh(x, t, opts)
v = sign(x) .* max(abs(x) - t*opts.rho,0);
end
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent