\documentclass[]{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{url}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
\usepackage[noadjust]{cite}
\usepackage{threeparttable}
\usepackage{framed}
\usepackage{fullpage}
\usepackage{geometry}
\usepackage{cancel}

\begin{document}
\begin{center}
\textbf{CSE 203B W23 Homework 1} \\
\end{center}

\noindent{\textbf{Due Time : 11:50pm, Wednesday Jan. 18, 2023}} 
\textbf{Submit to Gradescope \\ Gradescope: \url{https://gradescope.com/} }\\

{\bf In this homework, we work on the basic concepts of convex optimization and linear algebra. \\
All the problems are graded by completion.}\\

\noindent {\bf 1. {Convex Optimization} (10 pts)}\\
1.1. Given a function $f_0(x)= x^4-5x^3+4x^2-3x+1$, where
$x\in \mathbb{R}$.
Solve $min_x f_0(x)$ using Kuhn-Tucker conditions. Show your derivation. (2 pts)\\

\noindent
1.2. Given two functions $f_0(x)= x^2-5x+2$, and $f_1(x)= 2x+1$, where
$x\in \mathbb{R}$.
Solve $min_x f_0(x)$ subject to $f_1(x) \leq 0$. (8 pts)\\

\noindent {\bf 2. {Matrix Properties} (16 pts)}

\noindent
2.1. Linear System:

Consider the following system of linear equations
\begin{eqnarray}
x_1 &+ x_2 &+ x_3 =  1\nonumber \\
x_1 & &- 2x_3 =  -2\nonumber \\
&x_2 &+ 3x_3 = -1. \nonumber 
\end{eqnarray}

Write the equations in a matrix form. (2 pts)\\

\noindent
2.2. For the matrix in problem 2.1, derive its range. What's the rank of this matrix? (2pts)\\

\noindent
2.3. Derive the nullspace of the matrix in problem 2.1. What's the relation between the range and nullspace of a matrix? (2pts)\\

\noindent
2.4. Derive the trace and determinant of the matrix in problem 2.1. Write the eigenvalues and eigenvectors. (3pts) \\

\noindent
2.5. Prove the following properties. (3 pts) 
\begin{itemize}
\item {For $A\in \mathbb{R}^{m\times n}, B\in \mathbb{R}^{n\times m}$, tr$AB =$ tr$BA$.}
\item{For $A, B \in \mathbb{R}^{n\times n}$, det$AB$ = det$A$ det$B$.}
\item{For $A \in \mathbb{R}^{n\times n}$, det$A$ = $\prod_{i=1}^{n} \lambda_i$, 
and tr$A$= $\sum_{i=1}^n \lambda_i$, 
where $\lambda_i, i=1, \dots, n$ are the eigenvalues of $A$.}
\end{itemize}

\noindent
2.6. Suppose that you are a tutor. Devise a simple but meaningful numerical example to illustrate the three equations in problem 2.5.
(4 pts)
\noindent \\ 

\noindent {\bf 3. {Matrix Operations} (22 pts)}

{\em \bf Gradient}: consider a function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ that takes a vector $x\in \mathbb{R}^n$  and returns a real value. Then the gradient of $f$ (w.r.t. $x$) is the vector of partial derivatives, defined as 
\begin{eqnarray}
\nabla_x f(x) = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1} \\ \frac{\partial f(x)}{\partial x_2} \\ \vdots \\ \frac{\partial f(x)}{\partial x_n}  \end{bmatrix} . \nonumber
\end{eqnarray} 

{\em \bf Hessian}: consider a function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ that takes a vector $x\in \mathbb{R}^n$  and returns a real value. Then the Hessian matrix of $f$ (w.r.t. $x$) is the $n\times n$  matrix of partial derivatives, defined as 
\begin{eqnarray}
\nabla_x^2 f(x) = \begin{bmatrix} 
\frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_1 \partial x_2} & \hdots & \frac{\partial^2 f(x)}{\partial x_1 \partial x_n}  \\
 \frac{\partial^2 f(x)}{\partial x_1 \partial x_2} & \frac{\partial^2 f(x)}{\partial x_2^2 } & \hdots & \frac{\partial^2 f(x)}{\partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial^2 f(x)}{\partial x_n \partial x_1} & \frac{\partial^2 f(x)}{\partial x_n \partial x_2} & \hdots & \frac{\partial^2 f(x)}{\partial x_n^2}
  \end{bmatrix}.  \nonumber
\end{eqnarray} 

\noindent
3.1. Write the gradient and Hessian matrix for the linear function
\begin{eqnarray}
f(x) = 2b^T x, \nonumber
\end{eqnarray}

where $x\in \mathbb{R}^n$ and vector $b\in \mathbb{R}^n$. (2 pts)\\

\noindent
3.2. Write the gradient and Hessian matrix of the quadratic function
\begin{eqnarray}
f(x) = x^T A x + b^Tx + c,\nonumber
\end{eqnarray}

where $x\in \mathbb{R}^n$, matrix $A\in \mathbb{R}^{n\times n}$, vector $b \in \mathbb{R}^n$,
and $c \in \mathbb{R}$. (2 pts)\\

\noindent
3.3. Given matrix $A\in \mathbb{R}^{m\times n}$ where $m<n$ and $rank(A) = m$, and vector $b\in \mathbb{R}^m$, find a solution $x\in \mathbb{R}^n$ such that $Ax=b$. (3 pts)
\noindent \\ 

\noindent
3.4. Given a nonsingular matrix
\begin{eqnarray}
A = \begin{bmatrix} 
a & b & c \\
d & e & f \\
g & h & i
\end{bmatrix},  \nonumber
\end{eqnarray}
write the analytic solution of $A^{-1}$. (4 pts)\\


\noindent
3.5. Given a nonsingular matrix
\begin{eqnarray}
M = \begin{bmatrix} 
A & B \\
C & D
\end{bmatrix},  \nonumber
\end{eqnarray}
where elements $A, B, C, D \in \mathbb{R}^{2 \times 2}$,
write an analytic solution of $M^{-1}$. 

\noindent
a. Assume that matrix $A$ is not singular. (2 pts)

\noindent
b. Assume that matrix $D$ is not singular. (2 pts)

\noindent
c. Assume that both matrices $A$ and $D$ are singular. (2 pts) \\

\noindent
3.6. Assume that matrix $A=[a_{i,j}]$ is not singular. Derive the analytical form of the derivative of $f$ over matrix $A$ (i.e. $[u_{i,j}]=\nabla_A f$, where $u_{i,j}= \partial f / \partial a_{i,j}$)  for function $f = tr A^{-1}$. (5 pts)\\

\noindent
4. How are the above three questions related to convex optimization? State your answer
in three sentences (one sentence for each question). (2 pts)

\end{document}