\newcommand{\thistitle}{Lecture 7: Optimisation}

\input{title.tex}


\section{Optimisation: Motivation}



\begin{frame}
  \frametitle{What to do about variable renewables?}

  Backup energy costs money and may also cause CO${}_2$ emissions.

  Curtailing renewable energy is also a waste.

  We consider \alert{four options} to deal with variable renewables:
  \begin{enumerate}
  \item Smoothing stochastic variations of renewable feed-in over \alert{larger areas}, e.g. the whole of European continent.
  \item Using \alert{storage} to shift energy from times of surplus to deficit.
  \item \alert{Shifting demand} to different times, when renewables are abundant.
    \item Consuming the electricity in \alert{other sectors}, e.g. transport or heating.
  \end{enumerate}

\alert{Optimisation} in energy networks is a tool to assess these options.


\end{frame}


\begin{frame}
  \frametitle{Why optimisation?}

  In the energy system we have lots of \alert{degrees of freedom}:
  \begin{enumerate}
  \item Power plant and storage dispatch
  \item Renewables curtailment
  \item Dispatch of network elements (e.g. High Voltage Direct Current (HVDC) lines)
    \item Capacities of everything when considering investment
  \end{enumerate}
  but we also have to respect \alert{physical constraints}:
  \begin{enumerate}
    \item Meet energy demand
  \item Do not overload generators or storage
    \item Do not overload network
  \end{enumerate}
  and we want to do this while \alert{minimising costs}. Solution: \alert{optimisation}.

\end{frame}


\section{Optimisation: Introduction}

\begin{frame}
  \frametitle{Simplest 1-d optimisation problem}

  Consider the following problem. We have a function $f(x)$ of one variable $x \in \mathbb{R}$
  \begin{equation*}
    f(x) = (x-2)^2
  \end{equation*}
  Where does it reach a minimum? School technique: find stationary point $\frac{df}{dx} = 2(x-2) = 0$, i.e. minimum at $x^* = 2$ where $f(x^*)=0$.

  \centering
  \includegraphics[width=7.5cm]{quadratic}
\end{frame}



\begin{frame}
  \frametitle{Simplest 1-d optimisation problem}

  Consider the following problem. We have a function $f(x)$ of one variable $x \in \mathbb{R}$
  \begin{equation*}
    f(x) = x^3 -4x^2+3x +4
  \end{equation*}
  Where does it reach a minimum? School technique fails since has two stationary points, one local minimum and local maximum; must check 2nd derivative for minimum/maximum. Also: function is not bounded as $x \to -\infty$.  No solution!

  \centering
  \includegraphics[width=7cm]{cubic}
\end{frame}

\begin{frame}
  \frametitle{Beware saddle points in higher dimensions}

  Some functions have \alert{saddle points} with zero derivative in all directions (stationary points) but that are neither maxima nor minima, e.g. $f(x,y) = x^2 - y^2$ at $(x,y) = (0,0)$.

  \centering
  \includegraphics[width=8cm]{Saddle_point.png}

  \source{Wikipedia}

\end{frame}

\begin{frame}
  \frametitle{Simplest 1-d optimisation problem}

  Consider the following problem. We have a function $f(x)$ of one variable $x \in \mathbb{R}$
  \begin{equation*}
    f(x) = x^4 -4x^2+x +5
  \end{equation*}
  Where does it reach a minimum? Now two separate local minima. Function is \alert{not convex} downward. This is a problem for algorithms that only search for minima locally.

  \centering
  \includegraphics[width=7.5cm]{quartic}
\end{frame}


\begin{frame}
  \frametitle{Simplest 1-d optimisation problem with constraint}

  Consider the following problem. We minimise a function of one variable $x \in \mathbb{R}$
  \begin{equation*}
      \min_x (x-2)^2
  \end{equation*}
  subject to a constraint
  \begin{equation*}
       x \geq 1
  \end{equation*}
  The constraint has \alert{no effect} on the solution. It is \alert{non-binding}.

  \centering
  \includegraphics[width=7cm]{quadratic-gt1}
\end{frame}

\begin{frame}
  \frametitle{Simplest 1-d optimisation problem with constraint}

  Consider the following problem. We minimise a function of one variable $x \in \mathbb{R}$
  \begin{equation*}
      \min_x (x-2)^2
  \end{equation*}
  subject to a constraint
  \begin{equation*}
       x \geq 3
  \end{equation*}
  Now the constraint is \alert{binding} and is \alert{saturated} at the optimum $x^* = 3$.

  \centering
  \includegraphics[width=7cm]{quadratic-gt3}
