4
$\begingroup$

I have just begun to study linear optimization problems.
I understand that linear optimization solves for minimum or maximum of a cost function, subject to different restraints.

1) How is it that we are able to give a min/max solution even when the number of variables is lesser than number of equations (I realize we are not solving it but calculating an optimum value) - I don't need a proof, an intuitive answer will do if that's easier.

2) Why do we require the number of equations being equal to the number of variables in the first place - To solve for them exactly?

3) How can I know by looking at a linear optimization problem if it is going to be unbounded/infeasible/feasible?()

$\endgroup$
1
  • 1
    $\begingroup$ In practical implementations the number of structural + logical variables is always exceeding the number of rows. Say we have $n$ structural variables and $m$ rows then the total number of variables is $n+m$ after we added $m$ slacks. $\endgroup$ Sep 26, 2016 at 6:43

1 Answer 1

5
$\begingroup$

Lets clarify a few things about linear optimization (linear programming) and solving a linear system.

  • In a linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, we want to find a solution to a set of linear equations. Indeed, to have a unique solutions, we need the number of equations to be equal to the number of variables. Intuitively, if the number of equations is smaller than the number of variables, then you have some "degrees of freedom" (we can change the values of the variables and still get a valid solution), which in turn implies you can have multiple solutions. But note that this is not always the case. It is possible to have fewer equations than variables and have an infeasible system (when $\mathbf{b}\neq \mathbf{0}$). Similarly, we could have more equations than variables, but if the equations are "redundant" (for example one constraint is a multiple of another), then we could still have either a unique solution, or many solutions or even no solutions. In summary, whether a solution exists and whether it is unique depends on the form of $\mathbf{A}$ and $\mathbf{b}$ and not only the number of constraints.

  • In a linear optimization problem, you are given a set of linear inequalities and you are asked to find a feasible point, i.e., a point that satisfies all those inequalities. Typically, you will also be given a linear function and you will want to find a point that is feasible and also maximizes that function. In standard form, this would be something like $$ \max_{\mathbf{x}}f(\mathbf{x}) = \mathbf{c}^{\top}\mathbf{x} \quad \text{subject to} \quad \mathbf{A}\mathbf{x}=\mathbf{b},\quad \mathbf{x}\ge \mathbf{0}. $$

1) Consider a simple example on two variables: $\max_{x} (2x+2y)$ subject to $x+y\le 1$.

First, we ask ourselves whether the system is feasible. For this, we completely ignore the objective function, focus only on the constraints and ask whether there are any points at all that satisfy these constraints. In this example, the answer is yes. There are infinitely many points (e.g., $(-1, 1)$, $(0.5, 0.5)$, $(0.3, 0.7)$).

Now that we have established that the system is feasible, then we know that it also has an optimal solution. Some achieve a sub-optimal solution (e.g., $(-1, 1)$), while there are several points that achieve the optimal solution (e.g., $(0.5, 0.5)$). The intuition here is the following. Each feasible points achieves a certain objective value. Here, it happens that the objective function $f(x)=2x+2y$ grows in both $x$ and $y$, so increasing $x$ and $y$ achieves higher value. But the inequality constraint puts a restriction on how much they can both grow: if $x$ grows too much, then $y$ has to become smaller to satisfy the constraint and works as a barrier on how much we can increase the function. In this case, you can easily see that the optimal objective value is equal to $2$ and it is achieved by points right on that barrier.

Note I: in the above example, the feasible region was unbounded: we can make $x$ and $y$ infinitely negative and still satisfy the constraints. Yet, the optimal value of the optimization problem is bounded. In principle, if the constraints were different, the optimal solution could be unbounded as well. But if the feasible region is bounded, then the optimal value will always be bounded. (More formally, we say that if the constraints form a polytope, i.e., a bounded polyhedron, then the optimal solution will be bounded. And in fact, there are many more interesting things we can say about that case.)

Note II: There is a distinction between the optimal value and the optimal solution/point. The optimal value will be unique (either unbounded or bounded). But in general it can be achieved by many points.

2) (See the introductory remark on linear systems.)

3) Deciding whether a linear optimization problem is feasible is actually as hard as maximizing the objective over the constraints. In other words, to decide whether a set of linear inequalities is feasible, we must "solve the linear program" e.g. using an algorithm (or software implementing such an algorithm). The same algorithm will tell you if your program has a bounded solution or unbounded. Of course, there are also mathematical conditions that can help you determine whether a given system will be bounded or unbounded.

$\endgroup$
3
  • $\begingroup$ The question was why and not how. $\endgroup$
    – novice
    Sep 25, 2016 at 21:39
  • 1
    $\begingroup$ On question number 1 I try to answer "why" with an example that you can draw to get some "(geometric) intuition". On question number 2, my comment is also on "why" and not how. Question 3 was asking "how". Which part would like more clarification on? $\endgroup$
    – megas
    Sep 25, 2016 at 21:44
  • $\begingroup$ Sorry, let me read it extensively and get back to yiu $\endgroup$
    – novice
    Sep 25, 2016 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .