\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{url}
\usepackage{graphicx}

\usepackage{xcolor}
\begin{document}


\begin{center}
\textbf{CSE 203B W23 Midterm 10AM 2/26/2023-10AM 2/28/2023} \\
Submit your solution to gradescope before the due time.
\end{center}

\noindent
\textbf{Policy of the Exam:} Here is the 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, 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: Explain your answer with one sentence} (30 pts) \\

% Convex set or not, extended from hw1 w'21
\noindent
I.1 (convex set):
Set $\{(x, y) | x^2 + y^2   \geq 1, x, y \in R \}$ is convex.\\
T/F:\\

% Dual Cone, extended from midterm W'19
\noindent
I.2 (dual cone):
Given cone $K = \{x | a_1^T x \geq 0, a_2^T x \leq 0,$ where $a_1, a_2, x\in R^n \},$ 
its dual cone is $K^* = \{a_1 \theta_1 + a_2 \theta_2 | \theta_1 \geq 0, \theta_2 \leq 0, $ and $ \theta_1, \theta_2 \in R \}$.\\
T/F:\\

\noindent
I.3 (dual cone):
The \textbf{dual of the dual} cone $K = \{x |~||Ax+b||_2 < c^Tx+d \}$ is itself, where
$A\in R^{mn}, x, b, c \in R^n$ and $d\in R$.\\
T/F:\\

\noindent
I.4 (Convex Function): Given a function $f(x) = 1.4x^{1.3} + 2.2x^{2.5},$ where $x\in R_+$.
The function is convex.\\
T/F:\\

\noindent
I.5 (Convex Function): Function $g(x)= max_y f(x,y)$ is a convex function
for any $f(x,y) \in R$, where $x, y \in R^n$. \\
T/F:\\

\noindent
I.6 (Conjugate Function): Given function $f(x)= x^TAx +b^T x +c,$ where $x, b \in R^n, A\in R^{nn},$ and $c\in R$. 
Suppose that matrix $A$ is not positive semidefinite. We can claim that the conjugate function, $f^*(y)= \infty$, for all $y\in R^n$. \\
T/F:\\

\noindent
I.7 (Supporting Hyperplane): Given a differentiable and convex function $f(x)$, where $x\in R^n$, and a fixed point $\bar x \in R^n$. Suppose that in a $n+1$ dimension space $[x^T, t]^T$, 
we draw the supporting hyperplane 

$[\nabla f(\bar x)^T, -1] (\begin{bmatrix} x \\ t \end{bmatrix} - \begin{bmatrix} \bar x \\ f(\bar x) \end{bmatrix} )=0$.  

\noindent
We can claim that the supporting hyperplane intersects the $t$ axis at its conjugate function i.e. $[x^T=\b0^T, t=-f^*(y)]^T$ where $y=\nabla f(\bar x)$, and $\b0$ is a vector of $0$.\\
T/F:\\

\noindent
I.8 (Problem Formulation/Duality): Given a convex programming problem: 

minimize $f_0(x)$, subject to $Ax \leq b$, $x\in R^n$, $A\in R^{m\times n}$, $b\in R^m$, 

\noindent
where $f_0 (x)$ is a differentiable convex function, we can claim that 

$\nabla f_0(\bar x) \in \{-A^T \theta | \theta \in R_+^m\}$ 

\noindent
is a necessary and sufficient condition for $\bar x$ to be an optimal solution.\\
T/F:\\

\noindent
I.9 (Duality): In the textbook subsection (5.1.1), we have the problem formulation (5.1)
and its Lagrangian $L(x,\lambda, \nu)$. The variable $x$ of the Lagrangian has to be feasible, i.e. $x$ satisfies the constraint in formulation (5.1).\\
T/F:\\

