0
$\begingroup$

I am studying linear optimization and want to understand the basic general forms. Consider this problem for $A \in \mathbb{R}^{n \times m}$:

\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx.\end{array}

From linear algebra I know there are three cases to solve $Ax=b$:

  1. if $\mathrm{rank}(A)<\mathrm{rank}([A\quad b])$, which is like putting to many equations that cannot be solved simultaneously, thus in this case no solution.

\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx=+\infty.\end{array}

  1. if $\mathrm{rank}(A)=\mathrm{rank}([A\quad b])=m$, which means the number of variables is equal to number of equations and this equations are independent, thus there exists only one unique $x=(A^*A)^{-1}A^*b$.

\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx=c^T(A^*A)^{-1}A^*b.\end{array}

  1. if $\mathrm{rank}(A)=\mathrm{rank}([A\quad b])<m$, which means the number of variables is greater then number of equations, thus we have a freedom to choose many variations of $x$ to solve $Ax=b$. Many solutions $x$ exists.

Now, among these $x$, I need to find the one that minimizes $c^Tx$. I remember from linear algebra class, that among these $x$, there is one that minimizes $||x||_2^2$ is $x=A^*(AA^*)^{-1}b$. Is it the one that I need to minimize $c^Tx$? How I can show it?

$\endgroup$
  • 1
    $\begingroup$ I am quite scared of your notation $A \in \mathbb{F}^{n \times m}$, what does this mean? I do not think this notation should be in a linear program as you are defining. $\endgroup$ – Michael Sep 20 '19 at 4:37
  • 2
    $\begingroup$ @Michael maybe I better change it to real numbers $\endgroup$ – Lee Sep 20 '19 at 4:39
  • 1
    $\begingroup$ Unless I am missing something, case 1 and case 3 are defined by the same condition. $\endgroup$ – Arin Chaudhuri Sep 20 '19 at 4:40
  • 1
    $\begingroup$ One way to think about it is that $Ax=b$ has general solution $x=x^*+My$ where $x^*$ is a particular solution (assuming one exists) and $M$ is a matrix with columns that form a basis for $Null(A)$, $y$ is any vector in $\mathbb{R}^k$ (where $k$ is the dimension of $Null(A)$). $\endgroup$ – Michael Sep 20 '19 at 4:45
  • $\begingroup$ @ArinChaudhuri thanks, I did mistake there $\endgroup$ – Lee Sep 20 '19 at 4:45
1
$\begingroup$

If $Ax = b$ has multiple solutions then let $x_0$ be any solution.

A general solution is given by $x = x_0 + n$ where is $n$ is an arbitrary vector in the null space of $A$.

If there is a vector $n$ in the null space of $A$ such that $c^T n \neq 0$, assuming without loss of generality $ c^T n > 0$, then $x_0 - t n_0$ is a solution of $Ax = b$ for every real $t > 0$ and letting $t \to \infty$ we see that the value of the objective function tends to $-\infty$ , and so the minimum is clearly not attained.

In case $c^T n = 0$ for every $n$ in the null space of $A$ (in this case $c$ is in the row space of $A$) then clearly objective function takes only one value over the permissible set of values which will be the minimum.

$\endgroup$
  • $\begingroup$ thanks! I got the logic. $\endgroup$ – Lee Sep 20 '19 at 5:12
  • $\begingroup$ one question, if we change $Ax=b$ to $Ax\leq b$, the above still must hold since for the convex problem, the optimal $x$ is in the boundary of the constraint, i.e. $Ax=b$. Is it correct? $\endgroup$ – Lee Sep 20 '19 at 5:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.