\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} \usepackage{hyperref} \hypersetup{ colorlinks=true, linkcolor=blue, filecolor=magenta, urlcolor=blue, pdftitle={Overleaf Example}, pdfpagemode=FullScreen, } \begin{document} \begin{center} \textbf{CSE 203B W25 Homework 1} \\ \end{center} \noindent{\textbf{Due Time : 11:50pm, Thursday Jan. 16, 2025}} \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. You are free to use software tools to facilitate the calculation. However, you are also encouraged to go through the derivations manually wherever it is feasible because these concepts are fundamental and needed for the study of convex optimization.\\ \\ All the problems are graded by completion.\\ \\ You can work on Homework 1 in a group (each group can have up to four students). Make a single PDF submission to Gradescope and add all the members of your group to the submission. \\ \\ \underline{IMPORTANT:} Mention the contributions of all members towards the homework in the beginning of the Homework 1 report. }\\ \noindent {\bf 1. {Convex Optimization} (10 pts)}\\ 1.1. Given a function $f_0(x)= x^4 -2x^3+3x^2-2x-4$, where $x\in \mathbb{R}$. Solve $min_x f_0(x)$ using Kuhn-Tucker conditions. Show your derivation. (5 pts)\\ \noindent 1.2. Given two functions $f_0(x)= x^2-6x+9$, and $f_1(x)= 2x+3$, where $x\in \mathbb{R}$. Solve $min_x f_0(x)$ subject to $f_1(x) \leq 0$. (5 pts)\\ \noindent {\bf 2. {Matrix Properties} (16 pts)} \noindent 2.1. Linear System: Consider the following system of linear equations \begin{eqnarray} \nonumber x_1 &+ 2x_2 &+ 3x_3 = 1 \\ \nonumber x_1 &+ x_2 & +x_3 = -2 \\ \nonumber & x_2 &+ 2x_3 = 3. \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. Note that $det$ means determinant operator and $tr$ trace opeartor. (3 pts) \begin{itemize} \item{For $A, B \in \mathbb{R}^{n\times n}$, $detAB = detA \times detB$.} \item {For $A\in \mathbb{R}^{m\times n}, B\in \mathbb{R}^{n\times m}$, $trAB = trBA$.} \item{For $A \in \mathbb{R}^{n\times n}$, $detA = \prod_{i=1}^{n} \lambda_i$, and $trA= \sum_{i=1}^n \lambda_i$, where $\lambda_i, i=1, \dots, n$ are the eigenvalues of $A$.} \end{itemize} \noindent 2.6. Use the following example of matrices $A$ and $B$ to illustrate the equations in problem 2.5. (4 pts) \begin{eqnarray} A = \begin{bmatrix} -2 & -4 & 2 \\ -2 & 1 & 2 \\ 4 & 2 & 5 \end{bmatrix}, \nonumber ~B = \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \\ 2 & 1 & 3 \end{bmatrix}, \nonumber \end{eqnarray} \noindent \\ \noindent {\bf 3. {Matrix Operations} (24 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) = b^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 + 2b^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