\chapter{    نتایجی در مسائل نقطه زینی}

\section{مقدمه}
\glspl{gsp}
\begin{equation}
\label{saddle}
\mathcal{A}u\equiv  \begin{bmatrix}
{A}&{B^*}\\{-B}&{C}
\end{bmatrix}
 \begin{bmatrix}{x}\\{y}\end{bmatrix} =  \begin{bmatrix}{f}\\{g}\end{bmatrix}\equiv b,
\end{equation}
را در نظر بگیرید که در آن 
$A \in \mathbb{C}^{n\times n}$ و $C \in \mathbb{C}^{m\times m}$ 
نیمه معین مثبت غیر هرمیتی، 
$ B \in  \mathbb{C}^{m \times n} $   $(m\leq n)$,   $f \in \mathbb {C}^n$ و  $g \in \mathbb{C}^m$. 
فرض می‌کنیم ماتریس‌های 
$A$، $B$ و $C$ 
تنک و از ابعاد بزرگ هستند.  
\glspl{gsp}
 دارای کاربردهای متنوعی در علوم و مهندسی می‌باشند 
(\cite{bai752006, benzi262004} را ببینید). 

	فرض کنید $D$  یک ماتریس نیمه معین منفی و 
	$A$
	یک ماتریس نیمه معین مثبت باشد.  آنگاه 
	\gls{spp} 
	\begin{align*}
	\begin{bmatrix} A&B^*\\B&D	\end{bmatrix}
	\begin{bmatrix}x\\y  	\end{bmatrix}
	=\begin{bmatrix}f\\h\end{bmatrix},
	\end{align*}
	با انتخاب 
	$g=-h$  و  $C=-D$
	و
	\gls{spp}	
	\begin{align*}
	\begin{bmatrix} A&-D^*\\D&C	\end{bmatrix}
	\begin{bmatrix}x\\z  	\end{bmatrix}
	=\begin{bmatrix}f\\g\end{bmatrix},
	\end{align*}
	با انتخاب 
	 $B=-D$
	به 
	\gls{gsp}
	 \eqref{saddle}  تبدیل می‌شود.  از این رو،   فقط به حل 
	 \glspl{gsp}
	  به صورت \eqref{saddle}  می‌پردازیم.
	
در این فصل، ابتدا  کاربردهایی از 
\glspl{gsp}
 را بیان می‌کنیم.  سپس به بررسی وجود و یکتایی جواب این مسائل می‌پردازیم و شرایط لازم و کافی را برای وجود و یکتایی جواب ارائه می‌کنیم. پس از آن، برخی از روش‌ها و پیش‌شرط‌‌سازهای مختلفی را که برای حل این‌گونه مسائل معرفی شده‌اند، مورد مطالعه قرار داده و چند روش جدید     را برای حل \glspl{spp} 
\eqref{saddle}
ارائه می‌دهیم. سپس روش تکراری 
$\EPSS$  
و پیش‌شرط‌ساز وابسته به آن  را برای حل مسائل نقطه زینی تعمیم‌یافته معرفی می‌کنیم.  
 همگرایی و نیمه همگرایی این روش، مورد بررسی قرار می‌گیرد. سپس به ذکر برخی از روش‌هایی می‌پردازیم که  حالت‌های خاصی از این روش می‌باشند. بنابراین، همگرایی و نیمه همگرایی این روش‌ها نیز اثبات می‌گردد.  یکی از  حالت‌های ویژه از این روش را مورد مطالعه قرار داده و نتایجی را برای آن به دست می‌آوریم. با استفاده از مثال‌های  عددی، رفتار و عملکرد این روش با برخی روش‌های دیگر مورد مقایسه قرار خواهد گرفت. 

