homework 1

Question 1

Lagrangian Form of LP

Answer 1

L(x,y,s) = c^T x + y^T (b-Ax) -s^Tx

where problem is min c^Tx = b
such that Ax = b

Question 2

Dual function (min and max)

Answer 2

(minimisation of Lagrangian)

g(y,s) = min L(x,y,s)
= min c^T x + y^T (b-Ax) -s^Tx
= min c^T x + y^Tb-Axy^T -s^Tx
= min x^T(c-A^Ty - s) + b^T y

=( b^Ty, if c - A^Ty - s = 0
<
( - infinity, if c - A^Ty - s =/ 0 (positive infinity if max function)_

maximisation
g(y,s) = max L(x,y,s)
=max(c-y^T A)x + y^Tb =
=( y^Tb, if c - A^Ty - s = 0
<
( infinity, if c - A^Ty - s =/ 0 (positive infinity if max function)_

Question 3

dual problem

Answer 3

max b^Ty
s.t c-A^Ty >= 0
y E R^m

Question 4

How to put LP into standard form

Answer 4

1) should look like:
min c^Tx
ax = b
x>= 0
2) add slack variables to inequalities and make sure all numbers are onthe same side and variables on other side
3) rewrite all variables (but slack) so like y = y1-y2 to get rid of all negatives
4) sub back into lpp
write in forms wanted :)

Question 5

standard form

Answer 5

min c^Tx
ax = b
x>= 0

Question 6

solving basic llp

Answer 6

1) put into form
2) plot and see all max/min points (points where lines meet in feasible region
3) find all these points values
4) see which is min/max

Question 7

Formulate the following optimisation problem as a linear programming
problem.
max x1 +x 2
𝑠𝑠.𝑡𝑡. || x||1^2≤ 4, x ∈ ℝ^2

Answer 7

max x1 + x2
s.t {-z1<x1<z1
(-z2<x2<z2
(z1 + z2 = 2

Question 8

turning max into min problem

Answer 8

put minus on whole problem

Question 9

turing min c^Tx s.t Ax <= b, x E R^n into min cTx s.t Ax = b x >= 0

Answer 9

1) x = (1,-1)^T = (y-z) = (1,0)^T - (0,1)^T
2) put into vectors of z = (y,z)
3) add slack varible of 1 to make no longer <= b
4) y,z,s >= 0

Question 10

what is ||x||1 equal to

Answer 10

|x1| +|x2| + … + |xn|

Question 11

Farkas’ lemma

Answer 11

let A E R^m,n b E R^m. Then exactly one is true:
1. There exists x >= 0 such that Ax = b
2. There exists y such that y^T A <= 0 ANS Y^t > 0