\noindent
I.10 (Min Max Problem): Given a function $f(x,y)= x^TAy$, we have
$x, y \in R^n$ and matrix $A \in R^{nn}$.
We can claim that the equality, \\
$min_x max_y f(x,y)= max_y min_x f(x,y)$ is true when there is a bounded (not infinite) solution. \\
T/F:\\

\noindent
\textbf{Part II: Problem Solving: Show your process} \\

% based on HW1
% Write down dual problem
% Give feasible points for both primal/dual problems
% Come up with a n=xxx, p=xxx examples in dual problem, and use tools to solve your formulated dual problem
\noindent
Problem 1. Dual Cone: Find the dual cone of the following cones. (20 pts)

\noindent
1.1 $K=\{\begin{bmatrix} x \\t \end{bmatrix} |~||Ax||_2 \leq t \}$, where $A \in R^{nn}, x\in R^n,$ and $ t\in R_+ $. Matrix $A$ is nonsingular. (hint: If you have no clue, start with a small but nontrivial case, e.g. n=1 and/or 2.\\

\noindent
1.2 $K=\{\begin{bmatrix} x \\t \end{bmatrix} |~||Ax||_p \leq t \}$, where $A \in R^{nn}, x\in R^n,$ $p \geq 1,$ and $ t\in R_+ $. Matrix $A$ is nonsingular.\\

\noindent
Problem 2. Conjugate Function: Find the conjugate function of the following functions. (20 pts)

\noindent
2.1 $f(x) = -x^3+3x+2$, where $x\in R$.\\

\noindent
2.2 $f(x) = \frac{x_1^2}{x_2}$, where $x\in R_{++}^2$.\\


\noindent
Problem 3. Graph embedding and graph learning. (30 pts)

\noindent
Recall that given a connected, undirected graph $G = (V, E)$ with $n_0$ vertices, the graph embedding problem is to assign coordinates in $\mathbb{R}^m$ to each vertex $v \in V$. Let $A \in \{0,1\}^{n_0\times n_0}$ be the symmetric adjacency of $G$, and let $D$ be the corresponding diagonal degree matrix such that $D_{ii} = \sum_{j}A_{i,j}$. The \textit{graph Laplacian} is defined to be $L_0 = D - A$.

One way to define the graph embedding problem (i.e. Laplacian Eigenmaps) is to solve the following problem:
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n_0\times m}} \langle X, L_0X \rangle \\
    &\:\:\text{s.t. }X^\top X = I, \:\: \textbf{1}^\top X = 0
\end{aligned} \label{eq:unfixed}
\end{equation}
Where the inner product $\langle U, V \rangle$ is defined to be $\text{tr}(U^\top V)$. 

(i) Problem (1) is nonconvex. Prove that the solution is given by $m$ eigenvectors corresponding to the smallest nonzero $m$ eigenvalues of $L_0$.  \\

(ii) Derive the dual and KKT conditions of the semi-supervised problem (you may assume $L$ is nonsingular).
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n\times m}} \langle X, L X \rangle + \langle B, X \rangle  \\
     &\:\:\text{s.t. } \textbf{1}^\top X = 0
\end{aligned} \label{eq:unfixed}
\end{equation}

(iii) Derive the dual and KKT conditions of the problem
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n\times m}} \langle X, L X \rangle + \langle B, X \rangle  \\
     &\:\:\text{s.t. } \textbf{1}^\top X = 0, \quad ||X||_1 \leq c,
\end{aligned} \label{eq:unfixed}
\end{equation}
where $||X||_1 = \sum_{ij}|X_{ij}|$ and $c$ is some constant, say $1000$. (Hint: if you get stuck, try to write the l1 ball in standard form as an lp). Use the framework\footnote{\url{https://colab.research.google.com/drive/1suBO3RgKaqzJBh-tzpGLIlXn625hmzH2?usp=sharing}} from homework 4 to implement this problem (where $L$ and $B$ are now given). Note that the random seed has been updated from homework 4 (different graph and fixed vertices).

\end{document}