\section{برخی از کاربرد‌ها }
در این بخش  به  برخی از کاربردهای  مسائل  نقطه زینی اشاره می‌کنیم.  
 \subsection{مسائل بهینه‌سازی نقطه زینی }
	مساله‌ی برنامه‌ریزی درجه دوم مقید   
	\begin{align}
	\label{optpro}
	&\mathop{\min}\limits_{x \in \mathbb{R}^n} \text{~~}f(x)= \frac{1}{2} x^TAx -c^Tx, \nonumber\\
	& s.t.\qquad  B^Tx=d,
	\end{align}
	 را در نظر بگیرید که در آن 
	$A \in \mathbb{R}^{n\times n}$ 
	یک ماتریس معین مثبت متقارن،  
	$B \in \mathbb{R}^{n\times m}$
	یک ماتریس رتبه کامل سطری،
	$c \in \mathbb{R}^n$
	و 
	$d \in \mathbb{ R}^m$
	است.
	تابع لاگرانژ\LTRfootnote{Lagrangian}
	آن  به صورت  
	\begin{align*}
	\mathcal{L}(x,y)&=f(x)+y^T(B^Tx-d)=\frac{1}{2}x^T A x+x^T B y-x^Tc-y^Td \\
	&=\frac{1}{2}\begin{bmatrix}{x}\\{y}\end{bmatrix} ^T \begin{bmatrix}{A}&{B}\\{B^T}&{0}\end{bmatrix}  \begin{bmatrix}{x}\\{y}\end{bmatrix} -\begin{bmatrix}{x}\\{y}\end{bmatrix} ^T \begin{bmatrix}c&d\end{bmatrix},
	\end{align*}  
	تعریف می‌شود. به ازای هر 
	$x \in \mathbb{R}^n$
	و هر 
	$y \in \mathbb{R}^m$،
	داریم  
	\begin{align*}
	\mathcal{L}(x,y)&=\sum _{i=1}^n x_i \left( \sum _{j=1}^n A_{i,j}x_j+\sum _{k=1}^m B_{ik}y_k-c_i \right)-\sum_{k=1}^m y_kd_k\\
	&=\sum _{i=1}^n x_i \left( \sum _{j=1}^n A_{i,j}x_j-c_i \right)-\sum_{k=1}^m y_k \left( \sum _{j=1}^n B_{k,j}^Tx_j-d_k \right).
	\end{align*} 
	
	بنابراین 
	\begin{align*}
	\frac{\partial \mathcal{L}}{\partial x_j}(x,y)&=e_j^T(Ax+By-c), \, j=1, \cdots, n,\\
	\frac{\partial \mathcal{L}}{\partial y_k}(x,y)&=-e_k^T(B^Tx-d), \, k=1, \cdots, m.
	\end{align*}
	لذا اولین شرط بهینگی بصورت 
	\begin{align*}
	Ax+By-c&=0, \\
	-B^Tx+d&=0.
	\end{align*}
	 خواهد بود که معادل با حل دستگاه 
	\begin{align}
	\label{optcond}
	\begin{bmatrix}{A}&{B}\\{B^T}&{0}\end{bmatrix}\begin{bmatrix}{x}\\{y}\end{bmatrix} -\begin{bmatrix}c\\d\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix},
	\end{align}
	می‌باشد. اگر  
	$[{x_*;y_*}]$
	جواب دستگاه  
	\eqref{optcond}
	باشد، آنگاه 
	\begin{align*}
	\mathcal{L}(x_* , y_*)&=\frac{1}{2}\begin{bmatrix}x_*\\y_*\end{bmatrix} ^T \begin{bmatrix}{A}&{B}\\{B^T}&{0}\end{bmatrix} \begin{bmatrix}x_*\\y_*\end{bmatrix} -\begin{bmatrix}x_*\\y_*\end{bmatrix}^T \begin{bmatrix}c\\d\end{bmatrix} \\
	&=\frac{-1}{2}\begin{bmatrix}x_*\\y_*\end{bmatrix} ^T \begin{bmatrix}{A}&{B}\\{B^T}&{0}\end{bmatrix} \begin{bmatrix}x_*\\y_*\end{bmatrix}.
	\end{align*} 
	در نتیجه به ازای هر 
	$x \in \mathbb{R}^n$
	و
	$y\in \mathbb{R}^m$  
	داریم 
	\begin{align*}
	\mathcal{L}(x, y)-\mathcal{L}(x_* , y_*)&=\frac{1}{2}\left(\begin{bmatrix}{x}\\{y}\end{bmatrix} -\begin{bmatrix}x_*\\y_*\end{bmatrix} \right)^T \begin{bmatrix}{A}&{B}\\{B^T}&{0}\end{bmatrix} \left(\begin{bmatrix}{x}\\{y}\end{bmatrix} -\begin{bmatrix}x_*\\y_*\end{bmatrix} \right) .
	\end{align*}
	حال اگر 
	$y=y_*$، آنگاه 
	\begin{align*}
	\mathcal{L}(x, y_*)-\mathcal{L}(x_* , y_*)&=\frac{1}{2}(x-x_*)^T   {A}  (x-x_*) \geq 0,
	\end{align*}
	و اگر 
	$x=x_*$، آنگاه 
	\begin{align*}
	\mathcal{L}(x_*, y)-\mathcal{L}(x_* , y_*)= 0.
	\end{align*}
	بنابراین برای  هر 
	$x \in \mathbb{R}^n$
	و
	$y\in \mathbb{R}^m$،  
	داریم 
	\begin{align*}
	\mathcal{L}(x_*, y)\leq  \mathcal{L}(x_* , y_*) \leq \mathcal{L}(x, y_*).
	\end{align*}
	از این رو 
	\[
	\max_{y \in   \mathcal{R}^m} \min_{x \in \mathcal{R}^n}  \mathcal{L}(x, y) =\mathcal{L}(x_*, y_*)=\min_{x \in \mathcal{R}^n} \max_{y \in   \mathcal{R}^m} \mathcal{L}(x, y).
	\]  
	لذا  هر جواب دستگاه 
	\eqref{optcond}
	بصورت 
	$[{x_*;y_*}]$
	یک نقطه زینی برای تابع لاگرانژین 
	$\mathcal{L}(x, y) $  
	می‌باشد که بردار $x_*$ آن جواب مساله‌ی  
	\eqref{optpro}
	می‌باشد. 
	\subsection{مسائل   کم‌ترین مربعات}
	دسته‌ای از مسائل کم‌ترین مربعات وجود دارند که به حل 
	\glspl{spp}
	 ارتباط پیدا می‌کنند. 
 \begin{enumerate}[1)]
 	\item
	فرض کنید $B \in \mathbb{R}^{n \times n}$ و $b \in \mathbb{R}^n$. مسأله‌ی کم‌ترین توان‌های دوم 
