0
$\begingroup$

I'm currently studying convex optimization using the textbook written by Boyd. I came across an example where the author demonstrates how an equivalent way to express affine sets is that they are a solution set for a system of linear equations.

The example given in the book is in two variables (i.e. $x_1$ and $x_2$). I was attempting to prove this using the same method used by the author, but this time in $k$ variables. I'm not sure if my approach is correct, however as it seems a bit naive and was hoping to get some feedback on it.

My Approach:

Suppose that $C = \{x\ |\ Ax = b\}$, $x_1, \cdots , x_k \in C$, and $\theta_1, \cdots , \theta_k \in \Bbb{R}$ with $\sum_{i = 1}^k \theta_i = 1$. Since each $x_i$ is in $C$, we can say that $Ax_k = b$. We want to show that $A(\theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_k x_k) = b$.

We could rewrite the last equation as

$$A(\theta_1 x_1 + (1 - \theta_1)(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1} x_k))$$

which is

$$\theta_1 Ax_1 + (1 - \theta_1)A(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1}x_k)$$

We can conclude that $A(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1}x_k) \in C$ because each $x_i$ is in $C$ and the coefficients are greater than $0$ and sum up to $1$. Thus, $A(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1}x_k) = b$.

If we put these values into the previous equation we get

$$\theta_1 Ax_1 + (1 - \theta_1)A(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1}x_k) = \theta_1 b + (1 - \theta_1)b = b$$

Thus we can conclude that this set is affine.

Is my approach correct? I'm not sure if the conclusion I drew that $A(\frac{\theta_2}{1 - \theta_1}x_2 + \cdots + \frac{\theta_k}{1 - \theta_1}x_k) = b$ is acceptable or not.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ You are using mathematical induction, so I suggest that you mention that explicitly at an appropriate place in the proof. But let me give you a hint for what could be a simpler proof: In $A(\theta_1 x_1 + \cdots \theta_k x_k)$, All the $\theta_i$ are scalars, and each $x_i \in C$. So how can you rewrite this expression using the former, and what can you conclude from the latter (look at the definition of $C$ again if it helps)? $\endgroup$ – M. Vinay Apr 2 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.