I have a very simple linear problem: <mtable columnalign="right left" rowspacing="3pt" column

Question

I have a very simple linear problem:

\begin{aligned} min_{x} & x^{2} \\ s.t. & a_{1} x_{1} + a_{2} x_{2} = b \end{aligned}

Suppose I want to write this problem equivalently as in Find the equivalent linear program. Unlike the problem in the link, I have equality. Can I write it equivalently as:

\begin{aligned} min_{x, α, β} & x^{2} \\ s.t. & a_{1} x_{1} = α b, a_{2} x_{2} = β b, α + β = 1. \end{aligned}

The converse is intuitive: Given

{x, α, β}

feasible for the second problem, adding the first and second constraints gives the constraint of the first problem. But the forward part is not clear, especially because I have never seen an equality constraint written like this. Any help would be highly appreciated.

Answer 1

You are correct. Suppose

x

is feasible. Then

a_{1} x_{1} + a_{2} x_{2} = b ⟺ (a_{1} x_{1} + a_{2} x_{2} = (α + β) b and α + β = 1)

. Therefore any solution satisfying the latter conditions is also feasible.

A simple example to explain what I think is the part you are unclear about is the following. Look at the following two problems:
1.

\begin{aligned} min_{x} & x \\ s.t. & x \geq 2 \\ x \in R \end{aligned}

2.

\begin{aligned} min_{x} & x \\ s.t. & x \geq 2 \\ x \geq 1 \\ x \in R \end{aligned}

They obviously generate the same feasible solution; the constraint added is weaker than the existing constraint. Similarly the following problem also generates the same feasible solution:

\begin{aligned} min_{x, a} & x \\ s.t. & x \geq a \\ a = 2 \\ x \in R \end{aligned}

I have a very simple linear problem: <mtable columnalign="right left" rowspacing="3pt" column

Answers (1)

Not exactly what you’re looking for?

You might be interested in

New questions