sesh2.tex (18030B)
1 \include{./preamble.tex} 2 3 \begin{document} 4 \maketitle 5 \tableofcontents 6 \section{Sheet 2} 7 \subsection{Exercise 7} 8 For the functions $g:\mathbb{R}^{2}\to \mathbb{R}^{2}$, find $X = 9 \{(x,y)\in\mathbb{R}^{2}: g(x, y)\leqq 0\} $, the tangent cone and the 10 linearized tangent cone at $x_0 \in X$ and find out if $x_0$ fulfills 11 (ADABIDE-CQ), i.e. $T_\text{lin}(x_0) = T_X(x_0)$. 12 \begin{enumerate} 13 \item $g(x,y) = (y-x^{3}, -y)^{T},\quad x_0=(0,0)^{T}$ 14 \item $g(x,y) = (y^{2}-x+1, 1-x-y)^{T},\quad x_0=(1,0)^{T}$ 15 \end{enumerate} 16 For 1. we have that $g(x,y)\leqq 0$ means that 17 \begin{align} 18 y-x^{3}\le_0\\ 19 -y \le 0\\ 20 \Rightarrow 0\le y\le x^{3}. 21 \end{align} 22 So is defined as $X = \{\left( x,y \right) \in \mathbb{R}^{2}: 0\le y, y\le 23 x^{3}\}$. Graphically represented $X$ looks like the following 24 \begin{figure}[H] 25 \centering 26 \begin{tikzpicture}[yscale=1, xscale=1] 27 \begin{axis}[ 28 xmin=-1, xmax=2, 29 ymin=-1, ymax=2, 30 axis lines = middle, 31 ] 32 \addplot[domain=0:2, samples=100, color=gray, name path=A]{x^3}; 33 \addplot[domain=0:2, samples=100, name path=B]{0}; 34 \addplot[fill=gray,fill opacity=0.5] fill between[of=A and B,soft 35 clip={domain=0:2},]; 36 \node[] at (axis cs:2,2) [below left] {X}; 37 \node[draw, circle, inner sep=1pt, fill=red, label=above right:{$x_0$}] at 38 (axis cs:0, 0) {}; 39 \end{axis} 40 \end{tikzpicture} 41 \label{fig: ex7.1} 42 \end{figure} 43 Then the tangent cone is 44 \begin{align} 45 T_X(x_0) = \left\{\begin{pmatrix} \lambda\\ 0 \end{pmatrix} : \lambda 46 \ge 0\right\}. 47 \end{align} 48 Now for the linearized tangent cone we calculate, $g_1(x_0) = 0$ and 49 $g_2(x_0) = 0$ meaning that $\mathcal{A}(x_0)=\{1, 2\}$ thereby 50 \begin{align} 51 T_\text{lin}(x_0) 52 &= \{d\in \mathbb{R}^{2}: \nabla g_1(x_0)^{T}d\le 0,\; \nabla g_2(x_0)^{T}d 53 \le 0\}\\ 54 &= \left\{d\in \mathbb{R}^{2}: \begin{pmatrix}0\\1\end{pmatrix}^{T}d\le 0,\; 55 \begin{pmatrix}0\\-1\end{pmatrix}^{T}d 56 \le 0\right\}\\ 57 &= \left\{\begin{pmatrix} \lambda \\ 0 \end{pmatrix}, \begin{pmatrix} -\lambda 58 \\ 0 \end{pmatrix}:\; \lambda \ge 0 \right\}. 59 \end{align} 60 We conclude that $x_0 = (0, 0)^{T}$ does not satisfy the ADABIE-CQ 61 condition for this optimization problem. 62 \newline 63 For number 2. first the domain $X$, $g(x, y) \le 0$ 64 \begin{align} 65 y^{2}-x +1 \le 0 \quad &\text{and} \quad 1-x-y\le 0\\ 66 y^2 - 1 \le x \quad &\text{and} \quad y-1\le x 67 \end{align} 68 so $X$ has the following form 69 \begin{align} 70 X = \left\{ \left( x,y \right) \in \mathbb{R}^{2}: 71 \begin{cases} 72 -\sqrt{x+1}\le y\le x+1 73 \quad \text{for}\; x\in(-1, 0]\\ 74 -\sqrt{x+1}\le y \le\sqrt{x+1}\quad \text{for}\; x > 0 75 \end{cases} 76 \right\} 77 \end{align} 78 and graphically 79 \begin{figure}[H] 80 \centering 81 \begin{tikzpicture}[yscale=1, xscale=1] 82 \begin{axis}[ 83 xmin=-1.5, xmax=2, 84 ymin=-1.5, ymax=1.5, 85 axis lines = middle, 86 ] 87 \addplot[domain=-1:0, samples=100, color=gray, name path=A]{x+1}; 88 \addplot[domain=-1:2, samples=100, color=gray, name 89 path=B]{-sqrt(x+1)}; 90 \addplot[domain=0:2, samples=100, color=gray, name 91 path=C]{sqrt(x+1)}; 92 \addplot[domain=-1:0, samples=100, color=gray, name 93 path=L]{0}; 94 \addplot[fill=gray,fill opacity=0.5] fill between[of=A and B,soft 95 clip={domain=-1:0},]; 96 \addplot[fill=gray,fill opacity=0.5] fill between[of=C and B,soft 97 clip={domain=0:2},]; 98 \node[] at (axis cs:2,1.5) [below left] {X}; 99 \node[draw, circle, inner sep=1pt, fill=red, label={$x_0$}] at (axis cs:1, 0) {}; 100 \end{axis} 101 \end{tikzpicture} 102 \label{fig: ex7.2} 103 \end{figure} 104 Then the tangent cone is obviously 105 \begin{align} 106 T_X(x_0) = \left\{ d: d \in \mathbb{R}^{2} \right\} 107 \end{align} 108 For the linearized tangent cone we calculate $g_1(x_0) = 0$ and $g_2(x_0)=0$, 109 thereby $\mathcal{A}(x_0)=\{1, 2\}$ and 110 \begin{align} 111 T_\text{lin}(x_0)&= 112 \left\{ d\in\mathbb{R}^{2}: \begin{pmatrix} -1\\0 \end{pmatrix}^{T}d\le 0,\; 113 \begin{pmatrix} -1 \\ -1 \end{pmatrix}^{T}d\le 0 \right\} \\ 114 &= \left\{ \begin{pmatrix} \lambda \\ \lambda \end{pmatrix}, 115 \begin{pmatrix} \lambda \\ -\lambda \end{pmatrix}:\; \lambda \ge 116 0\right\}. 117 \end{align} 118 In this case $x_0$ also does not satisfy the ABADIE-CQ. 119 \subsection{Exercise 8} 120 Let $(x^{*}, \lambda^{*}, \mu^{*})$ be a KKT point of the optimization 121 problem 122 \begin{align} 123 \text{min}\quad & f(x),\\ 124 \text{s.t.}\quad & g_i(x) \le 0, i=1,\ldots,m\nonumber\\ 125 &h_j(x) = 0, j=1,\ldots,p\nonumber\\ 126 & x \in \mathbb{R}^{n}\nonumber 127 \end{align} 128 for $f, g_i, h_i:\mathbb{R}^{n}\to \mathbb{R}$ continuously differentiable 129 functions. Prove that $x^{*}$ is a critical point of the optimization point, 130 namely that it holds 131 \begin{align} 132 \nabla f(x^{*})^{T}\ge 0 \;\; \forall d\in T_X(x^{*}), 133 \end{align} 134 where $X = \left\{ x \in R^{n}: g_i(x) \le 0, i=1,\ldots,m, h_j(x) = 0, 135 j=1,\ldots,p\right\}$. Given a critical point $x^{*}$ when do Lagrange 136 multipliers $\lambda^{*}, \mu^{*}$ exist such that $(x^{*}, \lambda^{*}, 137 \mu^{*})$ is a KKT point? 138 \newline 139 Firs of all if $(x^{*}, \lambda^{*}, \mu^{*}) $ is a KKT point then 140 \begin{align} 141 &\nabla_x L(x^{*},\lambda^{*}, \mu^{*}) = 0\\ 142 &\nabla f(x^{*}) + \sum_{i=1}^{m} \lambda_i^{*} \nabla g_i(x^{*}) 143 + \sum_{j=1}^{p} \mu_j^{*} \nabla h_j(x^{*}) = 0 144 \end{align} 145 is satisfied for the Lagrangian. Then we can take the scalar product with $d 146 \in T_X(x^{*})$. We know that $\nabla g_i(x^{*})^{T} d \le 0$ and $\nabla h_j 147 (x^{*})^{T}d =0$ for all $i = 1,\ldots,m$ and $j=1,\ldots,p$ and 148 $\lambda_i^{*}\ge 0$ which means 149 \begin{align} 150 0 &= \nabla f(x^{*})^{T}d + \sum_{i=1}^{m} \lambda_i^{*} \nabla g_i(x^{*})^{T}d 151 + \sum_{j=1}^{p} \mu^{*}_j \nabla h_j(x^{*})^{T}d \\ 152 &= \nabla f(x^{*})^{T}d + \sum_{i=1}^{m} \lambda_i^{*} \nabla 153 g_i(x^{*})^{T}d\\ 154 &\le \nabla f(x^{*})^{T}d. 155 \end{align} 156 This concludes 157 \begin{align} 158 \nabla f(x^{*})^{T}d \ge 0. 159 \end{align} 160 Now if $x^{*}$ is a critical point then it is a local minimum. If it 161 fulfills the ABADIE-CQ condition then there exist $\lambda^{*} \in 162 \mathbb{R}^{m}$ and $\mu^{*}\in\mathbb{R}^{p}$ such that $(x^{*}, 163 \lambda^{*}, \mu^{*})$ is a KKT point. We know that $X$ is convex and $x^{*}$ 164 fulfills the ABADIE-CQ then $\nabla f(x^{*}) \in \left( T_X(x^{*})^{*} 165 \right)$ and $\left( T_X(x^{(*)} \right)^{*} = (T_\text{lin}(x^{*}))^{*}$. 166 This means that $\nabla f(x^{*}) \in \left( T_\text{lin}(x^{*} \right)^{*}$. 167 By Farkas Lemma there exist $\lambda_i^{*} \ge 0$ and $\mu_j^{*}$, 168 $i=1,\ldots,m$, $j=1,\ldots,p$ such that $\nabla_x L(x^{*}, \lambda^{*}, 169 \mu^{*}) = 0$, then $(x^{*}, \lambda^{*}, \mu^{*})$ is a KKT point. 170 \subsection{Exercise 9} 171 Consider the optimization problem 172 \begin{align} 173 \text{min}\quad & x_1^{2}\left( x_2 + 1 \right)^{2} ,\\ 174 \text{s.t.}\quad &x_1^{3} - x_2 \le 0\\ 175 & x_2 \le 0. 176 \end{align} 177 Show that $x^{*} = (0, 0)^{T}$ fulfills ABADIE-CQ but not MFCQ. 178 \newline 179 The domain $X$ is defined by $x_1^2 \ge x^2$ and $x_2 \ge 0$, 180 \begin{align} 181 X = \left\{ (x_1, x_2) \in \mathbb{R}^{2}: x_1^{2}\ge x_2 \ge 0 \right\}, 182 \end{align} 183 graphically 184 \begin{figure}[H] 185 \centering 186 \begin{tikzpicture}[yscale=1, xscale=1] 187 \begin{axis}[ 188 xmin=-2, xmax=2, 189 ymin=-0.5, ymax=2, 190 axis lines = middle, 191 xlabel=$x_1$, 192 ylabel=$x_2$, 193 ] 194 \addplot[domain=-2:2, samples=100, color=gray, name path=A]{x^2}; 195 \addplot[domain=-2:2, samples=100, name path=B]{0}; 196 \addplot[fill=gray,fill opacity=0.5] fill between[of=A and B,soft 197 clip={domain=-2:2},]; 198 \node[] at (axis cs:2,2) [below left] {X}; 199 \node[draw, circle, inner sep=1pt, fill=red, label=above 200 right:{$x^{*}$}] at 201 (axis cs:0, 0) {}; 202 \end{axis} 203 \end{tikzpicture} 204 \label{fig: ex9} 205 \end{figure} 206 meaning that 207 \begin{align} 208 T_X(x^{*}) = \left\{\begin{pmatrix} -\lambda \\ 0 \end{pmatrix}, 209 \begin{pmatrix} \lambda \\ 0 \end{pmatrix}:\; \lambda \ge 0 \right\}, 210 \end{align} 211 Then 212 \begin{align} 213 T_\text{lin}(x^{*}) 214 &= \left\{d\in\mathbb{R}^{2}: \begin{pmatrix} 0\\1 215 \end{pmatrix}^{T}d \le 0,\; \begin{pmatrix} 0 \\ -1 216 \end{pmatrix}^{T}d\le 0 \right\} \\ 217 &= \left\{ \begin{pmatrix} -\lambda \\ 0 \end{pmatrix}, \begin{pmatrix} 218 \lambda , 0 \end{pmatrix}:\; \lambda \ge 0 \right\}. 219 \end{align} 220 This means that $x^{*}$ fulfills the ABADIE-CQ condition. On the other hand 221 MFCQ is fulfilled only if there exists $d\in\mathbb{R}^{2}$ such that $\nabla 222 g_i(x^{*})^{T}d < 0$, for all $i\in \mathcal{A}(x^{*})$ but the problem is the 223 strict constraint 224 \begin{align} 225 \nabla g_1 (x^{*}) = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \quad 226 \nabla g_2 (x^{*}) = \begin{pmatrix} 0 \\ -1 \end{pmatrix}. 227 \end{align} 228 Any feasible solutions are of the form $(\pm \lambda , 0)^{T}$, $\lambda \ge 229 0$. Both cases always equal to $0$. 230 \subsection{Exercise 10} 231 Consider the optimization problem 232 \begin{align} 233 \text{min}\quad & x_1^{2}\left( x_2 + 1 \right)^{2} ,\\ 234 \text{s.t.}\quad &-x_1^{3} - x_2 \le 0\\ 235 & -x_2 \le 0. 236 \end{align} 237 Show that $x^{*} = (0, 0)^{T}$ fulfills MFCQ but not LICQ. 238 \newline 239 The domain $X$ is defined by $x_1^2 \ge -x^2$ and $x_2 \ge 0$, 240 \begin{align} 241 X = \left\{ (x_1, x_2) \in \mathbb{R}^{2}: x_2 \ge 0 \right\}, 242 \end{align} 243 and $g_1(x^{*}) = 0$ and $g_2(x^{*}) = 0$ so $\mathcal{A}(x^{*}) = \{1,2\}$. 244 \begin{align} 245 \nabla g_1(x^{*}) = \begin{pmatrix} 0\\-1 \end{pmatrix},\quad \nabla 246 g_2(x^{*}) = \begin{pmatrix} 0 \\ -1 \end{pmatrix} 247 \end{align} 248 For strict inequality $\nabla g_i(x^{*})^{T}d < =$ for all $i \in 249 \mathcal{A}(x^{*})$ we have that $d = (0, \lambda)$ with $\lambda > 0$. This 250 means $x_0$ fulfills MFCQ. On the other hand LICQ is fulfilled if 251 \begin{align} 252 \{\nabla g_i(x^{*})\}_{i\in\mathcal{A}(x^{*})} 253 \end{align} 254 are linearly independent. But in our case $\nabla g_1(x^{*}) = \nabla 255 g_2(x^{*})$, meaning that $x_0$ does not fulfill LICQ. 256 \subsection{Exercise 11} 257 Let $U \subseteq \mathbb{R}^{n}$ be a nonempty, open convex set and $f \in U 258 \to \mathbb{R}$ a differentiable function on $U$. Prove that the following 259 statements are equivalent. 260 \begin{enumerate} 261 \item $f$ is convex on $U$ 262 \item $\langle\nabla f(x),y-x\rangle \le f(y) - f(x) \quad \forall x, y \in U$ 263 \item $\langle\nabla f(x)-\nabla f(y),y-x\rangle \le 0 \quad \forall x, y \in U$ 264 \item if f is twice differentiable on $U$, then $\nabla^{2}f(x)$ is 265 positively semi definite for every $x \in U$. 266 \end{enumerate} 267 We start with (1) $\Leftrightarrow$ (2).\newline 268 Ad $\Rightarrow$: $f$ is convex, then for all $x, y \in U$, $\lambda \in [0, 269 1]$ we have 270 \begin{align} 271 f\left( (1-\lambda)x + \lambda y \right) 272 &\le (1-\lambda)f(x) + \lambda(y)\\ 273 &=f(x) + \lambda\left( f(y) - f(x) \right)\\ 274 \frac{f\left( (1-\lambda)x + \lambda y \right) -f(x)}{\lambda} 275 &\le f(y) - f(x). 276 \end{align} 277 Letting $\lambda \downarrow 0 $ we get 278 \begin{align} 279 \nabla f(x)^{T}(y-x) \le f(x) - f(y) 280 \end{align} 281 Ad $\Leftarrow$: we have that $\forall x, y \in U$: 282 \begin{align} 283 \nabla f(x)^{T}(y-x) \le f(x) - f(y). 284 \end{align} 285 Since $U$ is convex then the above also holds for $z \in U$ where $z = 286 (1-\lambda)x + \lambda y$, then 287 \begin{align} 288 &f(x) \ge f(z) + \nabla f(z)^{T}(x-z) \quad | \cdot (1-\lambda)\\ 289 &f(y) \ge f(z) + \nabla f(z)^{T}(y-z) \quad | \cdot \lambda 290 \end{align} 291 adding both of them together we get 292 \begin{align} 293 (1-\lambda)f(x) + \lambda f(y) 294 &\ge f(z) + \nabla f(z)^{T}((1-\lambda) x + \lambda y - z) \\ 295 &= f(z)\\ 296 &= f((1-\lambda)x + \lambda y). 297 \end{align} 298 This shows that $f$ is convex on $U$. 299 \newline 300 Next we show (2) $\Leftrightarrow$ (3).\newline 301 Ad $\Rightarrow$: We start with 302 \begin{align} 303 &f(y) \ge f(x) + \nabla f(x)^{T}(y-x)\\ 304 &f(x) \ge f(y) + \nabla f(y)^{T}(x-y). 305 \end{align} 306 Adding them together we get 307 \begin{align} 308 \nabla f(y)^{T}(y-x) - \nabla f(x)^{T}(y-x) \ge 0\\ 309 \left( \nabla f(y)^{T} - \nabla f(x)^{T} \right) (y-x) \ge 0. 310 \end{align} 311 Ad $\Leftarrow$: We can just do the same operations as in $\Rightarrow$ in 312 reverse. 313 \newline 314 Now we prove (2) $\Leftrightarrow$ (4).First we consider in one dimension and 315 then generalize 316 \newline 317 Ad $\Rightarrow$: . In 318 $U \subseteq \mathbb{R}$ we have that $\forall x ,y \in U$ 319 \begin{align} 320 &f(y) \ge f(x) + f(x)'(y-x)\\ 321 &f(x) \ge f(y) + f(y)'(x-y). 322 \end{align} 323 Let $x < y$, then 324 \begin{align} 325 &f'(x)(y-x) \le f(y) - f(x) \le f'(y) (y- x) \quad | \frac{1}{(y-x)^{2}}\\ 326 &\frac{f'(y) - f'(x)}{y-x} \ge 0 \quad | y\to x\\ 327 &f''(x) \ge 0 \quad \forall x \in U. 328 \end{align} 329 Ad $\Leftarrow$: We use Taylors expansion formula for $f(y)$ in $x \in U$ 330 \begin{align} 331 f(y) = f(x) + f'(x)(y-x) + \frac{1}{2}f''(\xi) (y-x)\quad \xi \in [x,y]\\ 332 f(y) \ge f(x) + f'(x)(y-x). 333 \end{align} 334 In general dimensions convexivity means convexivity along all directions, 335 i.e. $f : U\subseteq \mathbb{R}^{n} \to \mathbb{R}$ is convex if 336 \begin{align} 337 g(\alpha) = f(x + \alpha d) 338 \end{align} 339 is convex $\forall x \in U$ and $\forall d \in \mathbb{R}^{n}$. This is 340 exactly the case if 341 \begin{align} 342 g''(\alpha) = d^{T}\nabla^{2}f(x+\alpha d) d \ge 0 \quad \forall x \in 343 U\; \forall d \in \mathbb{R}^{n} \; \forall \alpha \in \mathbb{R} 344 \end{align} 345 such that $x + \alpha d \in U$ so $f$ is convex if and only if 346 \begin{align} 347 \nabla f(x) \ge 0 \quad \forall x \in U \qed 348 \end{align} 349 \subsection{Exercise 12} 350 Let $c: \mathbb{R}\to \mathbb{R}$ be defined as 351 \begin{align} 352 c(y) = 353 \begin{cases} 354 (y+1)^{2} \qquad &y < -1\\ 355 0 \qquad &-1 \le y \le 1\\ 356 (y-1)^{2} \qquad &y > 1 357 \end{cases} 358 \end{align} 359 Let $g_1, g_2: \mathbb{R}^{2}\to \mathbb{R}$ 360 \begin{align} 361 g_1(x_1, x_2) = c(x_1) - x_2\\ 362 g_2(x_1, x_2) = c(x_1) + x_2\\ 363 \end{align} 364 Let $f: \mathbb{R}^{2} \to \mathbb{R}$ be a convex function and continuously 365 differentiable. Show that for the convex optimization problem 366 \begin{align} 367 \text{min}\quad & f(x),\\ 368 \text{s.t.}\quad & g_i(x) \le 0, i=1,2\nonumber\\ 369 & x \in \mathbb{R}^{2}\nonumber 370 \end{align} 371 ABADIE-CQ holds at $x^{*}= (0, 0)^{T}$ SLATER-CQ is not satisfied. 372 \newline 373 Bellow is a graphical representation of, $c(x_1)$, $g_1(x) \le 0$ and 374 $g_2(x)$ 375 \begin{figure}[H] 376 \centering 377 \begin{tikzpicture}[yscale=1, xscale=1] 378 \begin{axis}[ 379 xmin=-5, xmax=5, 380 ymin=-1, ymax=5, 381 axis lines = middle, 382 xlabel=$x_1$, 383 ylabel=$x_2$, 384 ] 385 \addplot[domain=1:5, samples=100, color=red, name 386 path=A]{(x-1)^2}; 387 \addplot[domain=-1:-5, samples=100, name path=B, color=red]{(x+1)^2}; 388 389 \addplot[domain=-5:5, samples=100, name path=D,, color=gray, 390 opacity=0]{0}; 391 \addplot[domain=-5:5, samples=100, name path=E,, color=gray, 392 opacity=0]{-1}; 393 394 \addplot[domain=-5:5, samples=100, name path=F,, color=blue, 395 opacity=0]{5}; 396 397 \addplot[fill=gray,fill opacity=0.3] fill between[of=D and E,soft 398 clip={domain=-5:5},]; 399 \addplot[fill=gray,fill opacity=0.3] fill between[of=B and D,soft 400 clip={domain=-5:-1},]; 401 \addplot[fill=gray,fill opacity=0.3] fill between[of=A and D,soft 402 clip={domain=1:5},]; 403 404 \addplot[fill=blue,fill opacity=0.3] fill between[of=A and F,soft 405 clip={domain=1:5},]; 406 \addplot[fill=blue,fill opacity=0.3] fill between[of=B and F,soft 407 clip={domain=-1:-5},]; 408 \addplot[fill=blue,fill opacity=0.3] fill between[of=D and F,soft 409 clip={domain=-1:1},]; 410 411 \addplot[domain=-1:1, samples=100, name path=C, color=red]{0}; 412 413 \node[color=red] at (axis cs:3.5,4) [above right] {$c(x_1)$}; 414 \node[color=gray] at (axis cs:2.5,2) [below right] {$g_2(x) \le 0$}; 415 \node[color=blue] at (axis cs:-1.3,3.5) [] {$g_1(x) \le 0$}; 416 \node[draw, circle, inner sep=1pt, fill=red, label=above 417 right:{$x^{*}$}] at 418 (axis cs:0, 0) {}; 419 \end{axis} 420 \end{tikzpicture} 421 \label{fig: ex12} 422 \end{figure} 423 So $X$ has only elements on the curve $c(x)$, i.e. $X = \{x \in 424 \mathbb{R}^{2}: g_1(x) \le 0, g_2(x) \le 0\} = \{(x_1, c(x_1))^{T} : x_1 \in 425 \mathbb{R}\}$ and thereby the tangent cone of $X$ at $x^{*}$ consists of 426 tangent vectors of $c(x)$ at $x^{*}$ 427 \begin{align} 428 T_X(x^{*}) = \left\{\begin{pmatrix} \lambda\\ 0 \end{pmatrix}, \begin{pmatrix} 429 -\lambda\\ 0\end{pmatrix} : \lambda \ge 0 \right\}. 430 \end{align} 431 For the linearized tangent cone we have that $g_1(x^{*}) = c(0) = 0 $ and 432 $g_2(x^{*})= c(0) = 0$, then the gradients at $x^{*}$ are 433 \begin{align} 434 \nabla g_1(x^{*}) = \begin{pmatrix} 0\\1 \end{pmatrix}, \qquad 435 \nabla g_2(x^{*}) = \begin{pmatrix} 0\\-1 \end{pmatrix}. 436 \end{align} 437 Thereby 438 \begin{align} 439 T_\text{lin}(x^{*}) 440 &= \left\{ d \in \mathbb{R}^{2}: \nabla g_1(x)^{T}d \le 0, \nabla 441 g_2(x)^{T}d\le 0 \right\} \\ 442 &= \left\{ \begin{pmatrix} \lambda\\0 \end{pmatrix}, \begin{pmatrix} 443 -\lambda \\ 0 \end{pmatrix} : \lambda \ge 0 \right\}. 444 \end{align} 445 We have that $x^{*}$ satisfies ABADIE-CQ. 446 \newline 447 In our case SLATER-CQ is fulfilled if there exists an $x' \in \mathbb{R}^{2}$ 448 such that $g_i(x') < 0$ for all $i = 1,2$. The problem arises because in case 449 of strict inequality the domains defined by $g_1(x) < 0$ and $g_2(x) < 0$ do 450 not match for any $x$ as seen the figure above. In the relaxed case they 451 match exactly at the line $c(x_1)$. But $c(x_1) \ge 0$. Meaning that there 452 exists no $x'$ such that SLATER-CQ is satisfied (in our case). 453 \end{document}