Quiz on Convex Optimization and KKT Conditions for Data Scientists

📚 Quick Study Guide

• 📈 Convex Set: A set where the line segment between any two points within the set also lies entirely within the set. Mathematically, for any $x, y \in C$ and any $\theta \in [0, 1]$, we have $\theta x + (1 - \theta)y \in C$.
• 🍎 Convex Function: A function where the line segment between any two points on the function's graph lies above or on the graph. Mathematically, $f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y)$ for all $x, y$ and $\theta \in [0, 1]$.
• 📐 Convex Optimization Problem (General Form): minimize $f(x)$ subject to $g_i(x) \leq 0$, $i = 1, ..., m$ $h_j(x) = 0$, $j = 1, ..., p$ where $f$ and $g_i$ are convex functions and $h_j$ are affine functions.
• 🔑 Karush-Kuhn-Tucker (KKT) Conditions: Necessary conditions for optimality in constrained optimization problems, given certain regularity conditions. For the above problem, the KKT conditions are:
  • Stationarity: $\nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) + \sum_{j=1}^{p} \nu_j \nabla h_j(x^*) = 0$
  • Complementary Slackness: $\lambda_i g_i(x^*) = 0$ for all $i$
  • Primal Feasibility: $g_i(x^*) \leq 0$ for all $i$, $h_j(x^*) = 0$ for all $j$
  • Dual Feasibility: $\lambda_i \geq 0$ for all $i$

🧪 Practice Quiz

1. Which of the following is NOT a requirement for a standard convex optimization problem?
   1. A. The objective function must be convex.
   2. B. Inequality constraint functions must be convex.
   3. C. Equality constraint functions must be affine.
   4. D. The feasible set must be non-empty.
2. What does the 'complementary slackness' condition in KKT conditions imply?
   1. A. The Lagrange multipliers must be equal to zero.
   2. B. At the optimal solution, either the constraint is active or the corresponding Lagrange multiplier is zero (or both).
   3. C. The gradient of the Lagrangian must be zero.
   4. D. All constraints must be inactive at the optimal solution.
3. Which of the following functions is convex?
   1. A. $f(x) = x^3$
   2. B. $f(x) = -x^2$
   3. C. $f(x) = e^x$
   4. D. $f(x) = \log(x)$ for $x > 0$
4. Which of the following conditions is NOT a KKT condition?
   1. A. Stationarity
   2. B. Primal Feasibility
   3. C. Dual Feasibility
   4. D. Gradient Descent
5. In the context of KKT conditions, what does 'primal feasibility' refer to?
   1. A. The dual variables being non-negative.
   2. B. The solution satisfying the original constraints of the problem.
   3. C. The Lagrangian being differentiable.
   4. D. The objective function being convex.
6. Consider the problem: minimize $x^2$ subject to $x \geq 1$. Which of the following KKT conditions is most relevant to solving this problem?
   1. A. Stationarity
   2. B. Complementary Slackness
   3. C. Primal Feasibility
   4. D. Dual Feasibility
7. What is the key property of affine functions that makes them suitable as equality constraints in convex optimization problems?
   1. A. They are always non-negative.
   2. B. They preserve convexity of the feasible set.
   3. C. They are easy to differentiate.
   4. D. They are always linear.