% Function to compute the CONVEX Regression of the response y on the data matrix x
% Function NEEDS the PACKAGE cvx (see http://cvxr.com/cvx/) to be installed in the computer 

% y: the response variable -- a column vector of length n
% x: the data matrix of the predictors (of size n*p);
% Note that the vector of ones is NOT required in the data matrix

% th: the value of the fitted response

% The function also gives estimates of the sub-gradients at each data point
% and is stored in the 'eta' matrix

% Note that for sample sizes of 200 or more, the function can be very slow!
% It involves n(n-1) many constraints  

function [th] = ComputeConvexFn(x,y)
n = length(y);
d = size(x); d = d(2);

cvx_begin quiet
    %cvx_precision low
    variable th(n)
    variable eta(d,n)
    minimize(norm(y-th))
    subject to
        for i = 1:n,
            for j = 1:n,
                if(i ~=j) th(i) - th(j) <= (x(i,:) - x(j,:))*eta(:,i); end
            end
        end
cvx_end

end
