%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Please do not change the following statements. You must start from line 43 "==>start from here"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt, reqno]{amsart}
\usepackage{amsmath, amsthm, amscd, amsfonts, amssymb, graphicx, color}
\usepackage[bookmarksnumbered, colorlinks, plainpages]{hyperref}
%\usepackage{enumitem}
%\usepackage{multirow}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% If you want to insert other packages. Insert them here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\makeatletter \oddsidemargin.9375in \evensidemargin \oddsidemargin
\marginparwidth1.9375in \makeatother

\def\affilfont{\normalfont\fontsize{10}{12}\selectfont\centering}
\def\affil#1{\par\vskip12pt{\affilfont#1\par}\vskip15pt}
\def\Speaker{$^{*}$\protect\footnotetext{$^{*}$ S\lowercase{peaker.}}}
\def\authorsaddresses#1{\dedicatory{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{xca}[theorem]{Exercise}
%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}
%\numberwithin{equation}{section}
%
\begin{document}
%\setcounter{page}{1}
%\pagenumbering{gobble}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% ==>start from here
%% Start from here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Insert title of your article. Note: \title[short title]{full title}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[quadratic L-shaped algorithm for SLP]{A quadratic L-shaped algorithm for two-stage stochastic linear programming (SLP)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author's name must be inserted here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\author[Ketabchi and Behboodi]{Saeed Ketabchi$^1$ and Malihe Behboodi Kahoo$^2$\Speaker}

%%%%%%%%%%%%%%%%%%%%%%%%
% Addresses
%%%%%%%%%%%%%%%%%%%%%%%%
\authorsaddresses{$^{1,2}$ Department of Applied Mathematics, Faculty of Mathematical Sciences, University
of Guilan, P. O. Box 416351914, Rasht, Iran;\\  $^1$ sketabchi@guilan.ac.ir,\\ $^2$ behboodi.m@webmail.guilan.ac.ir\\}
%\vspace{0.5cm} $^2$ Department of Applied Mathematics, University
%of Guilan, P. O. Box 416351914, Rasht, Iran;\\  behboodi.m@webmail.guilan.ac.ir\\}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Subject class; see http://www.ams.org/mathscinet/msc/msc2010.html
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subjclass[2010]{90C15,  90C05, 90C20.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% keywords; Note that the number of keywords must be at least 3 items and at most 5 items.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\keywords{Hilbert space, local cohomology, semi-Fredholm operator
%(at least 3 and at most 5 items).}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\keywords{Two-stage stochastic linear programming,  Recourse problem, L-shaped method, Augmented Lagrangian method.}
% \PACS{PACS code1 \and PACS code2 \and more}
% \subclass{ 90C15 \and  90C05 \and 90C20.}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
Stochastic programming is a technique for optimization in the presence of uncertainty which typically leads to very large problem sizes.
Here, we present a modified version of the L-shaped method and reduce  linear master and linear recourse programs  to  unconstrained
maximization of  concave differentiable piecewise quadratic functions.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%
% The body of your extended abstract
%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Note that The number of
%% pages of the extended abstract should have 3-4 pages. Papers prepared
%% in less than 3 pages, more than 4 pages or out of the style of the conference will be
%% returned

\section{Introduction}

In mathematical linear programming, matrix of coefficients and vectors are exact values. However, in practice, the problem data are not definite because of many reasons like error in measurement, incomplete information about future and events which have not occurred yet. In stochastic programming, some data are random variables with a specific possibility distribution.
Before presenting the mathematical formulation of the two-stage stochastic linear program (SLP) model, we introduce
some notation. Let $(\Omega; \vartheta; P)$ be a discrete probability space and consider
$\Omega = \{\omega_1,\omega_2,\ldots,\omega_N\}$ as the set of scenarios with associated probabilities $\{\rho_1,\rho_2,\ldots,\rho_N\}$ such
that $\sum_{i=1}^{N}\rho_i = 1$.
In this paper, consider the following two-stage stochastic linear program (SLP) with fixed recourse and a finite number of scenarios \cite{kall wallace}:
\begin{eqnarray}\label{slp}
\min_{x\in X} \ \ f(x)=c^T x+\phi(x), \ \ \  X=\{x\in \mathbb{R}^{n}: Ax=b, x\geq 0\},
\end{eqnarray}
where
\begin{eqnarray*}
\phi(x)=E(Q(x,\omega))=\sum_{i=1}^{N} Q(x,\omega_i)\rho_i,
\end{eqnarray*}
and



in which $\beta , \hat{y} $  are constants and
\begin{eqnarray}\label{s}
S(p,\beta , \hat{y})= (h - T x^\nu)^T p -\frac{1}{2} \|(\hat{y}+ W^T p-\beta \hat{q})_{+}\|^2 .
\end{eqnarray}
Also, assume that the solution set $Y_{\ast}$ of (\ref{recourse}) is non-empty and the rank of sub-matrix $W_l$ of $W$ corresponding to nonzero components of $\hat{y}_{\ast}$ (the projection of  $\hat{y}$ on $Y_{\ast}$ ) is $m_2$.
In such a case, there is  $\beta^{\ast}$ which for all $\beta\geq\beta^{\ast}$, $\hat{y}_{\ast}=(\hat{y}+W^T p(\beta)-\beta \hat{q})_{+}$ where $p(\beta)$  is the point obtained from solving (\ref{ps}).

$$
\Delta_1 = \|Ax-b\|_\infty, \Delta_2 = {\max_i} \ \|T_i x + W y_i - h_i\|_\infty, \Delta_3 = |c^T x +  \sum_{i=1}^{N} \hat{q_i} y_{i}-f^*|,
$$
% The optimality conditions for solution of (\ref{eq:slp})
%are
%\begin{eqnarray*}
%\left\{
%  \begin{array}{l}
%  f(x) = c^T x +  \sum_{i=1}^{N} \hat{q_i} y_{i} = f^*\\
% A x = b,  \\
%T_i x  + W y_i = h_i, ~~~~  i = 1, \ldots, N, \\
% x\geq 0, \  y_i\geq 0, ~~~~  i = 1, \ldots, N,
%  \end{array}
%\right.
%\end{eqnarray*}
where $f^*$ is the optimal value of  (\ref{eq:slp}). Also, $d$ and $d_2$ are the density of matrices $A$ and $W$ respectively.

%In Table 1,
%the nonnegativity conditions are always satisfied. Therefore, these conditions are eliminated.
%\begin{center}
% \begin{table}[ht] %\centering
%\small
%\caption{Comparative between quadratic L-shaped method (QLM)  and linear L-shaped method (LLM)}
%%\resizebox{15cm}{13cm} {
%\scalebox{0.8}{
%\begin{tabular}{|c|c|c |c| c| c|c|}

%\hline\noalign{\smallskip}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...


%     \multirow{2}{*}{$500\times 5e3\times 0.1$} &\multirow{2}{*}{$200\times 1e3\times.1$} &\bf{ALM}&
% 3.3651e-10  & 7.6398e-11  & 3.5390e-08  &  24.995  \\ \cline{3-7}
%  & &\bf{linprog} &  out  &      &     &  \\\hline
%
%
%
%     \multirow{2}{*}{$100\times 1e4\times 0.001$} &\multirow{2}{*}{$200\times 2e4\times 0.1$} &\bf{ALM}&
%   1.2369e-10 &  5.7480e-10  & 6.7055e-08    & 2.898  \\ \cline{3-7}
%  & &\bf{linprog} &    1.1350e-09 &  2.6829e-06  & 1.4901e-08   &  159.846\\\hline
%
%     \multirow{2}{*}{$1000  \times 1e5  \times 0.001$} &\multirow{2}{*}{$1000  \times 1e5  \times 0.001$} &\bf{ALM}&
%   5.8208e-11 &  4.5475e-11 &  1.4901e-08    &  9.316  \\ \cline{3-7}
%  & &\bf{linprog} &    1 5.0495e-09  & 1.2866e-07  & 8.9407e-08   &  20.944\\\hline


% \textbf{Before submitting your extended abstract to the












%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% References
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{amsplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Please cite your relevant papers but at most total 5 papers/books.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{5}
\bibitem{modifi L-shaped}
J. Abaffy and E. Allevi, \textit{A modified L-Shaped method}, J. Optim. Theory  Appl.  123 (2004), No. 2,  255�-270.
\bibitem{kall wallace}
 P. Kall and S. W. Wallace, \textit{ Stochastic programming}, John Wiley and Sons, (1994).

\bibitem{behboodi} S. Ketabchi and M. Behboodi-Kahoo, \textit{Augmented Lagrangian method  for  recourse problem of two-stage stochastic linear programming}, Kybernetika 2 (2013) no. 1, 188--198.

\bibitem{L-shaped}
R. M. Van Slyke and R. Wets, \textit{L-Shaped linear programs with applications to optimal control and stochastic programming}, Siam J. Appl. Math. 17 (1969) 638-663.

\end{thebibliography}

\end{document}