diff --git a/codes/convex_example_bp/bp_nonconvex_adap.m b/codes/convex_example_bp/bp_nonconvex_adap.m new file mode 100755 index 0000000..2eef019 --- /dev/null +++ b/codes/convex_example_bp/bp_nonconvex_adap.m @@ -0,0 +1,179 @@ +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') + + + diff --git a/codes/convex_example_bp/update_params.m b/codes/convex_example_bp/update_params.m new file mode 100755 index 0000000..5841c1f --- /dev/null +++ b/codes/convex_example_bp/update_params.m @@ -0,0 +1,46 @@ +function [beta_, sigma_, k_t] = update_params(feas_cur, feas_old, k_t, iter, beta_old, sigma_old, sigma_vec, beta_vec, sigma_0, beta_0) +% This function computes the parameters for the new iteration depending on +% the predefined adaptive rule +% INPUTS: feas_cur: current feasibility value +% iter : current iteration number +% sigma_0 : initial value for the dual step size +% beta_0 : initial value for the penalty parameter +% OUTPUTS: beta_ : updated penalty parameter +% sigma_ : updated dual step size +% +% Author: Mehmet Fatih Sahin +% Date: 09.11.2018 + +if iter<2 + beta_ = beta_0; + sigma_ = sigma_0; + return +end + +if feas_cur > beta_0/sqrt(iter) + beta_ = beta_old*sqrt(iter/(iter-1)); +else + beta_ = beta_old; +end + +if feas_old <= sigma_0/sqrt(iter-1) && feas_cur > sigma_0/sqrt(iter) + k_t = iter; +end + +if feas_cur <= sigma_0/iter + sigma_ = sigma_old; +elseif sigma_0/iter < feas_cur && feas_cur<=sigma_0/sqrt(iter) + sigma_ = sigma_old*sqrt((iter-1)/iter); +else +% sigma_ = sigma_0/beta_0*(beta_-beta_old); + if k_t == iter + sigma_ = sigma_old/(beta_-beta_vec(k_t))*(beta_-beta_old); + elseif k_t == 1 + sigma_ = sigma_0/beta_0*(beta_-beta_old); + else + sigma_ = sigma_vec(k_t)/(beta_vec(k_t+1)-beta_vec(k_t))*(beta_-beta_old); + end +end + + +end \ No newline at end of file