\end{frame}


\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  Consider the following problem. We have a function $f(x,y)$ of two variables $x,y\in \mathbb{R}$
  \begin{equation*}
    f(x,y) = 3x
  \end{equation*}
  and we want to find the maximum of this function in the $x-y$ plane
  \begin{equation*}
    \max_{x,y\in \mathbb{R}} f(x,y)
  \end{equation*}
  subject to the following constraints
  \begin{align}
    x + y & \leq 4 \\
    x & \geq 0 \\
    y & \geq 1
  \end{align}
\end{frame}


\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  Consider $x-y$ plane of our variables:

  \centering
  \includegraphics[width=7cm]{2dsimple-b.pdf}
\end{frame}



\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  Add constraints (2) and (3):

  \centering
  \includegraphics[width=7cm]{2dsimple-c.pdf}
\end{frame}


\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  Add constraint (1).   In this allowed space (white area) what is the maximum of $f(x,y) = 3x$?


  \centering
  \includegraphics[width=7cm]{2dsimple-d.pdf}
\end{frame}


\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  $f(x,y) = 3x$ maximised at $x^* = 3, y^* = 1, f(x^*, y^*) = 9$:

  \centering
  \includegraphics[width=7cm]{2dsimple.pdf}
\end{frame}



\begin{frame}
  \frametitle{Simple 2-d optimisation problem}

  Consider the following problem. We have a function $f(x,y)$ of two variables $x,y\in \mathbb{R}$
  \begin{equation*}
    f(x,y) = 3x
  \end{equation*}
  and we want to find the maximum of this function in the $x-y$ plane
  \begin{equation*}
    \max_{x,y\in \mathbb{R}} f(x,y)
  \end{equation*}
  subject to the following constraints
  \begin{align}
    x + y & \leq 4 \\
    x & \geq 0 \\
    y & \geq 1
  \end{align}

  \alert{Optimal solution:} $x^* = 3, y^* = 1, f(x^*,y^*) = 9$.

  NB: We would have gotten the same solution if we had removed the 2nd constraint - it is \alert{non-binding}.
\end{frame}


\begin{frame}
  \frametitle{Another simple optimisation problem}

  We can also have equality constraints. Consider the maximum of this function in the $x-y-z$ space
  \begin{equation*}
    \max_{x,y,z\in \mathbb{R}} f(x,y,z) =  (3x + 5z)
  \end{equation*}
  subject to the following constraints
  \begin{align*}
    x + y & \leq 4 \\
    x & \geq 0 \\
    y & \geq 1 \\
    z & = 2
  \end{align*}

  \pause
  \alert{Optimal solution:} $x^* = 3, y^* = 1, z^* = 2, f(x^*,y^*,z^*) = 19$.

  [This problem is \alert{separable}: can solve for $(x,y)$ and $(z)$ separately.]
\end{frame}

\begin{frame}
  \frametitle{Energy system mapping to an optimisation problem}

  This optimisation problem has the same basic form as our energy system considerations:
  \ra{1.05}
  \begin{table}[!t]
    \begin{tabular}{p{6cm}p{0.5cm}p{6cm}}
      \toprule
      \alert{Objective function to minimise} & \vspace{.4cm}$\leftrightarrow$  &  \alert{Minimise total costs} \\
      \alert{Optimisation variables} & \vspace{.4cm} $\leftrightarrow$ &  \alert{Physical degrees of freedom (power plant dispatch, etc.)} \\
      \alert{Constraints} &\vspace{.4cm}  $\leftrightarrow$  &  \alert{Physical constraints (overloading, etc.)} \\
      \bottomrule
    \end{tabular}
  \end{table}

\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}

  Have to meet annual electricity demand of 500~TWh\el/a. Have two generators:

    \begin{table}[!t]
    \begin{tabular}{lrrrrr}
      \toprule
      Generator & Capacity limit & Yearly limit & efficiency & fuel cost & specific emissions \\
       & GW\el & TWh\el/a &  & \euro/MWh\th & tCO$_2$/MWh\th \\
      \midrule
      gas & 40 & 350 & 0.6 & 20 & 0.2 \\
      coal & 34 & 300 & 0.4 & 8 & 0.3 \\
      \bottomrule
    \end{tabular}
  \end{table}

    \begin{itemize}
    \item What is the minimum cost solution (considering only fuel costs)?
    \item What is the minimum cost solution if we restrict emissions to 300 MtCO$_2$/a?
    \item What about 250 MtCO$_2$/a?
    \end{itemize}

