\documentclass{article}
\usepackage[letterpaper, portrait, margin=1in]{geometry}
\usepackage{fancyhdr} % header
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{multirow}

\usepackage{tikz}
\usetikzlibrary{chains}

\usepackage[]{algorithm2e}
\usepackage{hyperref}

\usepackage[useregional]{datetime2}

\lstset{
  basicstyle=\ttfamily,
  mathescape
}
\newcommand\floor[1]{\lfloor#1\rfloor}
\newcommand\ceil[1]{\lceil#1\rceil}
\newcommand\indep{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\begin{document}

\begin{center}
\textbf{CSE 203B W21 Homework 4} \\
\end{center}

\noindent{\textbf{Due Time : 11:50pm, Wednesday Feb. 22, 2023}} 
        \textbf{Submit to Gradescope}  \\
        
{\bf In this homework, we work on exercises from the textbook. Problems 4.1, 4.8, 4.11, and 4.15 are related to LP. Problems 4.21, 4.39, and 4.47 are related to QCQP, and SDP. Problem 5.3 is about the basic definition of duality. Problems 5.4, 5.5, 5.6, 5.7, 5.8, 5.9, and 5.10 are examples and applications of duality. Also, we practice using the convex optimization tools on a linear programming problem, and a quadratic programming problems. \\

Total points: 50.  Exercises are graded by completion, and assignments are graded by correctness.}\\

\noindent\textbf{I. Exercises from textbook chapters 4 \& 5 (15 pts, 1pt for each problem)}

\indent
4.1, 4.8, 4.11, 4.15, 4.21, 4.39, 4.47, 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.9, 5.10. \\

\noindent\textbf{II. Assignments (35 pts)} \\%\\[0.2in]

\noindent
\textbf{II.1 Linear Programming:} You are free to use any software packages. (15 pts)

\noindent
Given \begin{eqnarray}
A = \begin{bmatrix} 
2 & 0 & 1 & 1  \\
0 & 0 & 0 & 1 \\
0 & 2 & 1 & 0 \\
2 & 3 & -1 & 2 \\
0 & 2 & 2 & 0
\end{bmatrix},  \nonumber
\end{eqnarray}
\\[-0.5in]

\begin{eqnarray}
b^T= \begin{bmatrix} 
2 & 1 & 3 & 5 & 5
\end{bmatrix}, \nonumber
\end{eqnarray}
\\[-0.6in]

\begin{eqnarray}
c^T= \begin{bmatrix} 
-1 & -2 & -3 & -1 
\end{bmatrix}, \nonumber
\end{eqnarray}
and $n=4$,
solve the following linear programming problems. If a solution is found, validate that the solution satisfies the optimality criteria (which was talked about in class or textbook).
Otherwise, explain why a solution is not feasible and suggest how to mitigate the issue if you are the project leader:

\noindent
II.1.1. minimize $f_0(x)= c^T x$ subject to $Ax \leq b$, $x\in R^n$.

\noindent
II.1.2. minimize $f_0(x)= c^T x$ subject to $Ax = b$, $x\in R^n$.

\noindent
II.1.3. minimize $f_0(x)= c^T x$ subject to $Ax \leq b$, $x\in R_+^n$.

\noindent
II.1.4. minimize $f_0(x)= c^T x$ subject to $Ax = b$, $x\in R_+^n$.\\

\noindent
\textbf{II.2 Graph embedding} (20 pts)
Graph embedding is an important problem in machine learning and graph theory. Given an undirected graph $G = (V, E)$ with $n$ vertices, the problem is to assign coordinates in $\mathbb{R}^m$ to each vertex $v \in V$. Typically there are desired qualities or constraints imposed on the embedding\textemdash e.g. the coordinates assigned to connected nodes should be close with respect to some notion of distance. For example, the choice of Euclidean distance yields a quadratically constrained quadratic program (QCQP). Let $A \in \{0,1\}^{n\times n}$ 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 = D - A$.

One well known way to do graph embedding (Laplacian Eigenmaps) is to solve the following problem:
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n\times m}} \langle X, LX \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 A, B \rangle$ is defined to be $\text{tr}(A^\top B)$.

(i) Show that when $m = 1$, $\langle x, Lx \rangle = x^\top L x = \sum_{i,j \in E}(x_i - x_j)^2$. Is (1) convex? Why or why not?  \\

(ii) Show how the linear constraint may be eliminated and derive the dual and KKT conditions of the relaxation, where $r$ is a scalar constant. Are there any issues with this formulation?
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n\times m}} \langle X, \widetilde{L}X \rangle  \\
     &\:\:\text{s.t. } \langle X, X \rangle \leq r^2
\end{aligned} \label{eq:unfixed}
\end{equation}

