Intereting Posts

Show $z^4 + e^z = 0$ has a solution in $\{z \in \mathbb{C} : |z| \leq 2\}$
Eliminating Repeat Numbers from a Hat
Is my proof correct? ($A_n$ is generated by the set of all 3-cycles for $n \geq 3$)
Can a free group over a set be constructed this way (without equivalence classes of words)?
Application of Pumping lemma for regular languages
Field and Algebra
Growth estimate of an entire function
What mistakes, if any, were made in Numberphile's proof that $1+2+3+\cdots=-1/12$?
Concise proof that every common divisor divides GCD without Bezout's identity?
We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?
Prove that the operator norm is a norm
For $f \in L^1(\mathbb{R})$ and $y > 0$, we have ${1\over{\sqrt{y}}} \int_\mathbb{R} f(x – t)e^{{-\pi t^2}\over{y}}dt \in L^1(\mathbb{R})$?
Explanation of Maclaurin Series of $x^\pi$
Continuity on a union
Starting digits of $2^n$.

Given a problem:

Find the dual:

$$

Primal =\begin{Bmatrix}

max \ \ \ \ 5x_1 – 6x_2 \\

s.t. \ \ \ \ 2x_1 -x_2 = 1\\

\ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\

\ \ \ \ x_1 \geq 0\\

\end{Bmatrix}

$$

- How to find out whether linear programming problem is infeasible using simplex algorithm
- Degeneracy in Linear Programming
- Converting absolute value program into linear program
- Optimum solution to a Linear programming problem
- Linear Programming Books
- Linear Programming 3 decision variables (past exam paper question)

i) Introduce a slack variable ($+x_3$) into the 2nd constraint

$$

Primal =\begin{Bmatrix}

max \ \ \ \ 5x_1 – 6x_2 \\

s.t. \quad \quad2x_1 -x_2 \quad \quad \quad \quad \ = 1\\

\quad \quad \quad \quad x_1 +3x_2 + x_3 \quad \quad =9\\

\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_1 \geq 0\\

\end{Bmatrix}

$$

iii) Problem becomes a minimization problem with $\geq$ constraints

iv) Multiply the constraints by $y_1,y_2$

$$

Dual =\begin{Bmatrix}

min \ \ \ \ y_1 + 9y_2 \\

s.t. \ \ \ \ 2y_1 + y_2 \geq5\\

\quad \quad \quad \quad \quad-y_2+3y_2 \geq -6\\

\quad \quad \quad y_2 \geq 0\\

\end{Bmatrix}

$$

v) Change sign from $(-)$ to $(+)$ in second constraint

$$

Dual =\begin{Bmatrix}

min \ \ \ \ y_1 + 9y_2 \\

s.t. \ \ \ \ 2y_1 + y_2 \geq5\\

\quad \quad \quad \quad \quad y_2-3y_2 \leq 6\\

\quad \quad \quad y_2 \geq 0\\

\end{Bmatrix}

$$

Is this correct or am I missing something?

Thanks

- Quadratic optimisation with quadratic equality constraints
- Vector placement for optimal projections
- Is there a “simple” proof of the isoperimetric theorem for squares?
- Minimize Frobenius norm with unitary constraint
- Degeneracy in Linear Programming
- Arnol'd's trivium problem #68
- What is the derivative of this?
- How find this minimum $\sum_{i=1}^{n}a^2_{i}-2\sum_{i=1}^{n}a_{i}a_{i+1},a_{n+1}=a_{1}$
- Multiple solutions for both primal and dual
- Calculus of variations, what is a functional

Maybe it’s worthwhile to talk through where the dual comes from. This will take a while, but hopefully the dual won’t seem so mysterious when we’re done.

Suppose we want to use the primal’s constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by $9$, the second constraint by $1$, and add them together, we get $9(2x_1 – x_2) + 1(x_1 +3 x_2)$ for the left-hand side and $9(1) + 1(9)$ for the right-hand side. Since the first constraint is an equality and the second is an inequality, this implies $$19x_1 – 6x_2 \leq 18.$$

But since $x_1 \geq 0$, it’s also true that $5x_1 \leq 19x_1$, and so $$5x_1 – 6x_2 \leq 19x_1 – 6x_2 \leq 18.$$

Therefore, $18$ is an upper-bound on the optimal value of the primal problem.

Surely we can do better than that, though. Instead of just guessing $9$ and $1$ as the multipliers, let’s let them be variables. Thus we’re looking for multipliers $y_1$ and $y_2$ to force $$5x_1 – 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$? Let’s take the two inequalities one at a time.

**The first inequality**: $5x_1 – 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

We have to track the coefficients of the $x_1$ and $x_2$ variables separately. First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$. Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$. Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.

On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$. Since $x_2$ could be positive, we can’t go lower than $-6$, and since $x_2$ could be negative, we can’t go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality). So for the first inequality to work for the $x_2$ variable, we’ve got to have $-y_1 + 3y_2 = -6$.

Here we have to track the $y_1$ and $y_2$ variables separately. The $y_1$ variables come from the first constraint, which is an equality constraint. It doesn’t matter if $y_1$ is positive or negative, the equality constraint still holds. Thus $y_1$ is unrestricted in sign. However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can’t let that happen. So the $y_2$ variable can’t be negative. Thus we must have $y_2 \geq 0$.

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize $y_1 + 9y_2$.

Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal’s constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:

$$\begin{align*}

\text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\

\text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\

-y_1 + 3y_2& = -6\\

y_2 & \geq 0.

\end{align*}$$

And that’s the dual.

It’s probably worth summarizing the implications of this argument for all possible forms of the primal and dual. The following table is taken from p. 214 of

```
Primal Problem Dual Problem
(or Dual Problem) (or Primal Problem)
Maximization Minimization
Sensible <= constraint paired with nonnegative variable
Odd = constraint paired with unconstrained variable
Bizarre >= constraint paired with nonpositive variable
Sensible nonnegative variable paired with >= constraint
Odd unconstrained variable paired with = constraint
Bizarre nonpositive variable paired with <= constraint
```

- Example of a linear operator on some vector space with more than one right inverse.
- Spectrum of symmetric, non-selfadjoint operator on Hilbert space
- Optimising closest approach with third order motion
- Legendre symbol: Showing that $\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0$
- Horse and snail problem.
- Existence of a prime with some additional properties
- $(\sin^{-1} x)+ (\cos^{-1} x)^3$
- Does every power of $2$ of the form $2^{6+10x}$, $x\in\mathbb{N}$, have $6$ as one of its digits?
- Is an integral always continuous?
- Conditional Probability and Division by Zero
- If $x_n \to a$ and $x'_n \to a$, then $\{x_1, x'_1, x_2, x'_2, …\} \to a$
- Why do zeta regularization and path integrals agree on functional determinants?
- Verifying Touchard's Identity
- Where is the “relation” here?
- Suppose $a \in \mathbb{R}$, and $\exists n \in \mathbb{N}$, that $a^n \in \mathbb{Q}$, and $(a + 1)^n \in \mathbb{Q}$