\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}

\title{Методы Оптимизации д.з. 1}
\author{Piscenco Margarita, 797}
\date{September 2019}

\usepackage{natbib}
\usepackage{graphicx}
\pagestyle{empty}
\usepackage{amsthm}
\usepackage{amsmath}

\renewcommand\qedsymbol{$\blacksquare$}

\begin{document}
\maketitle

\Large
\section*{\LARGE Задача 1}

\paragraph{
\Large Док-ть,что $Tr(AB) = Tr(BA)\newline $
 Док-во:\newline \large Пусть \Large $  C := AB, D := BA. \newline
Tr(AB) = Tr(C) = \sum ^n_{i = 1} c_{i, i} =  \sum ^n_{i = 1}  \sum ^n_{j = 1} a_{i, j} b_{j, i} =  \sum ^n_{j = 1} \sum ^n_{i = 1} b_{j, i} a_{i, j} =  \sum ^n_{j = 1} d_{j, j} = Tr(D) = Tr(BA)$
}

\section*{\LARGE Задача 2}
\paragraph{\Large Док-ть,что $\forall A \in R^{m*k}, B \in R^{k*n}, C\in R^{m*n} $ \newline
$<AB, C> = <B, A^TC> = <A, CB^T>$\newline
Док-во:\newline
$<AB, C> =  \sum _{i=1}^m \sum _{j=1}^n \{AB\}_{i, j} c_{i,j} =
\sum _{i=1}^m \sum _{j=1}^n \sum _{l=1}^k a_{i,l}  b_{l,j}  c_{i,j}
=   \sum _{l=1}^k \sum _{j=1}^n  b_{l,j}  \sum _{i=1}^m a_{i,l}   c_{i,j} =
\sum _{l=1}^k \sum _{j=1}^n  b_{l,j} \{A^T\}_{l,i}  c_{i,j}= \newline
 \sum _{l=1}^k \sum _{j=1}^n  b_{l,j} \{A^TC\}_{l,j} = <B, A^TC>
 $\newline
 \large Аналогично \Large $<AB, C> = \sum _{l=1}^k \sum _{j=1}^n \sum _{i=1}^m a_{i,l} b_{l,j}   c_{i,j} =  \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \sum_{j=1}^n c_{i,j} b_{l,j} =
 \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \sum_{j=1}^n c_{i,j} B^T_{j,l} =
 \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \{ CB^T\}_{i, l}
 $
}
\newpage
\section*{\LARGE Задача 3}
\paragraph{  \Large Пусть $x,y \in R^n$. Док-ть,что $<xx^T, yy^T> = <x, y>^2$\newline
Док-во:\newline
 $<xx^T, yy^T> =$ \newline}
 {<}
 $\begin{pmatrix}
  \ x_{1}\\
  \ ...\\
  \ x_n
\end{pmatrix}
$
$
\begin{pmatrix}
  \ x_{1} &\ ... &\ x_n
\end{pmatrix}
$
{,}
 $\begin{pmatrix}
  \ y_{1}\\
  \ ...\\
  \ y_n
\end{pmatrix}
$
$
\begin{pmatrix}
  \ y_{1} &\ ... &\ y_n
\end{pmatrix}
$
{> = \newline}

{<}
 $\begin{pmatrix}
  \ x_{1}^2 &\ ... &\ x_1 x_n\\
  \ . &\ . &\ . \\
  \ x_n x_1 &\ ...&\ x_n^2
\end{pmatrix}
$
{,}
 $\begin{pmatrix}
  \ y_{1}^2 &\ ... &\ y_1 y_n\\
  \ . &\ . &\ . \\
  \ y_n y_1 &\ ...&\ y_n^2
\end{pmatrix}
$
{> =
$\sum_{i = 1}^n \sum_{j = 1}^n  x_i x_j y_i y_j$}


\paragraph{\Large $<x, y>^2 =  (\sum _{i = 1}^n x_i y_i)^2 = \sum_{i = 1}^n \sum_{j = 1}^n  x_i x_j y_i y_j $
}