\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}
  2 variables: $x_1$ for yearly electricity generation from gas, $x_2$ for generation from coal.

  Specific electricity costs are given by fuel cost divided by efficency. For gas
  \begin{equation*}
    o_1 = \frac{ 20\, \textrm{\euro/MWh}_{\textrm{th}}}{0.6} = 33\, \textrm{\euro/MWh}_{\textrm{el}}
  \end{equation*}
  For coal
  \begin{equation*}
    o_2 = \frac{ 8\, \textrm{\euro/MWh}_{\textrm{th}}}{0.4} = 20\, \textrm{\euro/MWh}_{\textrm{el}}
  \end{equation*}

  So the cheapest option is to produce as much from coal as possible. But there are capacity constraints!

  $\Rightarrow$ Generate maximum from coal (300 TWh\el/a), rest from gas (200 TWh\el/a).

  Consume 750 TWh\th/a of coal and 333 TWh\th/a of gas $\Rightarrow$ emissions of $225 + 67 = 292$ MtCO$_2$/a.
\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}

  The objective function minimises total electricity generation costs:
  \begin{equation*}
    \min_{x_1,x_2} f(x_1,x_2) = o_1 x_1 + o_2 x_2
  \end{equation*}
  such that we meet the yearly demand:
  \begin{equation*}
    x_1 + x_2 =  500
  \end{equation*}
  and we respect the capacity constraints:
  \begin{align*}
    0 & \leq x_1 \leq 350 \\
    0 & \leq x_2 \leq 300
  \end{align*}
  as well as the emissions limit:
  \begin{equation*}
    \frac{e_1}{\eta_1}x_1 + \frac{e_2}{\eta_2}x_2 \leq  300
  \end{equation*}
  where $e_i$ is the specific emissions and $\eta_i$ is the efficiency.

  \alert{Optimal solution}: $x_1^* = 200, x_2^* = 300$.
\end{frame}

\begin{frame}
  \frametitle{Simple energy system example}


  The optimal solution is given by $x_1^* = 200, x_2^* = 300$.

  \centering
  \includegraphics[width=10.5cm]{coal-gas-no-emissions.pdf}
\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}


  An emissions cap of $\leq 300$ MtCO$_2$/a is non-binding - the solution stays the same.

  \centering
  \includegraphics[width=10.5cm]{coal-gas.pdf}
\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}

  If we restrict emissions from 300 to 250 MtCO$_2$/a, the solution shifts to $x_1^* = 300, x_2^* = 200$.

  \centering
  \includegraphics[width=10.5cm]{coal-gas-emissions.pdf}
\end{frame}



\section{Optimisation: Theory}

\begin{frame}
  \frametitle{Optimisation problem}


We have an \alert{objective function} $f: \R^k \to \R$
\begin{equation*}
  \max_{x} f(x)
\end{equation*}
[$x = (x_1, \dots x_k)$] subject to some \alert{constraints} within $\R^k$:
\begin{align*}
  g_i(x) & = c_i \hspace{1cm}\leftrightarrow\hspace{1cm} \l_i \hspace{1cm} i = 1,\dots n \\
  h_j(x) & \leq d_j \hspace{1cm}\leftrightarrow\hspace{1cm} \m_j \hspace{1cm} j = 1,\dots m
\end{align*}

$\l_i$ and $\m_j$ are the \alert{Karush-Kuhn-Tucker (KKT) multipliers} (basically Lagrange multipliers) we introduce for
each constraint equation. Each one measures the change in the objective value of the optimal solution obtained by relaxing the constraint by a small amount. Informally $\l_i \sim \frac{\d f}{\d c_i}$ and $\m_j \sim \frac{\d f}{\d d_j}$ at the optimum $x^*$. They are also known as the \alert{shadow prices} of the constraints.

\end{frame}


\begin{frame}
  \frametitle{Feasibility}

  The space $X \subset \R^k$ which satisfies
\begin{align*}
  g_i(x) & = c_i \hspace{1cm}\leftrightarrow\hspace{1cm} \l_i \hspace{1cm} i = 1,\dots n \\
  h_j(x) & \leq d_j \hspace{1cm}\leftrightarrow\hspace{1cm} \m_j \hspace{1cm} j = 1,\dots m
\end{align*}
is called the \alert{feasible space}.

It will have dimension lower than $k$ if there are independent
equality constraints.

