\documentclass{article}

\usepackage[dvips]{graphics}
\usepackage{epsfig,epic,eepic}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{color}
\usepackage{textcomp}

\title{Transforming a  Piecewise Linear Functions in a Convex Predicate} 
\author{Simone Atzeni\\
{\tt simone@cs.utah.edu}}

% Set properties of paper
\setlength{\textheight}{8.75in}
\setlength{\textwidth}{6.8in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

\begin{document}
\maketitle 

We have this Piecewise Linear Functions:

\[ 
z=h_i(x,u)= 
\begin{cases} 
A_1(x) + u (B_1(x) - A_1(x)), & \text{if $0 \le u \le 1$} \\ 
B_1(x) + (u-1) (B_2(x) - B_1(x)), & \text{if $1 \le u \le 2$} \\ 
B_2(x) + (u-2) (B_3(x) - B_2(x)), & \text{if $u \ge 2$} \\ 
\end{cases} 
\] 

where:

\begin{itemize} 
\item $A_1(x) = 3x$
\item $B_1(x) = 4x$
\item $B_2(x) = 5x$
\item $B_3(x) = 6x$
\end{itemize} 

A KPI $h_i(x$, $u)$ ($i= 1, \ldots q$) is a convex predicate $H_i(x, u, {\bf y},z)$ tale che:
$\exists {\bf y}_i$ $H_i(x, u, {\bf y}_i, z_i) = 1$ 
$\; \mbox{\rm sse} \;$
$[h_i(x, u) = z_i]$ 

Convexification (?):

\begin{enumerate}
\item

${\rm Expr1}(y_1,x,u,z) = $

$z=A_1(x) + u (B_1(x) - A_1(x)), \text{se $0 \le u < 1$}$

\[
z=A_1(x) + (B_1(x) - A_1(x)) u \implies z + (A_1(x) - B_1(x)) u = A_1(x), \text{se $0 \le u \le 1$}
\]

then:

\[
[z + (A_1(x) - B_1(x)) u \ge A_1(x) \wedge z + (A_1(x) - B_1(x)) u \le A_1(x)]
\]

\[
\text{ se $[u \ge 0 \wedge u \le 1]$}
\]

or

\[
[u \ge 0 \wedge u \le 1] \to [z + (A_1(x) - B_1(x)) u \ge A_1(x) \wedge
\]

\[
z + (A_1(x) - B_1(x)) u \le A_1(x)]
\]

divided in:

\[
[u \ge 0 \wedge u \le 1] \to [z + (A_1(x) - B_1(x)) u \ge A_1(x)] 
\]

\[
[u \ge 0 \wedge u \le 1] \to [z + (A_1(x) - B_1(x)) u \le A_1(x)]
\]

Introduce a auxiliary variable

\[
[u \ge 0 \wedge u \le 1] \to y_1
\]

So the constraints about the first piece of the function are:

\begin{itemize}
\item[a.] ${\rm Expr1.1}(y_1,x,u,z) = $

$y_1 \to [z + (A_1(x) - B_1(x)) u \ge A_1(x)]$

\[
y_1 \to [z + (A_1(x) - B_1(x)) u \ge A_1(x)] \implies 
\]
\[
\implies (B_1(x) - A_1(x))u-z \le -A_1(x)y_1 + (1-y_1)maxA(u,z) \implies
\]

\[
\implies \bf{(B_1(x) - A_1(x))u-z + (A_1(x) + maxA(u,z)) y_1 \le maxA(u,z)}
\]

\item[b.] ${\rm Expr1.2}(y_1,x,u,z) =  $

$y_1 \to [z + (A_1(x) - B_1(x)) u \le A_1(x)]$
\[
y_1 \to [z + (A_1(x) - B_1(x)) u \le A_1(x)] \implies
\]
\[
\implies z + (A_1(x) - B_1(x))u \le A_1(x)y_1 + (1-y_1)maxA(u,z)
\]
\[
\implies \bf{z + (A_1(x) - B_1(x))u + (maxA(u,z) - A_1(x))y_1 \le maxA(u,z)}
\]
\end{itemize}

Besides:

\[\bar{y_1} \to \neg[u \ge 0] \vee \neg[u \le 1]\]

that spawns the constraints:

\begin{itemize}
\item[c.] ${\rm Expr1.3}(y_1,x,u,z) = $

$q_1 \to u \le 0$

\[
q_1 \to u \le 0 \implies u \le (1-q_1)maxA(u) \implies
\]
\[
\implies \bf{u + maxA(u)q_1 \le maxA(u)}
\]


\item[d.] ${\rm Expr1.4}(y_1,x,u,z) = $

$q_2 \to u \ge 1$

\[
q_2 \to u \ge 1 \implies -u \le -q_2 + (1-q_2)maxA(u) \implies
\]
\[
\implies \bf{-u  + (1 + maxA(u))q_2 \le maxA(u)}
\]

\item[e.] ${\rm Expr1.5}(y_1,x,u,z) = $

$\bar{y_1} \to q_1 + q_2 \ge 1$

\[
\bar{y_1} \to q_1 + q_2 \ge 1 \implies \bf{-q_1-q_2 \le (y_1-1)+y_1maxA(q_1,q_2)}
\]
\[
\implies \bf{-q_1-q_2 - (1 + maxA(q_1,q_2)) y_1 \le -1}
\]

\end{itemize}

The first expression defined ${\rm Expr1}(y_1,x,u,z)$ is then the \emph{and} of 5 expression:

\[
{\rm Expr1}(y_1,x,u,z) = {\rm Expr1.1}(y_1,x,u,z) \wedge {\rm Expr1.2}(y_1,x,u,z) \wedge
\]
\[
\wedge {\rm Expr1.3}(y_1,x,u,z) \wedge {\rm Expr1.4}(y_1,x,u,z) \wedge
\]
\[
\wedge {\rm Expr1.5}(y_1,x,u,z)
\]

\item

${\rm Expr2}(y_2,x,u,z) =  $

$z=B_1(x) + (u-1) (B_2(x) - B_1(x)), \text{se $1 \le u < 2$}$

\[
z=B_1(x) + (B_2(x) - B_1(x)) u - B_2(x)+B_1(x) \implies
\]
\[
\implies z + (B_1(x) - B_2(x)) u = 2B_1(x) - B_2(x), \text{se $1 \le u \le 2$}
\]

so:

\[
[z + (B_1(x) - B_2(x)) u \ge 2B_1(x) - B_2(x) \wedge
\]

\[
\wedge z + (B_1(x) - B_2(x)) u \le 2B_1(x) - B_2(x)] \text{ se $[1 \le u \le 2]$}
\]

or:

\[
[u \ge 1 \wedge u \le 2] \to [z + (B_1(x) - B_2(x)) u \ge 2B_1(x) - B_2(x) \wedge 
\]

\[
z + (B_1(x) - B_2(x)) u \le 2B_1(x) - B_2(x)]
\]

divided in:

\[
[u \ge 1 \wedge u \le 2] \to [z + (B_1(x) - B_2(x)) u \ge 2B_1(x) - B_2(x)]
\]

\[
[u \ge 1 \wedge u \le 2] \to [z + (B_1(x) - B_2(x)) u \le 2B_1(x) - B_2(x)]
\]

Introduce a auxiliary variable:

\[
[u \ge 1 \wedge u \le 2] \to y_2
\]

So the constraints about the second piece of the function are:

\begin{itemize}
\item[a.] ${\rm Expr2.1}(y_2,x,u,z) =  $

$y_2 \to [z + (B_1(x) - B_2(x)) u \ge 2B_1(x) - B_2(x)]$

\[
y_2 \to [z + (B_1(x) - B_2(x)) u \ge 2B_1(x) - B_2(x)] \implies 
\]
\[
\implies (B_2(x) - B_1(x)) u - z + \le (B_2(x) - 2B_1(x))y_2 + (1-y_2)maxA(u,z) \implies
\]
\[
\implies \bf{(B_2(x) - B_1(x)) u - z + (2B_1(x) - B_2(x) + maxA(u,z))y_2  \le maxA(u,z)}
\]

\item[b.] ${\rm Expr2.2}(y_2,x,u,z) =  $

$y_2 \to [z + (B_1(x) - B_2(x)) u \le 2B_1(x) - B_2(x)]$

\[
y_2 \to [z + (B_1(x) - B_2(x)) u \le 2B_1(x) - B_2(x)] \implies 
\]
\[
\implies z + (B_1(x) - B_2(x)) u \le (2B_1(x) - B_2(x))y_2 + (1-y_2)maxA(u,z) \implies
\]
\[
\implies \bf{z + (B_1(x) - B_2(x)) u + (maxA(u,z) - 2B_1(x) + B_2(x))y_2 \le maxA(u,z)}
\]
\end{itemize}

Besides: 

\[\bar{y_2} \to \neg[u \ge 1] \vee \neg[u \le 2]\]

that spawns the constraints:

\begin{itemize}
\item[c.] ${\rm Expr2.3}(y_2,x,u,z) =  $

$q_1 \to u \le 1$

\[
q_1 \to u \le 1 \implies u \le q_1+(1-q_1)maxA(u) \implies
\]
\[
\implies \bf{u + (maxA(u) - 1) q_1 \le maxA(u)}
\]


\item[d.] ${\rm Expr2.4}(y_2,x,u,z) =  $

$q_2 \to u \ge 2$

\[
q_2 \to u \ge 2 \implies -u \le -2q_2 + (1-q_2)maxA(u) \implies
\]
\[
\implies \bf{-u +(2 + maxA(u))q_2 \le maxA(u)}
\]


\item[e.] ${\rm Expr2.5}(y_2,x,u,z) =  $

$\bar{y_2} \to q_1 + q_2 \ge 1$

\[
\bar{y_2} \to q_1 + q_2 \ge 1 \implies -q_1-q_2 \le (y_2-1)+y_2maxA(q_1,q_2) \implies
\]
\[
\implies \bf{-q_1-q_2 - (1 +  maxA(q_1,q_2))y_2 \le -1}
\]

\end{itemize}

The expression ${\rm Expr2}(y_2,x,u,z)$, is the \emph{and} of:

\[
{\rm Expr2}(y_2,x,u,z) = {\rm Expr2.1}(y_2,x,u,z) \wedge {\rm Expr2.2}(y_2,x,u,z) \wedge
\]
\[
\wedge {\rm Expr2.3}(y_2,x,u,z) \wedge {\rm Expr2.4}(y_2,x,u,z) \wedge
\]
\[
\wedge {\rm Expr2.5}(y_2,x,u,z)
\]

\item

${\rm Expr3}(y_3,x,u,z) =  $

$z=B_2(x) + (u-2) (B_3(x) - B_2(x)), \text{se $u \ge 2$}$

\[
z=B_2(x) + (B_3(x) - B_2(x)) (u-2) \implies z=B_2(x) + (B_3(x) - B_2(x)) u - 2B_3(x) + 2B_2(x)
\]
\[
\implies z + (B_2(x) - B_3(x)) u = 3 B_2(x) - 2B_3(x), \text{se $u \ge 2$}
\]

quindi:

\[
[z + (B_2(x) - B_3(x)) u \ge 3 B_2(x) - 2B_3(x) \wedge
\]

\[
\wedge z + (B_2(x) - B_3(x)) u \le 3 B_2(x) - 2B_3(x) \text{ se $[u \ge 2]$}
\]

or:
\[
[u \ge 2] \to [ z + (B_2(x) - B_3(x)) u \ge 3 B_2(x) - 2B_3(x) \wedge 
\]

\[
z + (B_2(x) - B_3(x)) u \le 3 B_2(x) - 2B_3(x)]
\]

divided in:

\[
[u \ge 2] \to [ z + (B_2(x) - B_3(x)) u \ge 3 B_2(x) - 2B_3(x)]
\]

\[
[u \ge 2] \to [ z + (B_2(x) - B_3(x)) u \le 3 B_2(x) - 2B_3(x)]
\]

Introduce a auxiliary variable:

\[
[u \ge 2] \to y_3
\]

So the constraints about the third piece of the function are:

\begin{itemize}
\item[a.] ${\rm Expr3.1}(y_3,x,u,z) =  $

$y_3 \to [ z + (B_2(x) - B_3(x)) u \ge 3 B_2(x) - 2B_3(x)]$

\[
y_3 \to [ (B_3(x) - B_2(x)) u - z \le 2 B_3(x) - 3B_2(x)] \implies 
\]
\[
\implies (B_3(x) - B_2(x)) u - z \le (2 B_3(x) - 3B_2(x))y_3 + (1-y_3)maxA(u,z)
\]
\[
\implies (B_3(x) - B_2(x)) u - z \le (2 B_3(x) - 3B_2(x))y_3 + (1-y_3)maxA(u,z) \implies
\]
\[
\implies \bf{(B_3(x) - B_2(x)) u - z + (3B_2(x) - 2 B_3(x) + maxA(u,z))y_3 \le maxA(u,z)}
\]


\item[b.] ${\rm Expr3.2}(y_3,x,u,z) =  $

$y_3 \to [ z + (B_2(x) - B_3(x)) u \le 3 B_2(x) - 2B_3(x)]$

\[
y_3 \to [z + (B_2(x) - B_3(x)) u \le 3 B_2(x) - 2B_3(x)] \implies 
\]
\[
\implies z + (B_2(x) - B_3(x)) u \le (3 B_2(x) - 2B_3(x))y_3 + (1-y_3)maxA(u,z) \implies
\]
\[
\implies \bf{z + (B_2(x) - B_3(x)) u + (maxA(u,z) + 2B_3(x) - 3 B_2(x))y_3 \le maxA(u,z)}
\]
\end{itemize}

Besides: 

\[\bar{y_3} \to \neg[u \ge 2] \]

that spawns the constraints:

\begin{itemize}
\item[c.] ${\rm Expr3.3}(y_3,x,u,z) =  $

$\bar{y_3} \to u \le 2$

\[
\bar{y_3} \to u \le 2 \implies u \le 2(1-y_3)+ y_3maxA(u) \implies
\]
\[
\implies \bf{u + (2 - maxA(u))y_3 \le 2}
\]

\end{itemize}

Finally, the expression ${\rm Expr3}(y_3,x,u,z)$, is the \emph{and} of:

\[
{\rm Expr3}(y_3,x,u,z) = {\rm Expr3.1}(y_3,x,u,z) \wedge {\rm Expr3.2}(y_2,x,u,z) \wedge
\]
\[
\wedge {\rm Expr3.3}(y_3,x,u,z)
\]

\end{enumerate}

\end{document}