\begin{align*}
\norm{Bx_*-b}=\min_{x \in \mathbb{R}^n} \norm{Bx-b},
\end{align*}
را در نظر بگیرید.  $x_*$  جواب این مسأله است اگر و تنها اگر  در دستگاه معادلات خطی
\begin{equation*}
B^TBx=B^Tb,
\end{equation*}
  صدق کند. معادله‌ی فوق را دستگاه معادلات نرمال می‌گویند که  معادل  با
\begin{equation*}
B^T(b-Bx)=0,
\end{equation*}
است. با فرض $r=b-Bx$ داریم $B^Tr=0$. در نتیجه داریم 
\begin{align*}
\begin{cases}
r+Bx=b, \\ 
B^Tr=0 ,
\end{cases}
\end{align*}
که معادل با مسأله‌ی نقطه زینی زیر است 
\begin{align*}\label{optisys2}
 \begin{bmatrix} 
	I&B\\
	B^T&0
	\end{bmatrix} \begin{bmatrix}
r\\ 
x \\ 
\end{bmatrix} =  \begin{bmatrix}
b\\ 
0\\ 
\end{bmatrix}.         
\end{align*}
\item
مسأله‌ی محاسبه‌ی مینیمم نرم جواب $x_*\in \mathbb{ R}^m$، برای یک سیستم نامشخص از دستگاه معادلات خطی 
 \begin{align*}
 	&\norm{x_*}=\min_{x\in \mathbb{ R}^{ m}}  \norm{x},\\ 
 	&~\text{s.t. }~~~~{B^Tx=d},
 \end{align*}
 که در آن 
 $B\in \mathbb{ R}^{m\times n}$  و $d\in \mathbb{ R}^{ n}$.
 اگر  
 $\text{\rm rank}(B)=n$،
 آنگاه $B^Tx=d$ سازگار  و    دارای جواب یکتاست  و این جواب  با استفاده از حل  معادلات نرمال 
  \begin{align}
  B^TBy=d, ~~~~x=By,
  \end{align}
 به دست می‌آید که معادل با مسأله‌ی نقطه زینی زیر است 
 \begin{align}\label{optisys3}
 \begin{bmatrix} 
 I&B\\
 B^T&0
 \end{bmatrix} \begin{bmatrix}
 x\\ 
 y \\ 
 \end{bmatrix} =  \begin{bmatrix}
 0\\ 
 d\\ 
 \end{bmatrix}.     
 \end{align}
 \item 
 مسأله‌ی کم‌ترین مربعات مقید
 \begin{align*}
&\norm{c-By_*}=\min_{y \in \mathbb{R}^n}\norm{c-By},\\
&~~~~~~~\text{s.t.}   ~~~~~~~~Cy=d,
 \end{align*}
 را در نظر بگیرید که به حل مسأله‌ی نقطه زینی 
 \begin{align*}
 	\begin{bmatrix}
 	I&0&B\\0&0&C\\B^T&C^T&0
 	\end{bmatrix}\begin{bmatrix}
 	x\\y\\z
 	\end{bmatrix}=\begin{bmatrix}
 	c\\d\\0
 	\end{bmatrix},
 \end{align*}
 منجر می‌شود. 

 \item 
 فرض کنید 
 $A$  ماتریس معین مثبت متقارن  و 
 $\text{\rm rank} (B)=n$ و 
 $c \in \mathbb{ R}^m$.
 چون ماتریس $A$ معین مثبت متقارن است، پس 
 $A^{-1}$ 
 نیز یک ماتریس معین مثبت متقارن است و می‌توانیم مسأله‌ی کم‌ترین مربعات کلی  
  \begin{align*}
 &\|{c-By_*}\|_{A^{-1}}=\min_{y \in \mathbb{R}^n}\|{c-By}\|_{A^{-1}},\\
 &~~~~~~~~\text{s.t }~~~~~~Cy=d,
 \end{align*}
  را در نظر بگیریم    که جواب آن از حل معادله‌ی نرمال 
 $B^TA^{-1}By=B^TA^{-1}c$
 به دست می‌آید. 
 با فرض 
 $x=A^{-1}(c-By)$ 
 معادلات نرمال این مسأله با مسأله‌ی نقطه زینی 
 \begin{align*}
 \begin{bmatrix}
 A&B\\B^T&0
 \end{bmatrix}\begin{bmatrix}
 x\\y 
 \end{bmatrix}=\begin{bmatrix}
 c\\0
 \end{bmatrix},
 \end{align*}
 معادل می‌شود.
 \end{enumerate}
 
 