It may also be empty (e.g. for $k=1$, $x \geq 1, x \leq 0$ in $\R^1$), in which
case the optimisation problem is called \alert{infeasible}.

It can be \alert{convex} or \alert{non-convex}.

If all the constraints are affine, then the feasible space is a convex polytope (multi-dimensional polygon).


\end{frame}


\begin{frame}
  \frametitle{Convexity means fast polynomial algorithms}

  If the feasible space is \alert{convex} it is much easier to search, since for a convex objective function we can keep looking in the direction of improving objective function without worrying about getting stuck in a local maximum.

  \centering
  \includegraphics[width=12cm]{concave-convex.jpg}

\end{frame}

\begin{frame}
  \frametitle{Lagrangian}


We now study the \alert{Lagrangian function}
\begin{equation*}
   \cL(x,\l,\m) = f(x) - \sum_i \l_i \left[g_i(x) - c_i\right]  - \sum_j \m_j \left[h_j(x) - d_j\right]
\end{equation*}

We've built this function using the variables $\l_i$ and $\m_j$ to
better understand the optimal solution of $f(x)$ given the
constraints.

The stationary points of $\cL(x,\mathbf{\l},\m)$ tell us important information
about the optima of $f(x)$ given the constraints.

[It is entirely analogous to the physics Lagrangian $L(x,\dot{x},\l)$
except we have no explicit time dependence $\dot{x}$ and  we have additional
constraints which are inequalities.]

We can already see that if $\frac{\d \cL}{\d \l_i} = 0$ then the
equality constraint $g_i(x) = c$ will be satisfied.

[Beware: $\pm$ signs appear differently in literature, but have been chosen here such that $\l_i = \frac{\d \cL}{\d c_i}$ and $\m_j = \frac{\d \cL}{\d d_j}$.]


\end{frame}



\begin{frame}
  \frametitle{Optimum is a saddle point of the Lagrangian}

  The stationary point of $\cL$ is a saddle point in $(x,\l,\m)$ space (here minimising $f(x)$):

  \centering
  \includegraphics[width=8cm]{conejo-saddle.png}

  \source{Conejo et al, ``Decomposition Techniques'' (2006)}

\end{frame}


\begin{frame}
  \frametitle{KKT conditions}

The \alert{Karush-Kuhn-Tucker (KKT) conditions} are necessary conditions that an optimal solution $x^*,\m^*,\l^*$ always satisfies (up to some regularity conditions):
\begin{enumerate}
\item \alert{Stationarity}: For $\ell = 1,\dots k$
  \begin{equation*}
  \frac{\d \cL}{\d x_\ell} =   \frac{\d f}{\d x_\ell} - \sum_i \l_i^* \frac{\d g_i}{\d x_\ell}  - \sum_j \m_j^* \frac{\d h_j}{\d x_\ell} = 0
  \end{equation*}
    \item \alert{Primal feasibility}:
      \begin{align*}
        g_i(x^*) & = c_i \\
        h_j(x^*) &\leq d_j
      \end{align*}
    \item \alert{Dual feasibility}: $\m_j^* \geq 0$
    \item \alert{Complementary slackness}: $\m_j^* (h_j(x^*) - d_j) = 0$
\end{enumerate}

\end{frame}





\begin{frame}
  \frametitle{Complementarity slackness for inequality constraints}


  We have for each inequality constraint
  \begin{align*}
    \m_j^* & \geq  0 \\
    \m_j^*(h_j(x^*) - d_j) & = 0
  \end{align*}

  So \alert{either} the inequality constraint is binding
  \begin{align*}
    h_j(x^*)  = d_j
  \end{align*}
  and we have $\m_j^* \geq 0$.

  \alert{Or} the inequality constraint is NOT binding
  \begin{align*}
    h_j(x^*)  < d_j
  \end{align*}
  and we therefore MUST have $\m_j^* = 0$.

  If the inequality constraint is non-binding, we can remove it from the optimisation problem, since it has no effect on the optimal solution.
\end{frame}




\begin{frame}
  \frametitle{Nota Bene}

  \begin{enumerate}
  \item The KKT conditions are necessary conditions for an optimal solution, but are only \alert{sufficient} for optimality
    of the solution under certain conditions, e.g. for problems with convex objective, convex differentiable inequality constraints and affine equalities constraints. For linear problems, KKT is sufficient.
    \item The variables $x_\ell$  are often called the \alert{primary variables}, while $(\l_i,\m_j)$ are the \alert{dual variables}.
  \item Since at the optimal solution we have $g_i(x^*) = c_i$ for equality constraints and
    $\m_j^*(h_j(x^*) - d_j) = 0$, we have
    \begin{equation*}
         \cL(x^*,\l^*,\m^*) = f(x^*)
    \end{equation*}


  \end{enumerate}

