10.6 Practice Problems
Problem 10.6.1. Use the KKT conditions to maximise \(xy\) subject to \(x + 2y \leq 8\), \(x, y \geq 0\), and interpret the multiplier.
Show solution
Solution. Minimise \(-xy\). With \(x, y > 0\) and the constraint active: \(-y + \lambda = 0\), \(-x + 2\lambda = 0\), so \(x = 2y\), and \(x + 2y = 8\) gives \(x = 4\), \(y = 2\), \(\lambda = 2\). The objective \(-xy\) is not convex, but on the region \(x, y > 0\) the maximum of \(xy\) is at this point by the AM–GM inequality: \(8 = x + 2y \geq 2\sqrt {2xy}\), so \(xy \leq 8\). Relaxing the constraint to \(8 + \varepsilon \) raises the maximum by about \(2\varepsilon \).
Problem 10.6.2. Show that \(f(x) = x^{\mathsf T}Qx\) is convex if and only if \(Q\) is positive semidefinite.
Show solution
Solution. The Hessian is \(2Q\), constant, and a twice differentiable function is convex exactly when its Hessian is positive semidefinite everywhere. Directly: \(f(\lambda x + (1 - \lambda )y) - \lambda f(x) - (1 - \lambda )f(y) = -\lambda (1 - \lambda )(x - y)^{\mathsf T}Q(x - y)\), which is \(\leq 0\) for all \(x, y\) exactly when \(Q\) is positive semidefinite.
Problem 10.6.3. Solve the equality-constrained QP: minimise \(x_1^2 + 2x_2^2\) subject to \(x_1 + x_2 = 3\), by the KKT linear system.
Show solution
Solution. \(Q = \operatorname {diag}(2, 4)\), \(c = 0\), \(A = (1, 1)\), \(b = 3\). The system is \(2x_1 + \mu = 0\), \(4x_2 + \mu = 0\), \(x_1 + x_2 = 3\), so \(x_1 = 2x_2\), \(x_2 = 1\), \(x_1 = 2\), \(\mu = -4\), and the minimum is \(4 + 2 = 6\).
Problem 10.6.4. Find the global minimum-variance portfolio of two assets with variances \(\sigma _1^2\), \(\sigma _2^2\) and covariance \(\sigma _{12}\), allowing short sales.
Show solution
Solution. With \(w_2 = 1 - w_1\), the variance \(w_1^2\sigma _1^2 + 2w_1(1 - w_1)\sigma _{12} + (1 - w_1)^2\sigma _2^2\) is minimised at \(w_1 = (\sigma _2^2 - \sigma _{12})/(\sigma _1^2 + \sigma _2^2 - 2\sigma _{12})\). For \(\sigma _1^2 = 0.04\), \(\sigma _2^2 = 0.09\), \(\sigma _{12} = 0.006\): \(w_1 = 0.084/0.118 = 0.712\).
Problem 10.6.5. For the barrier problem of Software 10.5.3, show that the barrier minimiser is \(x_1 = x_2 = \sqrt {1 + t/2}\), that the objective there is \(2 + t\), and that the multiplier estimate is \(2\) for every \(t\).
Show solution
Solution. By symmetry take \(x_1 = x_2 = s\); then \(\frac {d}{ds}\bigl (2s^2 - t\log (s^2 - 1)\bigr ) = 4s - \frac {2ts}{s^2 - 1} = 0\) gives \(s^2 = 1 + \frac t2\). The objective is \(2s^2 = 2 + t\), and the multiplier estimate is \(t/(s^2 - 1) = t/(t/2) = 2\). At \(t = 1\), \(s = \sqrt {1.5} = 1.2247\), as printed.
Problem 10.6.6. Explain why a non-convex problem can satisfy the KKT conditions at a point that is not a minimum, with the example: minimise \(-x^2\) subject to \(-1 \leq x \leq 1\).
Show solution
Solution. At \(x = 0\) no constraint is active and \(\nabla f = 0\), so the KKT conditions hold with \(\lambda = 0\); but \(x = 0\) is the global maximum. The minima are \(x = \pm 1\), where \(-2x + \lambda _2 = 0\) (for \(x \leq 1\)) gives \(\lambda _2 = 2 \geq 0\) at \(x = 1\). The KKT conditions are necessary, not sufficient, without convexity.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.