Exercise 2 - LP and KKT Conditions

Problem 1 (30%) The Mean Value Theorem

a) Example A.2: page=650

---

Mean Value Theorem

For a function $f:{\mathbb{R}}^n\to \mathbb{R}$, and any vector $p$ we have

$$f(x+p)=f(x)+\nabla f(x+\alpha p{)}^{T}p$$

for some $\alpha \in (0,1)$.

Link to original

We have $f(x)=x_1^3+3x_1{x}_2^2$, where $x=[0,0{]}^T$ and $p=[2,1{]}^T$. It is then easy to verify that $f(x)=0$ and $f(x+p)=14$.

We then find the Gradient of $f(x+\alpha p)$

$$\nabla f(x+\alpha p)=\left[\begin{array}{c}3(x_1+\alpha p_1{)}^2+3(x_2+\alpha p_2{)}^2\\ 6(x_1+\alpha p_1)(x_2+\alpha p_2)\end{array}\right]{|}_{x=[0,0{]}^T,p=[2,1{]}^T}=\left[\begin{array}{c}15{\alpha }^2\\ 12{\alpha }^2\end{array}\right]$$

Which allows us to calculate

$$\nabla f(x+\alpha p{)}^{T}p=42{\alpha }^2$$

We can then calculate the Mean Value Theorem

$$\begin{array}{rl}f(x+p)& =f(x)+\nabla f(x+\alpha p{)}^{T}p\\ 14& =0+42{\alpha }^2\end{array}$$

Giving us $\alpha =\frac{\sqrt{3}}{3}$ which is in the range $(0,1)$.

b) Lipschitz Continuity Given $f(x)=x^{1/2}$, its derivative is equal to $\frac{d}{dx}f(x)=\frac{1}{2\sqrt{x}}$.

From the definition of Lipschitz Continuity

Link to original

We see that $||f^{\prime }(x)||\stackrel{x\to 0}{\to }\infty$. This means that there exists no constant Lipschitz constant, $L$, such that

$$||f^{\prime }(x)||=\frac{||f(x_1)-f(x_0)||}{||x_1-x_0||}\le L$$

In a small small neighborhood around $x=0$.

Therefore, $f(x)$ is not Lipschitz continuous.

Problem 2 (25%) LP and KKT-conditions (Exam August 2000)

Given the following LP in standard form

Link to original

Where $c\in {\mathbb{R}}^n$ and $b\in {\mathbb{R}}^m$

We can derive the KKT (Karush–Kuhn–Tucker) Conditions conditions

Link to original

Stationary First we find the Lagrangian

$$\mathcal{L}(x,\lambda )=c^{T}x-{\lambda }^T(Ax-b)-s^{T}x$$

Where $\lambda$ is the multiplier for the equality constraint, and $s$ is the multiplier for the inequality constraint. We then find the gradient of the Lagrangian when it is equal to zero

$${\nabla }_x\mathcal{L}(x^{\ast },{\lambda }^{\ast })=c-A^T{\lambda }^{\ast }-s^{\ast }=0$$

Which we can write as

$$c=A^T{\lambda }^{\ast }+s^{\ast }$$

Primal Feasibility

$$\begin{array}{rl}A{x}^{\ast }& =b\\ x^{\ast }& \ge 0\end{array}$$

Dual Feasibility

$$s^{\ast }\ge 0$$

Complementary Condition

$$s_i^{\ast }{x}_i^{\ast }=0,i=1,2,\dots ,n-1,n$$

Problem 3 (45%) Linear Programming

$$\begin{array}{rl}R(x_1)& :\text{100 NOK per tonne}\\ S(x_2)& :\text{75 NOK per tonne}\\ T(x_3)& :\text{55 NOK per tonne}\end{array}$$

Standard form for LP problem is

Link to original

a) We want to maximize profit

$$\underset{x\in {\mathbb{R}}^n}{\max }100x_1+75x_2+55x_3$$

And can rewrite this into a minimization problem

$$\underset{x\in {\mathbb{R}}^n}{\min }-100x_1-75x_2-55x_3$$

With the following constraints

$$\begin{array}{rl}{c}_1(x)& =3x_1+2x_2+x_3-7200\\ c_2(x)& =2x_1+2x_2+3x_3-6000\end{array}$$

And naturally $x\ge 0$, as we can’t produce “negative” product.

This gives us the following matrices we can use in the standard form for a LP problem

$$\begin{array}{rl}{c}^T& =\left[\begin{array}{ccc}-100& -75& -55\end{array}\right]\\ A& =\left[\begin{array}{ccc}3& 2& 1\\ 2& 2& 3\end{array}\right]\\ b& =\left[\begin{array}{c}7200\\ 6000\end{array}\right]\end{array}$$

b) Basic Feasible Point (BFP) We have two rows ($n=2$) and three columns ($m=3$) in $A$. The index set is therefore $\{1,2,3\}$, and the basis contains $m=2$ indices.

The idea for finding a basic feasible point is trying to optimize for n variables (setting the rest to zero), and solving the resulting equation set.

We have that $B=[A_i{]}_{i\in \mathcal{B}}$

1. $\mathcal{B}=\{2,3\}$, which is the same as setting $x_1=0$ This gives $B=\left[\begin{array}{cc}2& 1\\ 2& 3\end{array}\right]$, and it follows that

$$\begin{array}{rl}Bx& =b\\ \left[\begin{array}{cc}2& 1\\ 2& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]& =\left[\begin{array}{c}7200\\ 6000\end{array}\right]\end{array}$$