(iii) One way to condition the relaxation is to introduce additional constraints. Consider a ``semi-supervised'' modification of problem 1: where first $k$ vertices are ``labeled'' or ``anchored''\textemdash i.e. we have the constraints $X_i = y_i$ for $1,\ldots,k$, , where $y_i \in \mathbb{R}^m$. 
\begin{equation}
\begin{aligned}
    &\min_{X \in \mathbb{R}^{n\times m}} \langle X, \widetilde{L}X \rangle  \\
     &\:\:\text{s.t. } \langle X, X \rangle \leq r^2,\quad X_i = y_i, \ldots i = 1,\ldots, k
\end{aligned} \label{eq:unfixed}
\end{equation}
Derive the associated optimization problem and its dual in \emph{standard form}. (Hint: there are multiple derivations. Two potential directions: (a.) consider the partitioning $X = \left[\begin{smallmatrix}
X_l\\
X_u
\end{smallmatrix}\right]$, where $X_l$ denote the ``labeled'' first-$k$ rows of $X$ (b.) consider the geometry of the label constraints.) \\

(iv) Let $X \in \mathbb{R}^{n\times 3}$ represent the coordinates of $n$ vertices in $3$-d. The vertex coordinate assignment can be visualized\textemdash a ``drawing'' of $G$. Implement your solution to Problem (iii) and show your result for the given graph. We have written a partial framework in Python+CVXPY to get you started\footnote{If you prefer a different language or framework, you can also download a .txt file containing $L,x,y$, and the indices of the fixed nodes: \url{https://piazza.com/class_profile/get_resource/kx85xrdgigl5m5/kzfw6ud6fd964c} ($idx,x,y$ are the first 3 columns)}: \\ \url{https://colab.research.google.com/drive/1nvwWug_eowcAf4HrznlTm4YhcBJuokgc?usp=sharing}.

\iffalse
Graph embedding is an important problem in machine learning and graph theory. Given an undirected graph $G = (V, E)$ with $n$ vertices, the problem is to assign coordinates in $\mathbb{R}^m$ to each vertex $v \in V$. Typically there are desired qualities or constraints imposed on the embedding\textemdash e.g. the coordinates assigned to connected nodes should be close with respect to some distance metric. We can formulate this as a quadratically constrained quadratic program (QCQP). Let $A \in \{0,1\}^{n\times n}$ 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 = D - A$.


Let $x,y \in \mathbb{R}^n$ represnt the $x$ and $y$ coordinates of $n$ vertices. Given a parameter $c \in \mathbb{R}_{++}$, one way to define the graph embedding problem in 2-d is to solve the following problem:
\begin{equation}
\begin{aligned}
    &\min_{x, y \in \mathbb{R}^{n}}x^\top L x + y^\top L y \\
    &\:\:\text{s.t.}\quad x^\top x \leq c,\quad y^\top y \leq c
\end{aligned} \label{eq:unfixed}
\end{equation}

(i) Show that $x^\top L x = \sum_{i,j \in E}(x_i - x_j)^2$ \\
(ii) Consider a partitioning of $x$; $x = [x_1 : x_2]^\top$, where $x_1\in\mathbb{R}^{n-k}$ corresponds to the coordinates of $n-k$ ``free'' nodes and $x_2\in\mathbb{R}^{k}$ are the coordinates of $k$ ``fixed''/``anchor'' nodes (likewise for $y$). Under these ``fixed-node'' constraints, show that Prob.~\ref{eq:unfixed} is equivalent to
\begin{align*}
    &\min_{x_1, y_1 \in \mathbb{R}^{n-k}}x_1^\top L' x_1 + y_1^\top L' y_1 + b^\top x_1 + d^\top y_1 \\
    &\quad\:\:\:\text{s.t.}\quad x_1^\top x_1 \leq c_x',\quad y_1^\top y_1 \leq c_y'
\end{align*}
In other words, express $L'$, $b$, $d$, and $c_x'$ \& $c_y'$ in terms of $x_1$, $x_2$, $y_1$, $y_2$, $L$, and $c$. Are there any issues with Prob.~\ref{eq:unfixed} if there are no fixed nodes? \\
(iii) Implement the problem in CVX/CVXPY and show your result for the given graph with $c_x' = c_y' =10$. \\
\indent (iii.a) We have written a partial framework in Python to get you started: \\ \url{https://colab.research.google.com/drive/1apgxNJGN1E4_W6awYbbhNxTyL0VvvMVH?usp=sharing}. \\
\indent (iii.b) If you prefer a different language, you can also download a .txt file containing $L,x,y$, and the indices of the fixed nodes: \\ \url{https://piazza.com/class_profile/get_resource/kx85xrdgigl5m5/kzfw6ud6fd964c} ($idx,x,y$ are the first 3 columns) \\
(iv) Suppose we change the quadratic inequality constraints on $x$ and $y$ to equality constraints and add a constraint $x^\top y = c_{xy}'$. Is the problem still convex? If not, can we still recover a solution?
\fi

\end{document}