How do i check if a cost function is Concave or Convex?

Question

How do i check if this cost function is concave or convex? I also want to find if this has a single or multiple minimums.

Effort Made;

   function [w,pi,costvalue] = main_cost(inputdata, tmax,   alpha_ini,somrow,somcol)
   %main cost function; To get cost value for all possible random weights
   %Input:
   %inputdata : Data sample
   %tmax : Maximum Iteraitions - This determines the number of generated
   %random w and pi with cost function computation for each set. 
   %alpha_ini : The learning rate
   %Somrow,somcol : map size 

   %Output
   %w: Som weights 
   %pi: Global weights
   %costvalue: cost for a set of w,pi and input data

   %Example
   %load expdata_normalized;
   %[w,pi,costvalue]=main_cost(expdata_normalized,500,0.1,5,5);

   N = somrow * somcol; %all neurons
   Dimension = size(inputdata,2);%input data dimension
   % Get the corresponding 2D locations of the N neurons on the map
  [u(:,1) u(:,2)] = ind2sub([somrow somcol], 1:N);
  alpha = alpha_ini; %set initial learning rate

  %set map effective width
  sigma_ini = 2;
  sigma = sigma_ini;


  %initialise costvalues
  costval=zeros(1,tmax);

  %for 1 to max iterations
  for t = 1:tmax
  tic
 %generate random SOM weights
 w{t} = round(rand(N,Dimension),1);
 %generate random Global weights
 pi{t} = round (rand(1,Dimension),1);

% For 1 to all samples in the data
for j = 1:size(inputdata,1) 
   % Pick a single sample
    samplei = inputdata(j,:);
   % make global weight same dimension with SOM weights
    pirepmat = repmat(pi{t},N,1);
    % determine the winning node, from weights at iter(t) to picked
    % sample
    bmu = part1_closestNeuron(samplei, w{t},1,pirepmat);
    % calculate neighbourhood for SOM at iter (t)
    for k = 1:size(w{t},1)
        neighbourhoodF = exp(-eucdist(u(bmu,:),u(k,:), somrow, somcol, 1)^2 / (2*sigma^2));
        allneighbourhoodF(k)= neighbourhoodF;
    end
    % now get cost value with; inputdata(all-static), Somweights at
    % iter(t), and Global weights at iter(t)
    costval(t) = costval(t)+CostFunction_iter(inputdata, w{t},pi{t},allneighbourhoodF);
end
toc
end
costvalue = costval;
end

What i tried doing in the code above is to get a random weight values as inputs for the above cost function, then calculate the cost value for those random inputs with a sample that doesn't change, if i find multiple minimum cost, then that confirms that my cost function is not convex.

My code is slightly different from the cost function i posted in my question, as i have an additional input. As an output from my implementation, i have the cost values for different weights against my sample, now i am having trouble visualizing this.

Answer 1

You need to learn what convexity is. For the short version, check Wikipedia.

For a more detailed version, I recommend this lecture 2 and this lecture 3 of Boyd's course on convex optimization. The beginning part of that course introduces a bunch of useful math for identifying/checking convexity.

If a function is not convex, you can disprove convexity by finding a counterexample:

• Graph the function if 2d or 3d.
• Plot the value of the function applied to convex combinations of two random points and look for non-convex regions.

Convexity is violated if there exists two points x and y along with a scalar a in [0,1] such that a * f(x) + (1-a) * f(y) < f(a*x +(1-a) * y) (basically somewhere with a downward curve).

Failing to disprove convexity is not the same as proving convexity! Some approaches to prove convexity are:

• Show Hessian is positive semi-definite.
• Apply the definition of convexity directly (show def. satisfied for all possibilities)
• Show the function is convex by construction rules... eg. the pointwise maximum of a set of convex functions is convex. etc... apply theorems like that.

---

Glancing at the posted image, a norm is always convex (consequence of definition). A sum of convex functions is convex, but I don't know what that K thing is...