A6. Let f(x) =P    |xi | . Which of the following statements hold true:

a) f is di↵erentiable at x = 0 and its derivative is 0.

b) f  is not di↵erentiable at x  = 0 and its sub-gradient equals {x  : maxi |xi | 三 1}.

c) f is not di↵erentiable at x = 0 and its sub-gradient equals 0.

Section B: Bullet-Point Questions

B1.   Consider the optimization problem:

min   cTx

s.t.   aTx b  for all a e E = {¯(a) + Pu |  IuI2 1} ,

where c, ¯(a) e Rn , b e R, P e Rn 根n  with P 0. Determine if this problem

is a Linear Program.  If yes, provide an explanation why.  If not, explain why not.

B2.   Consider the optimization problem:

min   cTx

s.t.   aTx b  for all a e E = {¯(a) + Pu |  IuI2 1} ,

where c, ¯(a) e Rn , b e R, P e Rn 根n  with P = 0. Determine if this problem

is a Linear Program.  If yes, provide an explanation why.  If not, explain why not.

B3.   Consider the optimization problem:

min   x1 + x2 + x3

s.t.   x1 +4x2 2,

2x1 - x3                  > -2,

3x2 - x3                ≥ -4,

x1 , x2 , x3  ≥ 0.

Determine if this problem is a Linear Program.  If yes, provide an expla- nation why. If not, explain why not.

B4.   Consider a linear program of the form:

max   cTx

s.t.    Ax = b.

Reformulate this LP as an equivalent LP, where all decision variables are required to be non-negative.

B5.   State the definition for an optimization problem to be convex.  Moreover, give a simple example for both, (a) a convex optimization problem, and

(b) a non-convex optimization problem.

B6.   Given the integer linear program (ILP)

max   cTx

s.t.    Ax b,

x e Zn ,

where all entries of A and b are rational numbers.

State an linear program (LP), with the property that every optimal solu- tion to (ILP) is an optimal solution to (LP), and every optimal solution to (LP) that is an extreme point is an optimal solution to (ILP).

B7.    Consider the primal-dual pair of LP

max     (5, 3, 5)x

s.t.       0 3(1)        1(2)    2(−)1  1 x 0 4(2)      1

@ −1     1     1      A         @ −1  A

and

min     (2, 4, −1)y

s.t.       0  2(1)        1(3)     1(−)1  1 y =  0 3(5)  1 , y ≥ 0.

@ −1    2     1       A         @  5  A

Consider  ¯(x)a  =  (1, −1, 1)T ,  ¯(x)b  =  (1.5, −2, 0)T ,  ¯(x)c  =  (−1, 1, 0)T   and  y(¯) = (0, 2, 1)T .

a)    Check whether ¯(x)a , ¯(x)b  and  ¯(x)c  feasible  for the primal problem, and y(¯) feasible for the dual problem.

b)    Check the complementary slackness conditions for (¯(x)a , y(¯)), (¯(x)b , y(¯)) and (¯(x)c , y(¯)), respectively.

c)    Determine whether  (¯(x)a , y(¯)),  (¯(x)b , y(¯)) or  (¯(x)c , y(¯)) constitutes a pair of op- timal solutions for the given primal-dual pair of LP.

B8.    Define a set Q = {x = (x1 ... xn )>  : P xi(4) 1}.

a)  Is Q a convex set?

b)  What  is the minimax center of Q?

c)  How  many  solutions  does  the  following  optimization  problem  have: minf(x) =P xi s.t.  x 2 Q ?

d)  Where  is  the  minimal  point  of  f(x)  from  c)  attained,  within  the interior of Q or at the boundary of Q?

B9.    What  is  the gradient  descent method?  What is it used for?  Explain on an example in R1 .

B10.    Assume x 2 X , X is a convex subset of Rn  and fisa convex di↵erentiable function on Rn.  What is the necessary and sufficent condition for x 2 X to be aminimum point off (formulate in terms of the variational inequality)? Provide an example in R2 .

B11.    Define  a  local/global  maximum  of  a  function.   How  many  local  maxima does a concave function have?  Provide  an example of a concave function with  multiple  global  maxima.   Explain  how  to  select  a  particular  global maximum of a concave function by means of a regularisation.

B12.    Explain  with  a  simple  example  the  di↵erence  between  a  standard  linear program, robust linear program and a robust stochastic linear program.

Section C: Longer Questions

C1.  The director of the CO-Tech startup needs to decide what salaries too↵er its employees for the coming year. In order to keep the employees happy, she needs to satisfy the following constraints:

. Tom wants at least $20 000 or he will quit;

. Peter, Nina and Samir each want to be paid at least $5000 more than Tom;

.  Gary wants his salary to be at least as high as the combined salary of Tom and Peter;

. Linda wants her salary to be $200 more than Gary;

. the combined salary of Nina and Samir should be at least twice the combined salary of Tom and Peter;

.  Bob’s salary is at least as high as that of Peter and at least as high as that of Samir;

. the combined salary of Bob and Peter should be at least $60 000;

. Linda should not make more money than the combined salary of Bob and Tom.

a) Formulate as an LP that will determine the salaries for the employees of CO-Tech that satisfy each of the constraints while minimizing the total salary expenses.

b) Formulate as an LP that will determine the salaries for the employees of CO-Tech that satisfy each of the constraints while minimizing the salary of the highest paid employee.