\end{frame}


\begin{frame}
  \frametitle{How we will use the KKT conditions}

  Usually we will have enough constraints to determine the $k$ values
  $x_\ell^*$ for $\ell=1,\dots k$ uniquely, i.e. $k$ independent constraints will be binding and the objective function is never constant along any constraint.

  We will use the KKT conditions, primarily stationarity, to determine
  the values of the $k$ KKT multipliers for the independent binding constraints.

  \alert{Dimensionality check}: we need to find $k$ KKT multipliers and we have $k$ equations from stationarity to find them. Good!

  The remaining KKT multipliers are either zero (for non-binding
  constraints) or dependent on the $k$ independent KKT multipliers in the case of dependent constraints.

  (There are also degenerate cases where the optimum is not at a single point, where things will be more complicated, e.g. when objective function is constant along a constraint.)

\end{frame}

\begin{frame}
  \frametitle{Return to simple optimisation problem}

  We want to find the maximum of this function in the $x-y$ plane
  \begin{equation*}
    \max_{x,y\in \mathbb{R}} f(x,y) = 3x
  \end{equation*}
  subject to the following constraints (now with KKT multipliers)
  \begin{align*}
    x + y & \leq 4  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_1 \\
    -x & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_2\\
    -y & \leq -1  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_3
  \end{align*}
  We know the optimal solution in the \alert{primal variables} $x^* = 3, y^* = 1, f(x^*,y^*) = 9$.

  What about the \alert{dual variables} $\m_i$?

  Since the second constraint is not binding, by complementarity
  $\m_2^*(-x^* - 0) = 0$ we have $\m_2^* = 0$. To find $\m_1^*$ and
  $\m_3^*$ we have to do more work.


\end{frame}


\begin{frame}
  \frametitle{Simple problem with KKT conditions}

  We use stationarity for the optimal point:
  \begin{align*}
    0 & = \frac{\d \cL}{\d x } =   \frac{\d f}{\d x} - \sum_i \l_i^* \frac{\d g_i}{\d x}  - \sum_j \m_j^* \frac{\d h_j}{\d x} = 3 - \m_1^* + \m_2^* \\
    0 & = \frac{\d \cL}{\d y } =   \frac{\d f}{\d y} - \sum_i \l_i^* \frac{\d g_i}{\d y}  - \sum_j \m_j^* \frac{\d h_j}{\d y} = - \m_1^* + \m_3^*
  \end{align*}
  From which we find:
  \begin{align*}
    \m_1^* & = 3 - \m_2^* = 3 \\
    \m_3^* & = \m_1^* = 3
  \end{align*}

  Check interpretation: $\m_j = \frac{\d \cL}{\d d_j}$ with $d_j \to d_j + \varepsilon$.
\end{frame}

\begin{frame}
  \frametitle{Simple problem with KKT conditions: Check interpretation}

  Check interpretation of $\m_1^* = 3$ by shifting constant $d_1$ for first constraint by $\varepsilon$ and solving:
  \begin{equation*}
    \max_{x,y\in \mathbb{R}} f(x,y) = 3x
  \end{equation*}
  subject to the following constraints
  \begin{align*}
    x + y & \leq 4+ \varepsilon  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_1 \\
    -x & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_2\\
    -y & \leq -1  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_3
  \end{align*}

\end{frame}


\begin{frame}
  \frametitle{Simple problem with KKT conditions: Check interpretation}

  $f(x,y) = 3x$ maximised at $x^* = 3+\varepsilon, y^* = 1, f(x^*, y^*) = 9+3\varepsilon$.

  $d_1 \to d_1 + \varepsilon$ causes optimum to shift $f(x^*, y^*) \to f(x^*, y^*) + 3\varepsilon$. Consistent with $\m_1^* = 3$.

  \centering
  \includegraphics[width=7cm]{2dsimple-v1.pdf}

\end{frame}


