2
$\begingroup$

Consider the problem $$\max f(x)=-3x_1+2x_2$$ subject to $$2x_1-x_2\geq -2\\ x_1-2x_2\leq 3\\ x_1+2x_2\leq 11\\ x_1\geq 0\\ x_2\geq 0 $$

If one let $$A=\left[\begin{array}{cc} -2 & 2\\ 1 & -2\\ 1 & 2\\ -1 & 0\\ 0 & -1 \end{array}\right], \quad b=\left[\begin{array}{c} -2\\ -3\\ -11\\ 0\\ 0 \end{array}\right],$$ the feasible points may be rewritten as $Ax+b\leq 0$.

The solution of this problem presented says that, using the Farkas' Lemma, the necessary and sufficient conditions to optimality are $$A^ty=\left[\begin{array}{c} -3\\ 2 \end{array}\right]$$ with $y\in\mathbb{R}^5$, feasibility $Ax\leq -b$ and complementarity (what is this?) $\langle Ax+b,y\rangle=0$.

Somehow I think that it is related to the dual problem (which is not clear to me what is it) and and don't understand it.

$\endgroup$
3
  • $\begingroup$ It is not clear what you are asking. $\endgroup$ Commented Jul 4 at 18:48
  • $\begingroup$ This looks like a duality result with $y$ being the vector of dual variables. I think you would also need $y\geq 0$. The complementarity condition is also called "complementary slackness." $\endgroup$ Commented Jul 4 at 20:31
  • $\begingroup$ @copper.hat, i don't understan why these are the conditions. Why $A^ty=c$ and $(Ax+b)^Ty=0$ $\endgroup$ Commented Jul 4 at 20:45

1 Answer 1

3
$\begingroup$

It looks like you also need the dual feasibility condition: $$\boxed{y\geq 0}$$


The primal problem is:

Minimize: $c^{\top}x$

Subject to: $Ax+b\leq 0; x \in \mathbb{R}^n$


where $c=(3;-2)$ in your specific case.


Given a vector $y\geq 0$, the corresponding unconstrained problem is:

Minimize: $c^{\top}x + y^{\top}(Ax+b)$

Subject to: $x \in \mathbb{R}^n$


You can define the dual function $d(y)$ for $y\geq 0$ as the optimal objective of the unconstrained problem:

\begin{align} d(y) &= \inf_{x \in \mathbb{R}^n} [c^{\top}x + y^{\top}(Ax+b)]\\ &= \left\{\begin{array}{cc} y^{\top}b & \mbox{ if $c^{\top} + y^{\top}A=0$} \\ -\infty & \mbox{ else} \end{array}\right. \end{align} where you can argue the answer is indeed $-\infty$ if any component of the vector $c^{\top}+y^{\top}A$ is nonzero (why?). One approach is to maximize the dual function $d(y)$ over all $y\geq 0$, which (to avoid $-\infty$) certainly requires $y$ to be chosen so that: $$\boxed{c^{\top}+y^{\top}A=0}$$ which is the same as the condition $A^{\top}y=-c=(-3, 2)$.

The feasibility condition is: $$ \boxed{Ax+b\leq 0} $$ The complementary slackness condition requires $y_i=0$ whenever the corresponding $i$th entry of $Ax + b$ is strictly less than zero, which means we need $$ \boxed{y^{\top}(Ax+b)=0}$$


Here is a simple way to show that if you have vectors $x,y$ that satisfy the above four boxed conditions (including the equation $y\geq 0$) then $x$ must be an optimal solution to the primal: Since $y$ is a nonnegative vector that satsifies $c^{\top}+y^{\top}A=0$, every $x \in \mathbb{R}^n$ minimizes the corresponding unconstrained problem (for that particular $y$). Thus, the conditions of Theorem III.1 here hold (page 14)

https://ee.usc.edu/stochastic-nets/docs/network-optimization-notes.pdf

which means $x$ solves the primal problem.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.