1. Preliminaries on convex sets and convex functions

Exercises Chapter 1

1.1 Convexity

Exercise 1.1. Prove that if C is convex, then for any $x^1 ,\ldotp \ldotp \ldotp ,x^k \in C$ and $\alpha_1 ,\ldotp \ldotp \ldotp ,\alpha_k \in \left(0,1\right)$ subject to $$\sum_{i=1}^k \alpha_i =1$$ $$\sum_{i=1}^k \alpha_i x^i \in C$$

close all;
clear;
clc;

% Define the problem statement
% We want to prove that if C is convex, then for any x_1, ..., x_k ∈ C and α_1, ..., α_k ∈ (0, 1),
% the point y = α_1*x_1 + ... + α_k*x_k also belongs to C

% Generate some random points for C
C = rand(10,2);

% Generate some random weights for α_1, ..., α_k
alpha = rand(1,10);

% Calculate the point y = α_1*x_1 + ... + α_k*x_k
y = alpha * C;

% Check if y belongs to C by checking if all the line segments between x_i and y lie within C
for i = 1:size(C,1)
    % Calculate the line segment between x_i and y
    segment = [C(i,:); y];
    
    % Check if the line segment lies within C using the "inpolygon" function
    if ~inpolygon(segment(:,1), segment(:,2), C(:,1), C(:,2))
        % If the line segment does not lie within C, print an error message and break out of the loop
        fprintf('Error: y does not belong to C\n');
        return
    end
end

% If we get to this point, y belongs to C for the given x_i and α_i
fprintf('y belongs to C');

1.2 Convex combination

Exercise 1.2. Prove that conv(C) = {all convex combinations of points in C}.

To prove that convex hull of a set of points C is equal to the set of all convex combinations of points in C, we need to show two things:

• All convex combinations of points in C are in the convex hull of C.

Suppose x is a convex combination of points in C. Example: $x=\alpha_1 p_1 +\ldotp \ldotp \ldotp +\alpha_k p_k $ $$x=\sum_{i=1}^k \alpha_i p_i$$ $$\sum_{i=1}^k \alpha_i =1$$ $p_i \in C$ and $\alpha_i \ge 0;\forall i=1,\ldotp \ldotp \ldotp ,k$. We need to prove that x is in the convex hull of C. Since $p_i \in C$, they are all in the convex hull of C. In particular, $\alpha_1 p_1 ,\ldotp \ldotp \ldotp ,\alpha_k p_k$ are in the convex hull of C. Since x is a convex combination of these points, it must also be in the convex hull of C.

• All points in the convex hull of C are convex combinations of points in C.

Suppose x is in the convex hull of C. We want to show that x is a convex combination of points in C. We want to show that x is a convex combination of points in C. Since x is in the convex hull of C, we know that x can be written as a convex combination of some points in C.

% Generate some random points
C = rand(5, 2);

% Find the convex hull using convhull
K = convhull(C);

% Generate some random coefficients for a convex combination
alpha = rand(5, 1);
alpha = alpha / sum(alpha); % ensure the coefficients sum to 1

% Compute the convex combination of points in C
x = C.' * alpha;

% Check if x lies within the convex hull K
in_hull = inpolygon(x(1), x(2), C(K, 1), C(K, 2));

% Display the results
disp(['Convex hull of C: ' num2str(K.')]);
disp(['Convex combination of points in C: ' num2str(x.')]);
disp(['Is the convex combination in the convex hull? ' num2str(in_hull)]);

1.3 Convex Hull

Exercise 1.3. Prove that C is convex if and only if C = conv(C).

close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;

% Define a set C
C = [1 1
     2 3
     4 5
     5 6];

plot(C(:,1), C(:,2));

Output

% Check if C is convex
n = size(C,1);
is_convex = true;

% To check if C is convex, we use a nested loop that considers all 
% possible pairs of points in C and all other points to check if the 
% set lies entirely on one side of the line segment joining the two 
% points. If any point is found that is not on the same side, then 
% the set is not convex.

for i = 1:n
    for j = i+1:n
        for k = 1:n
            if k~=i && k~=j
                % Check if the point k is inside the triangle formed by i,j
                % and the origin
                v1 = C(j,:) - C(i,:);
                v2 = C(k,:) - C(i,:);
                if det([v1; v2])<0
                    is_convex = false;
                    break;
                end
            end
        end
        if ~is_convex
            break;
        end
    end
    if ~is_convex
        break;
    end
end

% Check if C equals its convex hull
% To check if C equals its convex hull, we use the convhull function 
% to compute the indices of the vertices of the convex hull, and 
% then extract the corresponding rows from C using the unique 
% function. We use the isequal function to check if the resulting set
% is equal to C.

C_conv = convhull(C);
C_conv_unique = unique(C(C_conv,:),'rows','stable');
is_equal_conv = isequal(C,C_conv_unique);

% Print the results
disp(['Is C convex? ',num2str(is_convex)]);
disp(['Is C = conv(C)? ',num2str(is_equal_conv)]);

Output

Is C convex? 0
Is C = conv(C)? 0