\begin{frame}
  \frametitle{Return to another simple optimisation problem}

  We want to find the maximum of this function in the $x-y-z$ space
  \begin{equation*}
    \max_{x,y,z\in \mathbb{R}} f(x,y,z) = 3x + 5z
  \end{equation*}
  subject to the following constraints (now with KKT multipliers)
  \begin{align*}
    x + y & \leq 4  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_1 \\
    -x & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_2\\
    -y & \leq -1  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_3 \\
    z & = 2  \hspace{1cm}\leftrightarrow\hspace{1cm} \l
  \end{align*}
  We know the optimal solution in the \alert{primal variables} $x^* = 3, y^* = 1, z^* = 2, f(x^*,y^*,z^*) = 19$.

  What about the \alert{dual variables} $\m_i,\l$?

  We get same solutions to $\m_1^* = 3, \m_2^* = 0, \m_3^* =3$ because they're not coupled to $z$ direction. What about $\l^*$?

\end{frame}


\begin{frame}
  \frametitle{Another simple problem with KKT conditions}

  We use stationarity for the optimal point:
  \begin{align*}
    0 & = \frac{\d \cL}{\d z } =   \frac{\d f}{\d z} - \sum_i \l_i^* \frac{\d g_i}{\d z}  - \sum_j \m_j^* \frac{\d h_j}{\d z} = 5 - \l^*
  \end{align*}
  From which we find:
  \begin{align*}
    \l^* & = 5
  \end{align*}

  Check interpretation: $\l_i = \frac{\d \cL}{\d c_i}$ with $c_i \to c_i + \varepsilon$.
\end{frame}


\begin{frame}
  \frametitle{An example for you to do}

  Find the values of $x^*,y^*,\m_i^*$
  \begin{equation*}
    \max_{x,y\in \mathbb{R}} f(x,y) = y
  \end{equation*}
  subject to the following constraints
  \begin{align*}
    y + x^2 & \leq 4  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_1 \\
    y - 3x & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_2\\
    -y & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \m_3
  \end{align*}
\end{frame}



\begin{frame}
  \frametitle{Simple energy system example}

  Objective function:
  \begin{equation*}
    \min_{x_1,x_2} f(x_1,x_2) = o_1 x_1 + o_2 x_2
  \end{equation*}
  with constraints:
  \begin{align*}
  x_1 + x_2 & =  500  \hspace{1cm}\leftrightarrow\hspace{1cm} \l \\
  x_1 & \leq 350  \hspace{1cm}\leftrightarrow\hspace{1cm} \bar{\m}_1 \\
  -x_1 & \leq 0 \hspace{1cm}\leftrightarrow\hspace{1cm} \ubar{\m}_1 \\
  x_2 & \leq 300  \hspace{1cm}\leftrightarrow\hspace{1cm} \bar{\m}_2\\
  -x_2 & \leq 0  \hspace{1cm}\leftrightarrow\hspace{1cm} \ubar{\m}_2\\
    \frac{e_1}{\eta_1}x_1 + \frac{e_2}{\eta_2}x_2 & \leq  300 \hspace{1cm}\leftrightarrow\hspace{1cm} \m
  \end{align*}

  Stationarity for $i=1,2$:
    \begin{align*}
    0 & = \frac{\d \cL}{\d x_i } =   \frac{\d f}{\d x_i} - \sum_i \l_i^* \frac{\d g_i}{\d x_i}  - \sum_j \m_j^* \frac{\d h_j}{\d x_i} = o_i - \l^* - \bar{\m}_i^*  +  \ubar{\m}_i^*  - \frac{e_i}{\eta_i} \m^*
  \end{align*}


\end{frame}



\begin{frame}
  \frametitle{Simple energy system example}


  An emissions cap of $\leq 300$ MtCO$_2$/a (red) is non-binding.

  \centering
  \includegraphics[width=10.5cm]{coal-gas.pdf}
\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}

  For an emissions limit of 300 we had $x_1^* = 200, x_2^* = 300$. Because so many constraints were non-binding here, we had:
  \begin{equation*}
     \ubar{\m}_1^* =  \ubar{\m}_2^* =  \bar{\m}_1^* =  \m^* = 0
  \end{equation*}
  The only non-zero dual variables are for the binding demand constraint $\l^*$ and the binding capacity constraint for coal $\bar{\m}_2^*$.  Thus we get from stationarity:
  \begin{equation*}
    \l^* = o_1 \hspace{1cm} \l^* = o_2  - \bar{\m}_2^*
  \end{equation*}
  $\l^* = o_1 = 33$ \euro/MWh\el{} is the price of supplying an extra unit of electricity. It comes from the gas generator, which still has free dispatchable capacity.

  $\bar{\m}_2^* = o_2 - \l^* = o_2 - o_1 = (20-33)$ \euro/MWh\el{} $= -13$ \euro/MWh\el{} is the system cost decrease if the capacity of generator 2 (coal) expands by one unit. This allows us to substitute more expensive generation from gas (at 33\euro/MWh\el) with cheaper generation from coal (at 20\euro/MWh\el).

