\documentclass{article} \usepackage[utf8]{inputenc} \usepackage{amssymb} \usepackage{amsmath} \usepackage{comment} \usepackage{url} \usepackage{graphicx} \usepackage{xcolor} \begin{document} \begin{center} \textbf{CSE 203B W25 Midterm 10AM 2/23/2025 - 10AM 2/25/2025} \\ Submit your solution to Gradescope before the due time (no late submission). \end{center} \noindent \textbf{Policy of the Exam:} \noindent 1. This is an open-book take-home exam. Internet search is permitted. However, you are required to work by yourself. Consultation or discussion with any other parties is not allowed. \noindent 2. You are not required to typeset your solutions. We do expect your writing to be legible and your final answers clearly indicated. Also, please allow sufficient time to upload your solutions. \noindent 3. You are allowed to check your answers with programs in Matlab, CVX, Mathematica, Maple, NumPy, SciPy etc. Be aware that these programs may not produce the intermediate steps needed to receive credit. \noindent 4. If something is unclear, state the assumptions that seem most natural to you and proceed under those assumptions. Out of fairness, we will not be answering questions about the technical content of the exam on Piazza or by email. The solution will then be graded based on the reasonable assumptions made. \\ \noindent \textbf{Part I: True or False: Briefly explain your answer} (30 pts, 3 pts each) \\ \noindent I.1 Convex Set\\ The set $S = \{ (x,y) \in \mathbb{R}^2 ~|~ y > 0, \frac{(x+2y)^2}{y} < x - y + 3 \}$ is convex. \\ T/F:\\ \noindent I.2 Matrix Solver\\ If $\hat{\mathbf{x}}$ is an approximate solution to \( \mathbf{A}\mathbf{x} = \mathbf{b} \), then the relative residual $\frac{\|\mathbf{b}-\mathbf{A}\hat{\mathbf{x}}\|_2}{\|\mathbf{b}\|_2}$ is always larger than the relative error $\frac{\|\hat{\mathbf{x}}-\mathbf{x}\|_2}{\|\mathbf{x}\|_2}$ for any matrix $\mathbf{A}$. \\ T/F:\\ \noindent I.3 Support Vector Machine\\ Given a set of points \( \{(x_i,y_i) ~|~ i=1,...,m\} \), where \( x_i \in \mathbb{R}^n \) and \( y_i\in\{-1,1\} \), we find a hyperplane with vector \( a \in \mathbb{R}^n \) and bias \( b \in \mathbb{R} \) by solving the optimization problem: $ \min_{\mathbf{a},b} ||\mathbf{a}||_2^2, ~\mathbf{a}\in \mathbb{R}^n, ~b\in \mathbb{R} \text{ \ subject to\ } y_i(\mathbf{a}^Tx_i -b)\geq 1, ~\forall i=1,...,m. $ To have a valid solution, the margin, defined as the distance from the hyperplane to the closest point across both classes, is at least 1. \\ T/F:\\ \noindent I.4 Dual Cone\\ $K = \{\theta_1 u_1 + \theta_2 u_2 \mid u_1 = [3, -2]^T, u_2 = [1, 1]^T, \theta_1 \geq 0, \theta_2 \geq 0\}$, its dual cone is $K^* = \{x_1 u_1 + x_2 u_2 \mid u_1 = [2,3]^T, u_2 = [-1,1]^T, x_1 \geq 0, x_2 \geq 0\}.$\\ T/F:\\ \noindent I.5 Convex Function\\ If \( f_1(x) \) and \( f_2(x) \) are convex functions, their weighted sum $ f(x) = w_1 f_1(x) + w_2 f_2(x)$ is \textbf{always convex}, where $w_1, w_2\in R$. \\ T/F:\\ \noindent I.6 Conjugate Function\\ Given function $f(x) = x_1^2 + 5x_1x_2 - x_2^2$, where $x \in \mathbb{R}^2$, then the conjugate of the conjugate function, $f^{**}(x)$, is equal to itself, i.e., $f^{**}(x) = f(x)$.\\ T/F:\\ \noindent I.7 Fenchel's Inequality\\ Fenchel’s inequality states that for any convex function \( f(x) \), its conjugate function \( f^*(y) \) satisfies: $f(x) + f^*(y) \geq \langle x, y \rangle, \quad \forall x, y.$\\ Consider the following statement: If \( f(x) \) is strictly convex and differentiable, then Fenchel’s inequality attains equality if and only if \( y = \nabla f(x) \).\\ T/F:\\ \noindent I.8 Geometric Programming \\ The geometric programming formulation can incorporate the posynomial \textbf{equality} constraints, i.e. $\sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}=1$, where $K \geq 1$ and $c_k > 0$.\\ T/F:\\ \noindent \noindent I.9 Duality \\ For any primal optimization problem, taking the dual of its dual problem and finding its optimal value always gives back the value equal to the optimal value of the original primal problem. \\ T/F:\\ \noindent I.10 Min Max Problem\\ In the context of duality theory, if a minimax problem has a saddle point, the duality gap must be zero. That is, given Lagrangian $\mathcal{L}(x, \lambda)$, consider the minimax objective:\\ \[\min_{x} \max_{\lambda \succeq 0} \mathcal{L}(x, \lambda)\] Assume that there exists a saddle point $(x^*, \lambda^*)$ for the above objective, then the duality gap for the corresponding original optimization problem is zero. We assume that the saddle point satisfies the KKT conditions.\\ T/F:\\ \noindent \textbf{Part II: Problem Solving: Show your process} \\ \noindent Problem 1. Conjugate Function. (20 pts) \\ Find the conjugate function of the following functions. \\ \noindent 1.1 $f(x) = 2x^2-5x+9$, where $x\in R$.\\ \noindent 1.2 Consider the function \[ f(x) = \begin{cases} 2||x||_2^2, & ||x||_2 \leq b, \quad \\ b(4||x||_2 -b), & ||x||_2 > b, \quad \\ \end{cases} \] \noindent where variable $x\in R^n$ and constant $b\in R_{++}$. \\ \noindent Problem 2. Linear Programming. (20 pts) \noindent \begin{eqnarray} A = \begin{bmatrix} 9 & 3 & -1 & 2 & 0 & 1 & 0 \\ -3 & 1 & 1 & 1 & 1 & 1 & 1 \\ 5 & 0 & 1 & 1 & 0 & 0 & -1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 & -1 & -1 & 0 \end{bmatrix}, \nonumber \end{eqnarray} \\[-0.5in] \begin{eqnarray} b^T= \begin{bmatrix} 1 & 5 & 2 & 3 & 2 \end{bmatrix}, \nonumber \end{eqnarray} \\[-0.6in] \begin{eqnarray} c^T= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{bmatrix}, \nonumber \end{eqnarray} and $n=7$, perform steps A, B, and C for problems 2.1, 2.2, 2.3, and 2.4.\\ \noindent A. Solve the following linear programming problems twice, once using the primal formulation and once using the dual formulation. \noindent B. Check the feasibility of the solution. If a solution is not found, explain why a solution is not available and suggest how to mitigate the issue if you are the project leader. (For this exam, there is no need to solve the mitigated problem unless you feel the explanation is not convincing enough.) \noindent C. Compare the primal and dual solutions. If the primal and dual formulation solutions are different, explain the difference.\\ \noindent 2.1. minimize $f_0(x)= c^T x$ subject to $Ax \leq b$, $x\in R^n$.\\ \noindent 2.2. minimize $f_0(x)= c^T x$ subject to $Ax = b$, $x\in R^n$.\\ \noindent 2.3. minimize $f_0(x)= c^T x$ subject to $Ax \leq b$, $x\in R_+^n$.\\ \noindent 2.4. minimize $f_0(x)= c^T x$ subject to $Ax = b$, $x\in R_+^n$.\\ \noindent Problem 3. KKT Conditions. (30 pts) \noindent Imagine that you work for a bank handling its trading portfolio. Your task is to minimize the risk associated with the portfolio while generating decent returns. A variant of this problem can be formulated as a convex optimization problem. For the objective function, we have a covariance matrix \(\Sigma \in S^n_{++}\) associated with the risk and a vector $x \in R^n$ associated with the investment portfolio. For inequality constraint, we have a minimum return threshold \(b \in R\), and a vector \(\alpha \in R^n\), which represents the average rate of return of the stocks. For the equality constraint. the total investment amount is fixed and normalized to one. \begin{equation} \begin{aligned} &\: \min_{x} \frac{1}{2}x^T\Sigma x \\ &\text{s.t.} \:\: \alpha^Tx \ge b, \\ &\ \:\:\:\:\:\:\: \mathbf{1}^Tx = 1. \end{aligned} \label{eq:linear} \end{equation} \noindent Taking the above primal problem, you need to describe the following. \\ \noindent a) Write the Lagrangian of the problem.\\ \noindent b) Write the KKT conditions for the optimal $x$ for the problem. \\ \noindent c) Write the dual problem. \\ d) Model this convex optimization problem in the convex solver of your choice. Describe the numerical value of the vector $x$ and the minimum value of the problem. You are given the following: \begin{eqnarray*} \Sigma = \begin{bmatrix} 10 & 5 & 2 \\ 5 & 3 & 2 \\ 2 & 2 & 3 \\ \end{bmatrix}, \alpha = \begin{bmatrix} 2 \\ 4 \\ 7 \\ \end{bmatrix}, b = 3 \end{eqnarray*} \\[-0.2in]. \end{document}