Question 1.

Solve the following optimisation problem

min x² + y²

Subject to

x + 2 y ≥ 1

Question 2.

Consider the following problem related to entropy maximisation in information theory. For ease of solution you can solve the problem ignoring the non-negativity constraints on p and q and then verify that they are satisfied.

min p log p + q log q

subject to p + q = 1

p, q ≥ 0

i. Solve the primal problem directly

ii. Obtain the dual problem and solve it. Verify it gives the same answer as the primal problem.

iii. By doing an internet search or looking up textbooks, explain why this problem would be called an "entropy maximisation" problem.

Question 3.

Solve the following modified entropy optimization problem. For ease of solution you can solve the problem ignoring the non-negativity constraints on p and q and then verify that they are satisfied.
min p log p + 2q log q

subject to

p + q = 1
p, q ≥ 0

Question 4.

A transmitter operates over four orthogonal channels as shown below.

Suppose the channel power gains and receiver noise powers are as follows:

g₁ = 0.2             σ²₁ = 1
g₂ = 0.2             σ²₂ = 2
g₃ = 2.0             σ²₃ = 4
g₃ = 0.5             σ²₄ = 10

The total power at the transmitter, P, is given by

P = P₁ + P₂ + P₃ + P₄

The waterfilling technique is used to maximise the sum capacity over all channels.

i. Using the waterfilling technique determine the range of power levels, P, for which:
a) only one channel is used to send data (i.e. one channel is allocated non-zero power)
b) exactly two channels are used to send data
c) exactly three channels are used to send data
d) all four channels are used to send data

ii. Determine the power allocation for each channel if:
a) P = 10
b) P =20
c) P = 50
(You can do this problem either by hand or using Matlab).

iii. Suppose in (ii.b) the power is increased by 0.1 i.e. the power becomes 20.1.

WITHOUT using the waterfilling algorithm again but using the associated theory and the theory of Lagrange multipliers estimate the increase in channel capacity.

Question 5.

Suppose in the waterfilling algorithm that instead of log(1 + α_iP_i) the utility function was tan^-1(α_iP_i). i.e. the waterfulling optimisation problem became

max ∑_itan^-1 (a_iP_i )

Subject to

P_i ≥ 0 i = 1,....,, N

P₁ + ..... + P_N = P

i. Determine the equivalent of equation (1) on slide 13 of the notes on waterfilling.

ii. What interpretation can be given to the nature of the utility function used? Explain.

Question 6.

Consider the channel allocation subproblem used the combined channel power allocation scheme in lectures. Consider a system with K = 2 users and N = 4 channels. Suppose the system parameters (in notation used in lecture) are given as

           0.1  0.2  0.8  1

[g_k,n = 

           0.5  0.3  0.1  0.5

             1

[σ²_{k ,n} =

             3  3  4  1

[P_n] = (1, 1, 1, 1)

W = 4

ρ1 : ρ = 1: 2

i. Determine which channels are allocated to which user.

You can solve this problem either by hand, Matlab or a combination of the two.

ii. When this channel allocation method is used in the combined channel and power allocation method in lectures under what conditions would you expect that the channel allocation would underperform? Explain.

Question 7.

Many problems in optimisation are solved using what are called "greedy algorithms".

By looking sources on the internet explain what these type of algorithms are and by what principles they operate.