\end{frame}


\begin{frame}
  \frametitle{Simple energy system example}

  For a binding emissions limit of 250 we had $x_1^* = 300, x_2^* = 200$. Because none of the generation constraints are non-binding here, we have $\ubar{\m}_1^* =  \ubar{\m}_2^* =  \bar{\m}_1^* = \bar{\m}_2^* = 0$.

  The only non-zero dual variables are for the binding demand constraint $\l^*$ and the binding emissions constraint  $\m^*$.  Thus we get from stationarity:
  \begin{equation*}
    \l^* = o_1  - \frac{e_1}{\eta_1} \m^* \hspace{1cm} \l^* = o_2   - \frac{e_2}{\eta_2} \m^*
  \end{equation*}
  Again we have two equations for two unknowns ($\l^*$ and $\m^*$) and solve to find:
  \begin{align*}
    \m^* & = \frac{o_1 - o_2}{\frac{e_1}{\eta_1} - \frac{e_2}{\eta_2}} = \frac{33.3-20}{0.333-0.75} = -32 \textrm{ \euro/tCO}_2
  \end{align*}
  and $\l^* = 44$ \euro/MWh\el{}. How do we interpret these shadow prices?

  Looking at the equation for $\m^*$, $o_1-o_2$ is the cost in \euro/MWh\el{} of replacing coal with gas to reduce emissions, divided by the emissions reduced $ \frac{e_2}{\eta_2} - \frac{e_1}{\eta_1}$ in tCO$_2$/MWh\el{}, multiplied by $-1$.

\end{frame}

\begin{frame}
  \frametitle{Simple energy system example}


  The magnitude of $\mu^*$ is the \alert{marginal abatement cost} for CO$_2$ reduction, i.e. what it costs to reduce the next tCO$_2$ from the system (e.g. by replacing coal generation by gas). It is negative in this case because $\mu^*$ by definition measures the cost reduction by increasing the CO$_2$ limit by $\varepsilon$, rather than the cost increase by tightening. (Whereas in maximisation problems we have dual feasibility $\m_j^* \geq 0$, for minimisation problems we have $\m_j^* \leq 0$ since we obtain a lower objective function when we relax the constraint.)


  The market price $\l^* = 44$ \euro/MWh\el{} is higher than either generator's marginal cost. Why?

  Because we have to obey the emissions constraint. If we raise demand by 1 MWh\el{}, we increase gas generation, but this increases also CO$_2$ emissions. To compensate and reduce emissions, we have to substitute some coal for gas. Coal is cheaper than gas, so this also raises the costs.

  In another interpretation: we have
  \begin{equation*}
    \l^* = o_i  - \frac{e_i}{\eta_i} \m^*
  \end{equation*}
  so $\m^*$ is adding an effective \alert{carbon price} to the fuel-based marginal cost, thus increasing the marginal cost (remember $\m^*$ is negative).

\end{frame}


\section{Optimisation: Solution Algorithms}


\begin{frame}
  \frametitle{Optimisation solution algorithms}

  In general finding the solution to optimisation problems is hard,
  at worst $NP$-hard. Non-linear,
  non-convex and/or discrete (i.e. some variables can only take
  discrete values) problems are particularly troublesome.

  There is specialised software for solving particular classes of
  problems (linear, quadratic, discrete etc.).

  Since we will mostly focus on linear problems, the main two
  algorithms of relevance are:
  \begin{itemize}
  \item The \alert{simplex algorithm}
  \item The \alert{interior-point algorithm}
  \end{itemize}

\end{frame}


\begin{frame}
  \frametitle{Simplex algorithm}

    \begin{columns}[T]
\begin{column}{6.5cm}

  \includegraphics[width=6cm]{480px-Simplex-method-3-dimensions.png}
\end{column}
\begin{column}{7.5cm}

  The simplex algorithm works for linear problems by building the feasible space, which is a multi-dimensional polyhedron, and searching its surface for the solution.

  If the problem has a solution, the optimum can be assumed to always occur at (at least) one of the vertices of the polyhedron. There is a finite number of vertices.

  The algorithm starts at a feasible vertex. If it's not the optimum, the objective function will increase along one of the edges leading away from the vertex. Follow that edge to the next vertex.

  Repeat until the optimum is found.

  \alert{Complexity:} On \emph{average} over given set of problems can solve in polynomial time, but worst cases can always be found with exponential time.
