-
Notifications
You must be signed in to change notification settings - Fork 0
/
get_c_minus.m
147 lines (130 loc) · 3.95 KB
/
get_c_minus.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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
function [c, i] = get_c_minus(A, b, y0, MAXITER, DEBUG)
% USAGE
% c = get_c_minus(A, b, [y], [k], [DEBUG])
%
% DESCRIPTION
% This function finds and returns vector c such that ∂F_c is non-convex through a stochastic
% algorithm using up to k iterations.
%
% This function consequently generates up to k random directions d and for each one finds vector c normal
% to ∂G at the boundary point y + td ∈ ∂G. Next it finds ∂F_c, the intersection of F with the supporting
% hyperplane orthogonal to c and checks if it is non-convex.
%
% If y and k are not specified, the unction uses default values y = f(0) = 0 and k = 10.
%
% DEBUG, if set to 1, will produce additional output indicating progress. Default value is 0
% which gives no additional output
%
% INPUT
% * A -- tensor of rank 3
% Dimensions: n x n x m
% The element A(i, j, k) denotes i'th row and j'th column of the n x n matrix A_k
% (k from 1 to m)
%
% * b -- tensor of rank 2
% Dimensions: n x m
% The element b(i, k) denotes i'th element of the vector b_k (k from 1 to m)
%
% * y (optional) -- column vector
% Dimensions: m x 1
% The point inside G = conv F, where F is the image of the quadratic map specified
% by A and b. This point is used in the heuristic algorithm, see get_c_from_d
% Default: f(0)
%
% * k (optional) -- integer
% This parameter specifies the number of iterations for the heuristic algorithm.
% The procedure will use up to k random directions d. If your current k does not
% yield the vector c, try larger number k
% Default: 10
%
% OUTPUT
% This function stops and returns c if non-convexity of ∂F c was established during one
% of the iterations. If the vector c was not found, an exception is produced.
%
% EXAMPLE
%% Unset all variables in the workspace
%clear all;
%
%% should be executed from the root project folder which contains the file README.md
%ls README.md
%% ans = README.md
%
%% Load the map from file
%load('examples/maps/article_example05_R4_R4.mat');
%
%% Construct y in G
%x = [1 1 0 0]';
%y = quadratic_map(A, b, x);
%
%% Fix the random seed
%rng(10);
%
%% Run the procedure
%get_c_minus(A, b, y, 10, 1)
%% ans = 0.7891 0.3782 -0.3916 -0.2843
%
% COPYRIGHT
% CAQM: Convexity Analysis of Quadratic Maps
% Copyright (c) 2015-2017 Anatoly Dymarsky, Elena Gryazina, Sergei Volodin, Boris Polyak
%
%% Implementation
%% Processing arguments
% error message on too few arguments
if nargin < 2
error('This function accepts at least 2 arguments, see readme.pdf');
end
% 2 arguments => assuming y0 = f(0)
if nargin == 2
y0 = quadratic_map(A, b, zeros(size(A, 1), 1));
end
% no 4th argument => assuming MAXITER=10
if nargin <= 3
MAXITER = 10;
end
% no 5th argument => assuming no debug
if nargin <= 4
DEBUG = 0;
end
%% check for infeasibility
is_infeasible = infeasibility_oracle(A, b, y0);
if is_infeasible
error('The input point y0 is not in the convex hull G (proven by infeasibility oracle). Please find a point y0 in G = conv F to use in this function.');
end
%% initializing
% resulting c
c = [];
% m dimension
m = size(A, 3);
% H from article
H = get_H(A, b);
% is c found?
found = 0;
% iterator
i = 0;
%% looking for c
% making MAXITER attemts or less
while (~found) && (i < MAXITER)
if DEBUG
fprintf('get_c_minus attempt %d\n', i);
end
% random direction
d = randn(m, 1);
% obtaining c via dual problem
c = get_c_from_d_H(H, y0, d);
% checking if c is a vector
if size(c, 1) == m
% checking nonconvexity
if is_nonconvex(A, b, c)
found = 1;
else
c = [];
end
end
i = i + 1;
end
if size(c, 1) == 0
error('No c_minus found');
end
% normalizing
c = c / norm(c);
end