Equivalent minimum linear program

[gfd43tg]

Homework Statement

Suppose you are given the following affine minimization problem.

\begin{align*} \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^Tx+3c^Tc \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

Which of the following is an equivalent linear minimization problem?

\begin{align*} c^T \big( \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in} &x + 3c \big ) \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

\begin{align*} \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^T(x +3c)\\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

\begin{align*}3c^Tc+ \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^Tx \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

\begin{align*} \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^Tx \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

Homework Equations

The Attempt at a Solution

I guessed and was right, the answer is


\begin{align*}3c^Tc+ \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^Tx \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

However, I don't feel comfortable and it was more an educated guess, instead of firm understanding. I figured that $3c^Tc$ would not affect the minimum since it is just an additive, but how should I approach these sorts of problems? Why are the other choices incorrect?

 

[mighty2000]

To approach these types of problems, it is important to understand the properties of affine and linear functions. An affine function is a function that can be written as $f(x) = Ax + b$, where $A$ is a matrix and $b$ is a vector. A linear function is a special case of an affine function where $b = 0$.

In this problem, we are given an affine minimization problem, which means that the objective function can be written as $c^Tx + 3c^Tc$. We are looking for an equivalent linear minimization problem, which means that the objective function should only have a linear term, i.e. $c^Tx$.

Let's look at each of the given options and see why they are incorrect:

1. \begin{align*} c^T \big( \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in} &x + 3c \big ) \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

This option is incorrect because the objective function is not linear. The term $3c$ is not a constant and therefore cannot be pulled out of the minimization.

2. \begin{align*} \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^T(x +3c)\\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

This option is incorrect because the objective function is not linear. The term $x + 3c$ is not a linear term.

3. \begin{align*}3c^Tc+ \underset{x \in \mathbb{R}^3} \min \hspace{0.1 in}&c^Tx \\ &\text{subject to} \hspace{0.1 in} Ax \leq b \end{align*}

This option is incorrect because the objective function is not equivalent to the given affine minimization problem. The term $3c^Tc$ is a constant and does not affect the minimization.

Therefore, the correct option is \begin{align*} \underset{x \in \math