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 Hull

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)]);