forked from ndwork/dworkLib
-
Notifications
You must be signed in to change notification settings - Fork 0
/
chambollePock.m
110 lines (98 loc) · 3.26 KB
/
chambollePock.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
function [xStar,objValues] = chambollePock( x, proxf, proxgConj, tau, varargin )
% [xStar,objValues] = chambollePock( x, proxf, proxgConj, tau [, ...
% 'A', A, 'f', f, 'g', g, 'N', N, 'normA', normA, 'sigma', sigma, ...
% 'verbose', verbose ] )
%
% minimizes f( x ) + g( A x )
%
% Inputs:
% x - initial guess
% proxf - a function handle for the proximal operator of
% proxgConj - a function handle for the proximal operator of the conjugate of g
%
% Optional Inputs:
% A - if A is not provided, it is assumed to be the identity
% f - to determine the objective values, f must be provided
% g - to determine the objective values, g must be provided
% N - the number of iterations that ADMM will perform (default is 100)
% normA - the matrix induced 2-norm of A. Could be determined with norm or, for
% large sparse matries, estimated with normest or powerIteration.
% verbose - true or false
%
% Outputs:
% xStar - the optimal point
%
% Optional Outputs:
% objValues - a 1D array containing the objective value of each iteration
%
% Written by Nicholas Dwork - Copyright 2019
%
% This software is offered under the GNU General Public License 3.0. It
% is offered without any warranty expressed or implied, including the
% implied warranties of merchantability or fitness for a particular
% purpose.
p = inputParser;
p.addParameter( 'A', [] );
p.addParameter( 'f', [] );
p.addParameter( 'g', [] );
p.addParameter( 'N', 100, @ispositive );
p.addParameter( 'normA', [], @ispositive );
p.addParameter( 'sigma', [], @ispositive );
p.addParameter( 'theta', 1, @(x) x > 0 && x < 2 );
p.addParameter( 'verbose', false, @(x) islogical(x) || x==1 || x==0 );
p.addParameter( 'printEvery', 1, @ispositive );
p.parse( varargin{:} );
A = p.Results.A;
f = p.Results.f;
g = p.Results.g;
N = p.Results.N;
normA = p.Results.normA;
sigma = p.Results.sigma;
theta = p.Results.theta;
printEvery = p.Results.printEvery;
verbose = p.Results.verbose;
if numel( A ) == 0
applyA = @(x) x;
applyAT = @(x) x;
elseif isnumeric( A )
applyA = @(x) A * x;
applyAT = @(y) A' * y;
else
applyA = @(x) A( x, 'notransp' );
applyAT = @(x) A( x, 'transp' );
end
if numel( sigma ) == 0 && numel( A ) > 0
if numel( normA ) == 0
error( 'If an A is supplied, you must supply sigma or normA' );
end
sigma = ( 0.95 / normA^2 ) / tau;
end
xBar = x;
if nargout > 1, objValues = zeros( N, 1 ); end
for optIter = 1 : N
if optIter == 1
tmp = sigma * applyA( xBar );
else
tmp = z + sigma * applyA( xBar );
end
z = proxgConj( tmp, sigma );
lastX = x;
tmp = x - tau * applyAT( z );
x = proxf( tmp, tau );
if nargout > 1
objValues( optIter ) = f( x ) + g( applyA( x ) );
end
if verbose == true
if mod(optIter,printEvery) == 0 || optIter == 1
if nargout > 1
disp([ 'chambollePock: working on ', indx2str(optIter,N), ' of ', num2str(N), ', ', ...
'objective value: ', num2str( objValues( optIter ), '%15.13f' ) ]);
else
disp([ 'chambollePock: working on ', indx2str(optIter,N), ' of ', num2str(N) ]);
end
end
end
xBar = x + theta * ( x - lastX );
end
xStar = x;
end