Page MenuHomec4science
Files F65081001

Test_maxcut.m
No OneTemporary
Actions

File Metadata

Created
Fri, May 31, 15:52

Test_maxcut.m
View Options

% TEST MAXCUT: Main file for solving sdp relaxation of maxcut problem using
% inexact augmented lagrangian method.
% minimize <C, X>
% subject to: diag(X) = n
% X positive-semi-definite
%
% Data: You may download the data from <a href="matlab:
% web('https://www.cise.ufl.edu/research/sparse/matrices/Gset/index.html')">Gset-Uf Sparse Dateset Collection</a>
% The graph must be symmetric.
%
% Author: Mehmet Fatih Sahin
% Date : 02.11.2018
clearvars
close all
vec = @(x)reshape( x, numel( x ), 1 );
addpath(genpath('./functions/'));
addpath(genpath('./helpers/'));
%% function settings
dataNum = 2; % default data number if no input
userinput = 1; % if enabled data is selected from the command line
maxcut_load_data();
normA = 1;
normC = normest(C);
%% Initializations
fprintf('Data size: %dx%d \n',n,n)
f_grad_u = @(u, beta, yc) (1/beta).*bsxfun(@times, u, A_id(u, u) - y) + C*u + bsxfun(@times, u, yc);
f_u = @(u) sum(vec(u .* (C*u)));
proj = @(u) u;
get_feas = @(u) A_id(u, u) - y;
gamma_rule = @(beta_, yc) beta_/(2*beta_*normC +2*normA^2 + 2*norm((beta_*yc-y))); % rule for the stepsize: later add linesearch for that
%% Define algorithmic parameters and rules
r = 20; % target rank: you may set it sqrt(n)
beta0 = normC/5e1; % initial value for the penalty parameter
sigma0 = beta0*1e2; % initial value for dual step size
update_params = @(feas_cur, feas_old, k_t, iter, beta_old, sigma_old, sigma_vec, beta_vec) update_params(feas_cur, feas_old, k_t, iter, beta_old, sigma_old, sigma_vec, beta_vec, sigma0, beta0);
params.averaging = 0;
params.iters = 1e4;% Number of iterations
params.verbose = 1e3;
params.Uinit = rand(n, r); % In case a random initialization is used
params.ycinit = zeros(size(y));
params.savehist = 1;
params.startfeasible = 1; % start from a feasible point
%% Run the algorithm
[Udl, output] = linearized_augmented_lagrangian(f_u, f_grad_u, proj, update_params, ...
gamma_rule, get_feas, params);
%% Plot results
maxcut_solve_cvx()
plot_results()

Event Timeline

c4science · Help