EEEN40580 Optimisation Techniques SEMESTER ll EXAMINATIONS - 2018/2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
SEMESTER ll EXAMINATIONS - 2018/2019
School of Electrical and Electronic Engineering
EEEN40580 Optimisation Techniques
Section A: Short Questions
A1. Is the LP given by
max x1 + x2 - x4
s.t. x1 +3x3 5, x1 +3x2 ≥ 3, x1 - 2x4 5, 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 bounded, 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 concave.
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 IΔf(x)I < 0.
c) iff is convex in Rn then H(f)(x) is a symmetric non-negative semidef- inite matrix.
A6. Let f(x) =P xi(2). 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)i + Pu | IuI2 1} ,
where c, ¯(a) e Rn , b e R, P e Rn xn with P 0. Determine if this problem
is a Second-Order Cone Problem. 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 xn 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 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 is this QP has the 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 convex 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
2(−)1 1
1 A
x 0 4(2) 1
@ −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 sufficent 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 on 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 numbers of milligrams of impurity per gram:
Type |
1 |
2 |
3 |
4 |
mg of lead |
1 |
2 |
2 |
1 |
mg of cobalt |
0 |
1 |
1 |
2 |
value |
1 |
2 |
3 |
2 |
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.
C2. Consider the function f(x) =P eai xi .
a) Is f convex for any real ai , i = 1 ...n? Compute the Hessian of f at point x.
b) Provide necessary and sufficient conditions for convexity of f.
c) Write necessary and sufficient optimality conditions for x* to be a minimum point off in the cube [−1, 1]n.
d) Derive the gradient method to find x* from c).
e) Provide a condition on a1 ... an for x* to be the unique minimum point off in the cube [−1, 1]n.
2023-12-09