I am studying algorithms and i saw a definition like the following:
Given $3$ points $p_1 = (x_1, y_1)$, $p_2 = (x_2, y_2)$ and $p_3 = (x_3, y_3)$, $p_3$ is a convex combination of $p_1$ and $p_2$ iff $\exists 0 \le a \le 1$ such that:
(i) $x_3 = x_1 + (1 −a )x_2$
(ii) $y_3 = y_1 + (1 − a)y_2$
If $p_3$ is a convex combination of $p_1$ and $p_2$, we also write $p_3 = p_1 + (1 −a )p_2$
My question is, i did not understand what this definition means, and what does convex combination means intuitively? I appreciate any help. Thanks
$\endgroup$ 13 Answers
$\begingroup$The point $ap_1+(1-a)p_2$ can also be written as $p_2+a(p_1-p_2)$. Perhaps you recognize this as a parametric representation of a line through $p_2$ with direction vector $p_1-p_2$ (with $a$ as the parameter).
When $a=0$, $ap_1+(1-a)p_2=p_2$. And when $a=1$, $ap_1+(1-a)p_2=p_1$. So the points $ap_1+(1-a)p_2$ with $0\le a\le1$ make up the line segment between the two given points.
$\endgroup$ $\begingroup$It just means that you can get the point $p_3$ by simply adding the other points ($p_1$, $p_2$). But you don't want to just add them instead you'd like to give some sort of "weight" to each point.
Simply put, convex combination means weighted sum with the condition that the weights have to sum to 1.
In general, for a vector ($x_1, x_2, ...., x_n$), the convex combination is:
$\alpha_1 x_1 + \alpha_2 x_2 + \alpha_3 x_3+ ... \alpha_n x_n \hspace{2em}$
where $\hspace{0.5em} \alpha_i \ge 0 \hspace{0.5em} $ and $\hspace{0.5em} \alpha_1+ \alpha_2+ \alpha_3+ ... +\alpha_n = 1$
$\endgroup$ $\begingroup$A less abstract and more meaningful example of convex combination can be got from the real world, for example from the production of two types of goods by means of a single machine. The machine has to work two lots sharing the same productive period of time $T$ [$T$ is measured in working days]. Let be $t_1$ the time spent by machine for working the first item and $t_2$ the time spent by machine for working the second item:
$ T = t_1 + t_2 $
Two vectors $p_1$ and $p_2$ express the productivity of the machine as $p_i$ units of output of the i-th kind of product during one working day, while at the end of period T the total amount $q$ of the two items worked by the machine is:
$ q = t_1p_1 + t_2p_2$ where $t_1+t_2=T$
If we designate by ai the fraction of time period $T$ for which the machine is occupied with the i-th kind of output, we can define the intensity (level of activity) of the machine as $a_1 = t_1/T$ and $a_2=t_2/T$, so that $a_1 + a_2=1$.
As a result
$p = a_1p_1 + a_2p_2$ where $a_1 + a_2=1$
So, the convex combination $p$ designates the productivity of the machine as units of output worked during one period of time $T$ being $p=q/T$.
Now, we can image a vector space of n dimensions where every dimension stands for a different machine. In this way, a vector designates the n output performed by every single machine and m vectors represent m different kind of output performed by n machines. Again, the n machines share the same time of production and the total production is a convex combination.
$\endgroup$
