EEEN40580: Optimisation Techniques for Engineers (Due: 18/NOV/19) Submission Assignment #3
Lecturer:Dr.GiovanniRusso Var.#1 a=3 b=4 c=4 s1=− s2=+ Offering1
Course Policy: Read the instructions below carefully before you start working on the assignment, and before you make a submission. See the document “2019 Regulations and grading” on Brightspace for additional information about grading and submission. Below are the key instructions summarised for your convenience:
• The report you are going to produce on this lab activity is individual;
• The deadline for the submission of your report on this lab is 12 noon on 18 November 2019;
• Each student has to submit a hard copy of their report to the School Office;
• Please include the listing of the relevant code into the report.
• A soft copy (.pdf files) and the relevant .m code be sent to giovanni.russo1@ucd.ie;
• The cover sheet of your report must contain a signed declaration that the work is your own and that you
have read and understood the University policy on plagiarism. The form can be found on http://www.ucd.ie/eece/. See below for screenshots from where you can download the “Ownership of Work” form you will need for
the cover sheet:
• Some of the problems require numerical value for the parameters α and β. They correspond to the last two digits of your student number (β is the last one).
1
2
3
1
Submission Assignment #3 2
Problem 1: Convex and Smooth Functions
For all problems below explanations are needed.
1. Assume f(x) is a convex function. Define f+(x) := max{f(x),0}. Is f+ convex? 1
np
2. Compute the sub-gradient for p-norm ∥x∥p := |xi|p , where 1 ≤ p < +∞.
(6 points)
i=1
3. Let y(x) = (−1)α(Ax, x). Under which conditions on matrix A function y(x) is convex?
4. Is the product of two convex functions convex? Positive answer requires a proof, negative – counterexam- ple.
5. Let x ∈ Rn, a ∈ Rn, b1 ∈ R and b2 ∈ R. What is the distance between two parallel hyperplanes {x ∈ Rn|aT x = b1} and {x ∈ Rn|aT x = b2}? Answer the question by setting up an optimization problem.
6. Which of the following sets is convex?
(a) {x:∥x∥p ≤1},p=1,2,3;
(b) {x:(ai,x)≤bi, ai ∈Rn, bi ∈R};
(c) {(x,t) ∈ Rn+1 : ∥x∥p ≤ t}, p = 1,2,3.
Consider the following problem:
x21 + x2
(x −α)2 +(x −α)2 ≤α2
x 1 , x 2 ∈ R
Ifα=0,thenpickα=β. Ifalsoβ=0,thenpickα=1intheaboveproblem. Then:
(7 points)
Problem 2: KKT Conditions
minimise subject to
12
(x1 −α)2 +(x2 +α)2 ≤α2
1. Sketch the feasible set and level set for the objective (recall: level sets are sets of points where a function takes the same, constant, value). Find the optimal point x∗.
2. Give the KKT conditions. Do there exist Lagrangian multipliers λ∗1 and λ∗2 that prove that x∗ is optimal?
3. Derive and solve the Lagrange dual problem. Does strong duality hold? (Hints: (i) for a generic ratio, set a/0 = 0 if a = 0 and a/0 = −∞ if a < 0; (ii) given a symmetric Lagrange dual function in the variables λ1 and λ2. Then, if the optimum exist, it must satisfy λ1 = λ2). Please comment on the relation between your answer to this point and your answer to the previous item.
(8 points)
Motivation
Let us consider a classical optimisation problem where an investor wants to make a profit by trading assets. The principal idea is to allocate some budget among N assets – create a portfolio, to hold it for a fixed period of time and then to sell it at the end of this period. The task is to find optimal distribution of the budget over the assets.
Return and risk of a portfolio
Let us assume that at the beginning of the investment period we bought q shares of the same asset at price p1
Problem 3: Markowitz Portfolio Optimisation
Submission Assignment #3 3 euros a share, thus our investment is x = qp1 euro. At the end of the period we sell q shares at price p2 euros,
so the profit is ∆x = (p2 − p1)q = p2−p1 x := rx, where r = p2−p1 is the return rate. By considering the case p1 p1
of two or more assets with initial investments x and corresponding returns r, the profit of a portfolio yields f = rT x. The return of portfolio R is the ratio of its profit and total investment, i.e., R = rT x := rT w, where
1T x
w = x denotes fractions of investments over the assets, and, the total fraction is 1T w = 1. Clearly, due to
1T x
stochastic nature of price action, vector r is random, and it possesses certain statistical properties. The more
we know about them, the better portfolio can be created.
The expected return of portfolio R ̄ is the following average R ̄ = E[rT w] = E[rT ]w = ̄rT w, where ̄rT is the vector whose components are expected returns of each asset. A convenient way of estimating the risk of a portfolio is to consider its variance V
V =E(R−E[R])2=E(r− ̄r)Tw(r− ̄r)Tw=EwT(r− ̄r)(r− ̄r)Tw=wT E(r− ̄r)(r− ̄r)Tw
C
where C is the covariance matrix.
For this problem we use a simple model for r implying that the corresponding random process is stationary and all parameters that characterise distribution of r, such as ̄r and C are constant, and their numerical values are known from the historical data. The values will be given in the following section.
Task
1. Formulate the problem for a portfolio of minimal risk, whose expected return is at least R0. Assume that short positions (when the profit is taken from downward price motion) are not allowed.
2. Solve the problem in Matlab using fmincon function for R0 = {0, 0.5, 1, . . . , 10}. For the obtained solution do the following:
• Plot the corresponding result on the risk-returns plane (√V,R ̄) (efficient frontier). On the same
√
• Plot the sharp ratio (√V , R ̄ ) and find w∗ that corresponds to optimum portfolio. Comment the
plane show risk-returns for individual assets (
Cii, r ̄i), i = {1, . . . , 6} and comment the result.
√
V
result.
−7.7
6.6
4.84 −2.46 −0.94 2.02 −0.15 0.1
−2.46 8.18 −1.07 −0.78 0.39 1.96
−0.94 −1.07 5.52 0.5 0.92 0.68
−9.1 ̄r= 2.5 ,
and C= 2.02 −0.78 0.5 7.56 −0.36 −0.03 1.0 −0.15 0.39 0.92 −0.36 5.29 −1.02
6.4 0.1 1.96 0.68 −0.03 −1.02 8.29