Which gives us $x=[0,3900,-600{]}^T$.

2. $\mathcal{B}=\{1,3\}$, which is the same as setting $x_2=0$ This gives $B=\left[\begin{array}{cc}3& 1\\ 2& 3\end{array}\right]$, and solved similarly we get $x=\left[\frac{15600}{7},0,\frac{3600}{7}\right]$.

3. $\mathcal{B}=\{1,2\}$, which is the same as setting $x_3=0$ This gives us $B=\left[\begin{array}{cc}3& 2\\ 2& 2\end{array}\right]$, and solved similarly we get $x=[1200,1800,0{]}^T$.

Setting $x_1=0$ gives us an infeasible point, since $x_3<0$, while the points we get setting $x_2=0$ and $x_3=0$ gives us basic feasible points.

c) We remember the KKT (Karush–Kuhn–Tucker) Conditions

Link to original

We start by checking the point $x=\left[\frac{15600}{7},0,\frac{3600}{7}\right]$. We can skip a few steps of calculations by using information found in problem 2

From the complementary condition we have

$$s_i^{\ast }{x}_i=0$$

Giving us $s=[0,s_2,0{]}^T$

From the stationary condition we have

$$\begin{array}{rl}c& =A^T{\lambda }^{\ast }+s^{\ast }\\ -\left[\begin{array}{c}100\\ 75\\ 55\end{array}\right]& =\left[\begin{array}{cc}3& 2\\ 2& 2\\ 1& 3\end{array}\right]\left[\begin{array}{c}{\lambda }_1\\ {\lambda }_2\end{array}\right]+\left[\begin{array}{c}0\\ s_2\\ 0\end{array}\right]\end{array}$$

Solving this in WolframAlpha gives us

$$\begin{array}{rl}\lambda & =-\frac{1}{7}\left[\begin{array}{c}190\\ 65\end{array}\right]\\ s_2& =-\frac{15}{7}\end{array}$$

Since $s_2<0$, dual feasibility is not fulfilled, and KKT do not hold. This point is therefore not the solution.

We then check the point $x=[1200,1800,0{]}^T$ similarly. This gives $s=[0,0,s_3{]}^T$, and the stationary condition gives us

$$\begin{array}{rl}c& =A^T{\lambda }^{\ast }+s^{\ast }\\ -\left[\begin{array}{c}100\\ 75\\ 55\end{array}\right]& =\left[\begin{array}{cc}3& 2\\ 2& 2\\ 1& 3\end{array}\right]\left[\begin{array}{c}{\lambda }_1\\ {\lambda }_2\end{array}\right]+\left[\begin{array}{c}0\\ 0\\ s_3\end{array}\right]\end{array}$$

Giving us

$$\begin{array}{rl}\lambda & =-\left[\begin{array}{c}25\\ 12.5\end{array}\right]\\ s& =\left[\begin{array}{c}0\\ 0\\ 7.5\end{array}\right]\end{array}$$

Since $s\ge 0$, the dual feasibility condition is satisfied, and all KKT conditions holds.

Solution

The solution to the problem is therefore $x^{\ast }=[1200,1800,0{]}^T$, and the function value at this point is $f(x^{\ast })=c^T{x}^{\ast }=-255,000$. For the original problem, this means a profit of $255,000$ (since we made this into a minimization problem instead of the maximization problem originally given)

d) The Dual LP Problem The given LP problem is already on standard form, therefore the dual problem is given by (same $b$, $c$, $A$, and $\lambda$)

Link to original

where ${\lambda }^{\ast }=-[25,12.5{]}^T$ and $b^T{\lambda }^{\ast }=-255,000$.

e)

Using the first KKT condition

$$1.c=A^T{\lambda }^{\ast }+s^{\ast }$$

The equality constraint at $x=x^{\ast }$

$$2.A{x}^{\ast }=b$$

And the last condition

$$3.s^{\ast T}{x}^{\ast }=0$$

---

From equation 1

c^Tx^* &= (A^T\lambda^*+s^*)^Tx^* \\ &=\lambda^{*T}Ax^*+s ^{*T}x^* \\ &=\lambda^{*T}b+0 \\ &=b^T\lambda^*, \;\;\; \text{Q.E.D} \end{align}

The last line is legal since it will be the same scalar operations

f) Sensitivity

Sensitivity

Given

Link to original

Where we do a small perturbation in $b_i:{\tilde{b}}_i=b_i+ϵ$, then the new solution fulfills

$$c^T{x}_{new}^{\ast }=c^T{x}^{\ast }\pm ϵ{\lambda }_i^{\ast }$$

Where $x^{\ast }$ and ${\lambda }^{\ast }$ are optimal solution and corresponding Lagrangian.

Link to original

The multiplier for $A$ is ${\lambda }_1^{\ast }=-25$, and the multiplier for $B$ is ${\lambda }_2^{\ast }=-12.5$. Since $|{\lambda }_1^{\ast }|>|{\lambda }_2^{\ast }|$. We will therefore see a bigger increase by increasing the capacity of $A$ compared to $B$.

Using the linprog function in Matlab (similar to Matlab Assignment 1) gives the following values for different $b$

$$\begin{array}{rl}b& =[7201,6000{]}^T\to f(x^{\ast })=255,025\\ b& =[7200,6001{]}^T\to f(x^{\ast })=255,012.5\end{array}$$

Which confirms the theory.