\end{column}
  \end{columns}

\source{\hrefc{https://en.wikipedia.org/wiki/Simplex_algorithm\#/media/File:Simplex-method-3-dimensions.png}{Wikipedia}}
\end{frame}




\begin{frame}
  \frametitle{Interior point methods}

    \begin{columns}[T]
\begin{column}{6.5cm}

  \includegraphics[width=7.5cm]{1024px-Karmarkar.png}
\end{column}
\begin{column}{7.5cm}

  Interior point methods can be used on more general non-linear problems. They search the interior of the feasible space rather than its surface.

  They achieve this by extremising the objective function plus a \alert{barrier term} that penalises solutions that come close to the boundary.

  As the penality becomes less severe the algorithm converges to the optimum point at the boundary.

  \vspace{.5cm}
  \alert{Complexity:} For linear problems, Karmakar's version of the interior point method can run in polynomial time.
\end{column}
  \end{columns}

\source{\hrefc{https://en.wikipedia.org/wiki/Interior-point_method\#/media/File:Karmarkar.svg}{Wikipedia}}
\end{frame}


\begin{frame}
  \frametitle{Interior point methods: Barrier method}

 Take a problem
  \begin{equation*}
    \min_{\{x_\ell, \ell=1,\dots k\}} f(x)
  \end{equation*}
such that for
\begin{align*}
  g_i(x) & = 0 \leftrightarrow \l_i, i = 1\dots n \\
  x & \geq 0
\end{align*}
Any optimisation problem can be brought into this form. Introduce the \alert{barrier function}
\begin{equation*}
 B(x,\mu) = f(x) - \m \sum_{\ell=1}^k \ln(x_\ell)
\end{equation*}
where $\mu$ is the small and positive \alert{barrier parameter} (a scalar). Note that the barrier term penalises solutions when $x$ comes close to 0 by becoming large and positive.
\end{frame}


\begin{frame}
  \frametitle{Interior point methods: Barrier method}

  Barrier term $-\m ln(x)$ penalises the minimisation the closer we get to $x=0$. As $\mu$ gets smaller it converges on being a near-vertical function at $x=0$.

  \centering
  \includegraphics[width=7.5cm]{barrier-term.pdf}


\end{frame}


\begin{frame}
  \frametitle{Interior point methods: Barrier method: 1-d example}

  Return to our old 1-d example. We minimise a function of one variable $x \in \mathbb{R}$
  \begin{equation*}
      \min_x (x-2)^2
  \end{equation*}
  subject to a constraint
  \begin{equation*}
       x \geq 3
  \end{equation*}
  Solution: $x^* = 3$.

  \centering
  \includegraphics[width=7cm]{quadratic-gt3}
\end{frame}



\begin{frame}
  \frametitle{Interior point methods: Barrier method: 1-d example}

  Now instead minimise the barrier problem without any constraint:
  \begin{equation*}
     \min_x B(x,\mu) = (x-2)^2 - \m  \ln(x-3)
  \end{equation*}
  Solve $\frac{\d B(x,\mu)}{\d x} = 2(x-2) -\frac{\mu}{x-3} = 0$, i.e. at $x^* = 2.5 + 0.5\sqrt{1+2\mu} \to 3$ as $\mu \to 0$.

  \centering
  \includegraphics[width=8.5cm]{quadratic-barrier}
\end{frame}



\begin{frame}
  \frametitle{Interior point methods: Barrier method}

  The problem
\begin{equation*}
  \min_{\{x_\ell, \ell=1,\dots k\}} \left[ f(x) - \m \sum_{\ell=1}^k \ln(x_\ell)  \right]
\end{equation*}
such that
\begin{align*}
  c_i(x) & = 0 \leftrightarrow \l_i, i = 1\dots n
\end{align*}
can now be solved using the extremisation of the Lagrangian like we did for KKT sufficiency.

Solve the following equation system iteratively using the Newton method to find the $x_\ell$ and $\lambda_i$:
\begin{align*}
    \nabla_\ell f(x) - \m  \frac{1}{x_\ell} + \sum_i \lambda_i \nabla_\ell c_i(x) & = 0 \\
  c_i(x) & = 0
\end{align*}

See this \hrefc{https://www.youtube.com/watch?v=zm4mfr-QT1E}{nice video} for more details and visuals.
\end{frame}


\end{document}