\section*{\LARGE Задача 4}
\paragraph{ \Large Док-ть неравенство Коши-Буняковского.\newline
Док-во:\newline
$<x, y> \in R, \forall \lambda \in R $\newline
$0 \leq < \lambda x + y, \lambda x+y > = \newline \lambda^2<x, x> +2\lambda <x, y> + <y, y> => D\leq 0$
$D = 4<x, y>^2 - 4<x, x><y, y> \leq  0 => \newline
|<x, y>| \leq <x, x>^{1/2} <y, y>^{1/2}$ \newline
Равенство при $y = 0$ и $x= \alpha y$ очевидно. Докажем, что в других случаях равенство строгое.\newline
$D = 4<x, y>^2 - 4<x, x><y, y> < 0, \newline
<x, y>^2  < <x, x><y, y> $, что выполняется при заявленных условиях.
}
\newpage
\section*{\LARGE Задача 5}
\paragraph{ \Large Док-ть:\newline
$||x||_{\infty} \leq ||x||_2 \leq \sqrt{n} ||x||_\infty  $\newline
$ \frac{1}{\sqrt{n}}||x||_{1} \leq ||x||_2 \leq ||x||_1 $\newline
Док-во:
}
\begin{multline*}
\ ||x||_{\infty} = max_{1\leq i \leq n}|x_i| \leq |x_{max}|  + (\sum _{i \neq i_{max}} x_i^2)^{1/2} =(\sum _{i=0} ^{n} x_i^2)^{1/2} =  ||x||_2
\\||x||_2 = (\sum _{i=0} ^{n} x_i^2)^{1/2} \leq (\sum _{i=0} ^{n} x_{max}^2)^{1/2} =
(n  x_{max}^2)^{1/2}   = \sqrt{n} ||x||_\infty
\\ \frac{1}{\sqrt{n}}||x||_{1} = \frac{1}{\sqrt{n}} \sum _{i=1}^n |x_i| =
\frac{1}{\sqrt{n}}  \sum _{i=1}^n \sqrt{<x_i, x_i>} ????
\\ ||x||_{1} = \sum _{i=1}^n |x_i| \geq (\sum _{i=0} ^{n} x_i^2)^{1/2} = ||x||_2
\end{multline*}
\section*{\LARGE Задача 6}
\paragraph{ \Large Док-ть:\newline
Док-во:
}
\newpage
\section*{\LARGE Задача 7}
\paragraph{ \Large  Найти $d, d^2$:\newline
1) $A \in R^{n*n} f(t) := Det(A - tI_n) $  \newline
$  d(Det(A - tI_n)) =  Det(A - tI_n) <(A - tI_n)^{-T}, d(A - tI_n)> =
Det(A - tI_n) <(A - tI_n)^{-T}, -I_n dt_1> =  - Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_1> \newline \newline
 d^2(Det(A - tI_n)) =  d(- Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_1>) =
 - d(Det(A - tI_n))  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) d( <(A - tI_n)^{-T}, I_n dt_1>) =
 - Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) <d(A - tI_n)^{-T}, I_n dt_1> =
 - Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) <(d(A - tI_n)^{-1})^T, I_n dt_1> =
 - Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) <(-(A - tI_n)^{-1}) (-I_n dt_2)(A - tI_n)^{-1})^{T}, I_n dt_1> =
 - Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) <(A - tI_n)^{-1} (I_n dt_2)(A - tI_n)^{-1})^{T}, I_n dt_1>
 \newline \newline$
 2) $ A \in S^{n}_+, b \in R^n,  f(t) := |(A+tI_n)^{-1}b|^2 \newline
 d(|(A+tI_n)^{-1}b|^2 ) = 2  |(A+tI_n)^{-1}b| * d(|(A+tI_n)^{-1}b| ) =
 2  |(A+tI_n)^{-1}b| * d((A+tI_n)^{-1}b) *(A+tI_n)^{-1}b /(|(A+tI_n)^{-1}b|)
 =  2  * d((A+tI_n)^{-1}b) *(A+tI_n)^{-1}b =
  2  * (d(A+tI_n)^{-1}b) *(A+tI_n)^{-1}b =
   2  * (-(A+tI_n)^{-1} d(A+tI_n)(A+tI_n)^{-1} b) *(A+tI_n)^{-1}b =
   2  * (-(A+tI_n)^{-1} I_n dt_1 (A+tI_n)^{-1} b) *(A+tI_n)^{-1}b = (A+tI_n)^{-3}*b *dt_1
$ \newline \newline
 $ d(- 2  * (A+tI_n)^{-3}*b*dt_1) = -2 * (-3) * (A+tI_n)^2 * d(A+tI_n) *b*dt_1 =  6 * (A+tI_n)^2*b *dt_1*dt_2$
}
\newpage
\section*{\LARGE Задача 8}
\paragraph{ \Large Найти $\nabla f$ и $\nabla^2 f$:\newline
1)
$f = 1/2||xx^T-A ||^2_F, A \in S^n$ \newline
$ f = 1/2||xx^T-A ||^2_F = 1/2 \sum _{i = 1}^n \sum _{j = 1}^n x_ix_j - a_{i, j}^2 =
\newline \nabla f = (1/2(\sum _{i=1}^n (x_i - a_{i, 1}) + \sum _{j = 2}^n (x_j - a_{1,j})), ..., \newline 1/2(\sum _{i=1}^n (x_i - a_{i, k}) + \sum _{j \neq k}(x_j - a_{k,j})), ...) $\newline
$H(f) = $
}
 \begin{pmatrix}
  \ \frac{\partial  f}{\partial x_1^2} &\ ... &\  \frac{\partial^2 f}{\partial x_1 \partial x_n }\\
  \ . &\ . &\ . \\
  \ \frac{\partial  f}{\partial x_1x_n} &\ ... &\  \frac{\partial^2 f}{\partial x_n^2 }\\
\end{pmatrix}
\paragraph{\Large $\frac{\partial^2 f}{\partial x_i \partial x_j } = 1/2 \xrightarrow{} $ $\nabla^2 f = H(f) = 1/2 I_n$}


\end{document}