Section A: Short Questions

A1. Is the LP given by

max   x1 + x2 — x4

s.t.    x1  +3x3    5,  x1 +3x2  ≥ 3, x1  — 2x4    4, x1 , x2 , x3 , x4  ≥ 0,

a)   infeasible, or

b)   unbounded, or

c)   has an optimal solution ?

A2.  Consider an integer-linear program (P) and its standard LP relaxation

(P(˜)). Assume we know that (P(˜)) has an optimal solution x.  Then x is an

optimal solution of (P) if

a)   x is feasible for P, or

b)   P is unbounded, or

c)   x is infeasible for P?

A3. Let (P) and (D) a primal-dual pair of LP. Assume we know that (D) is bounded and has optimal value d* . Let p*  be an optimal value of (P). Is

a)  p*  = d* , or

b)  p*  > d* , or

c)  p*  < d*  ?

A4. Let f(x) be a function of real variable x e R.  Which of the following statements holds true:

a)  f is linear if and only iff(y) — f(x) >  (x)(y — x), Ax, y e R b)  f is convex if and only if  = 0 for every x e R.

c)  f is convex if and only if the set {(x, t) : t ≥ f(x)} is convex.

A5. Let f(x) be a function of a real vector x e Rn. Define Δf(x) := [ax1 f(x) ... axnf(x)]> ,

the gradient of the function f at point x.  Which of the following state- ments holds true:

a)  f is convex if and only iff(y) — f(x) P axif(x)(yi — xi ) for all x, y e Rn.

b)  f attains a maximum at x e Rn  if Δf(x) < 0.

c) iff is convex in Rn then H(f)(x) is asymmetric non-negative semidef- inite matrix.

A6. Let xT  = (x1 ,...., xn ) and f(x) =P xi(2). Which of the following state-

ments 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)i + Pu |  IuI2    1} ,

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

is a Quadratic 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)i + Pu |  IuI2    1} ,

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

is a Quadratic 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 Quadratic Program.   If yes,  provide an explanation why. If not, explain why not.

B4.   Consider a Quadratic Program of the form:

max   xT Px

s.t.    Ax = b.

When does this QP have a unique solution?

B5.   State the definition of the  Second-Order  Cone Program  (SOCP). More-

over, give asimple example of Quadratically Constrained Quadratic Prob- lem which is not SOCP.

B6.   Given the linear program (LP)

min   cTx

s.t.   Ax = b,x ≥ 0.

Compute Lagrangian dual function g.   Is g  a concave function?   Write down the dual Lagrangian problem?  How is its optimal value related to the optimal value of the primal LP?

B7.    Consider the LP

max     (5, 3, 5)x

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

@  −1     1      1    A         @  −1  A

Derive  dual  LP,  and  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(8)  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  ascent method?  What is it used for?  Explain on an example in R1 .

B10.    Assume  x 2 X ,  X is  a concave subset of Rn  and  f is a concave di↵eren- tiable function on Rn.  What  is the necessary and sufficient condition for x 2 X to be a maximum point of f (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  convex/concave  function  have?   Provide  an  example  of  a  convex function  with  multiple  local  maxima.    Explain  how  to  select  a  particu- lar  global  minimum  of  a  quadratic  function  by  means  of  regularisation. Provide a simple example.

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

Section C: Longer Questions

C1.   The princess’ wedding ring can be made from four types of gold 1, 2, 3, 4 with the following amounts of milligrams of impurity per gram:

a) Formulate an LP that will determine the most valuable ring that can be made containing at most 6mg of lead and at most 10mg of cobalt.

b) Formulate the dual LP and finda feasible solution for the dual LP. Find a feasible solution of the primal LP and check complimentary slackness for the aforementioned solutions of the primal and dual problems.