Homec4science
Diffusion Nonlinear (master) Browse

R7172/codes/convex_example_bp/bp_nonconvex_adap.m
4f9ff70f0445master

Last Change
Raw File

bp_nonconvex_adap.m
View Options

clear all
scale = 1;
p = scale*100;
n = scale*40;
s = scale*1;
A = normr(randn(n, p));
x_org = zeros(p, 1);
T = randsample(p, s);
x_org(T) = randn(s, 1);
sigma = 1e-4;
b = A*x_org + sigma*randn(n, 1);
%% Solve by CVX
cvx_precision best;
cvx_solver SDPT3
cvx_begin
variable x_cvx(p);
minimize( (norm(x_cvx, 1)) );
subject to
A*x_cvx == b;
cvx_end
fopt = cvx_optval;
probParams.x_cvx = x_cvx;
%% constant params
prox_l1 = @(x, tau) sign(x).*max(abs(x)-tau, 0);
obj = @(x) norm(x,1);
LA = norm(full(A));
beta0 = 1e-1;
beta = beta0;
sigma0 = beta0*(1e1);
x0 = zeros(p, 1);
x = x0;
y0 = zeros(n, 1);
y = y0;
maxit = 1e5;
obj_vec_const = zeros(maxit, 1);
feas_const = zeros(maxit, 1);
betas = zeros(maxit, 1);
sigmas = zeros(maxit, 1);
sigma = sigma0;
k0= 0;
feas = norm(A*x-b);
feas_old = inf;
beta_1 = beta0/2;
beta_tilde_1 = beta0/2;
beta_tilde = beta0;
k_t = 1;
beta_old = beta;
sigma_old = sigma;
iter_const = zeros(maxit, 1);
for ii = 2:maxit
% beta0_old=beta0;
% if feas_old <= beta0/sqrt(ii*log(ii+1)) && feas > beta0/sqrt(ii*log(ii+1))
% k0 = 1
% k_t = ii;
% % beta_1 = beta_old;
% beta_tilde_1 = beta;
% sigma_tilde_1 = sigma;
% end
betas(ii) = beta;
sigmas(ii) = sigma;
% if feas <= beta0/sqrt(ii*log(ii+1))
% % disp('beta1')
% beta = beta;
% else
% % disp('beta2')
% beta = beta * sqrt((ii*log(ii+1))/((ii-1)*log(ii)));
% end
% if ii == k_t
% beta_tilde=beta;
% end
% if ii == 3
% beta1=beta;
% end
% if k0 == 1 && ii == k_t
% beta1=beta;
% end
% % beta = beta0*sqrt(ii);
gamma = 1/(beta*LA);
%
% if feas <= sigma0/(ii*log(ii+1))
% % disp('sigma1')
% sigma = sigma;
% elseif feas > sigma0/(ii*log(ii+1)) && feas <= sigma0 /sqrt(ii*log(ii+1))
% % disp('sigma2')
% sigma = sigma * sqrt(((ii-1)*log(ii))/(ii*log(ii+1)));
% elseif feas > sigma0/sqrt(ii*log(ii+1))
% % disp('sigma3')
% % sigma = sigma0 * (beta - beta_old)/()
% % if ii == 2
% % sigma = sigma0/beta0 * (beta-beta_old);
% % else
% % if ii == 2
% % sigma = sigma0;
% % else
% % if k0 == 0
% % sigma = sigma0 * (beta-beta_old)/(beta0);
% sigma=sigma0*(beta-beta_old)/(beta_tilde-beta_tilde_1);
% % else
% % sigma = sigma0 * (beta-beta_old)/(beta1-beta0);
% % end
% % end
% % end
% end
% if isnan(sigma)
% keyboard
% end
% sigma = sigma0*sqrt(ii);
x = prox_l1(x - gamma*A'*(y + beta*(A*x-b)), gamma);
% sigma = 1e2*beta0/sqrt(ii);
feas = norm(A*x-b);
[beta, sigma, k_t] = update_params(feas,feas_old, k_t, ii, beta_old, sigma_old, sigmas, betas, sigma0, beta0);
y = y + sigma * (A*x-b);
obj_vec_const(ii) = obj(x);
feas_const(ii) = norm(A*x-b);
iter_const(ii) = norm(x-x_org);
feas_old = feas;
beta_old = beta;
sigma_old = sigma;
end
%%
figure, loglog(betas), hold on, loglog(sigmas, '.-'), legend('beta', 'sigma');grid on;
%% decreasing params
LA = norm(full(A));
beta0 = 1e1;
beta = beta0;
gamma = 1/(LA*beta);
x0 = zeros(p, 1);
x = x0;
y0 = zeros(n, 1);
y = y0;
obj_vec_dec = zeros(maxit, 1);
feas_dec = zeros(maxit, 1);
iter_dec= zeros(maxit, 1);
sigmas_dec=zeros(maxit, 1);
betas_dec=zeros(maxit, 1);
for ii = 1:maxit
beta = beta0*(ii);
% beta=beta0;
gamma = 1/(beta*LA);
x = prox_l1(x - gamma*A'*(y + beta*(A*x-b)), gamma);
sigma = beta0;
sigma = beta;
y = y + sigma * (A*x-b);
obj_vec_dec(ii) = obj(x);
feas_dec(ii) = norm(A*x-b);
iter_dec(ii) = norm(x-x_org);
sigmas_dec(ii)=sigma;
betas_dec(ii)=beta;
end
%%
figure, subplot(131), loglog(abs(obj_vec_const-fopt)), hold on, loglog(abs(obj_vec_dec-fopt)), legend('adaptive', 'constant')
subplot(132), loglog(feas_const), hold on, loglog(feas_dec), legend('adaptive', 'constant')
subplot(133), loglog(iter_const), hold on, loglog(iter_dec), legend('adaptive', 'constant')
c4science · Help