\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 W25 Homework 4} \\
\end{center}

\noindent{\textbf{Due Time : 11:50pm, Thursday Feb. 13, 2025}} 
        \textbf{Submit to Gradescope}  \\
        
{\bf In this homework, we work on exercises from the textbook. Problems 4.1, 4.8 and 4.11 are related to LP. Problems 4.21 and 4.39 are related to QCQP, and SDP. Problems 5.4, 5.5, 5.6, 5.8, and 5.9 are examples and applications of duality. Also, we practice using the convex optimization tools on a linear programming problem, and a semi-definite programming problem. \\

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

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

\indent
4.1, 4.8, 4.11, 4.21, 4.39, 5.4, 5.5, 5.6, 5.8, 5.9. \\

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

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

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

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

\begin{eqnarray}
c^T= \begin{bmatrix} 
-1 & -2 & -3 & -4 
\end{bmatrix}, \nonumber
\end{eqnarray}
and $n=4$, perform steps A, B, and C for problems II.1.1, II.1.2, II.1.3, and II.1.4.

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. 

\noindent
C. Compare the primal and dual solutions. If the primal and dual formulation solutions are different, explain the difference.

\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 Eigenvalue Optimization Problem} 
Eigenvalues of certain matrices are related to physical phenomenon in our world. For example, in mechanical structures, we have something called stiffness matrices, whose maximum eigenvalue corresponds to the highest frequency in the mechanical system. Hence, sometimes it is of utmost importance, that if the matrix is parametrized, we want the parameters in the matrix such that, the maximum eigenvalue of the matrix is minimized. (20 pts)

We will try to solve this problem for a certain class of parametrized matrices. Given symmetric matrices \(A_i \in S_n\) , Let \(F = \sum_i \alpha_i A_i\). We have to chose \(\alpha_i \in \mathbf{R}\) such that \(\alpha_i \geq 0\) and \(\sum_i \alpha_i = 1\).

(i) Let us order the eigenvalues of F from large to small, i.e. $\lambda_0 \geq \lambda_1 ... \geq \lambda_{n-1}$. Prove that for some \(t \in R\), if the matrix \(t\mathbf{I} -F \succeq 0\), then \(t \geq \lambda_0\). (Here \(\mathbf{I}\) is the identity matrix and \(\succeq\) means positive semi-definite)\\

(ii) Using the above result, the problem of minimizing the maximum eigenvalue becomes \\
\begin{equation}
\begin{aligned}
    &\:\:\:\:\:\:\:\: \min_{t,\alpha_i} t \\
    &\text{s.t.} \:\: \sum_i \alpha_i A_i  - tI \preceq 0, \\
    &\ \:\:\:\:\:\:\: \sum_i \alpha_i = 1, \\
    &\ \:\:\:\:\:\:\: \alpha_i \geq 0 
\end{aligned} \label{eq:linear}
\end{equation}.

Using the above formulation, derive the KKT conditions and the dual for this problem. (\(\preceq\) means negative semi-definite)

(iii) Now, let's try a concrete example, you may use any convex optimization package to solve the problem.

Given
\begin{eqnarray}
A_0 = \begin{bmatrix} 
-300 & 5 & -5 \\
5 & 4 & -1 \\
-5 & -1 & 4  \\
\end{bmatrix},  A_1 = \begin{bmatrix} 
-4 & -5 & 5 \\
-5 & 4 & 5 \\
5 & 5 & -4  \\
\end{bmatrix}, A_2 = \begin{bmatrix} 
4 & -5 & -5 \\
-5 & 2 & -3 \\
-5 & -3 & 2  \\
\end{bmatrix}
\end{eqnarray}
\\[-0.2in],

minimize the maximum eigenvalue for \(F = \alpha_0*A_0 + \alpha_1*A_1 + \alpha_2*A_2\), such that \(\alpha_i \geq 0\) and \(\sum_i \alpha_i = 1\).

Report the value of maximum eigenvalue of F after the optimization and also the values of \(\alpha_i\) which should be used to get that value.

\end{document}