DL-CO pset 2

First order condition

Let $f$ be a differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$ over a convex set $K$. Then $f$ is convex if and only if for all $x,y\in K$

$$f(y)⩾f(x)+⟨\nabla f(x),y-x⟩.$$

1.) Verify the following statements. (5pts)

(a) $e^{ax}$ is convex on $\mathbb{R}$ for any $a\in \mathbb{R}$.
Az elsőrendű kritérium szerint $e^{ax}$ akkor és csak akkor konvex, ha $e^{ay}\ge e^{ax}+⟨(e^{ax}{)}^{\prime },y-x⟩$

$$e^{ay}\ge e^{ax}+(y-x)a{e}^{ax}$$ $$e^{ay}\ge e^{ax}(1+a(y-x))$$ $$\frac{e^{ay}}{e^{ax}}\ge 1+a(y-x)$$ $$e^{a(y-x)}\ge 1+a(y-x)$$

Ami már egy ismert állítás $z=a(y-x)$-el $e^z\ge 1+z$.
(b) $x^a$ is convex on ${\mathbb{R}}_{>0}$ when $a⩾1$ or $a⩽0$, otherwise it is concave.
A másodrendű kritérium szerint $x^a$ konvex akkor és csak akkor, ha ${\nabla }^2{x}^a⪰0$ minden $x\in \mathrm{dom}{x}^a$ -ra.

$${\nabla }^2{x}^a⪰0⟺(x^a{)}^{\prime \prime }\ge 0$$ $$(x^a{)}^{\prime \prime }=(a{x}^{a-1}{)}^{\prime }=a(a-1)x^{a-2}$$

A fenti pontosan akkor nemnegatív, ha $a\ge 1$ vagy $a\le 0$ és pontosan akkor nem pozitív, ha $a\in [0,1]$.

(c) $\log x$ is concave on ${\mathbb{R}}_{>0}$.
Tudjuk, hogy $\log x$ akkor konkáv, ha $-\log x$ konvex.
A másodrendű kritérium szerint $-\log x$ akkor és csak akkor konvex, ha $(-\log x{)}^{\prime \prime }\ge 0$

$$(-\log x{)}^{\prime \prime }={\left(-\frac{1}{x}\right)}^{\prime }=\frac{1}{x^2}\ge 0,\forall x\ge 0$$

(d) $x\log x$ is convex on ${\mathbb{R}}_{>0}$.
A másodrendű kritérium szerint $x\log x$ konvex akkor és csak akkor, ha $(x\log x{)}^{\prime \prime }\ge 0,\forall x\in {\mathbb{R}}^{+}$.

$$(x\log x{)}^{\prime \prime }={\left(\log x+x\frac{1}{x}\right)}^{\prime }=(\log x+1{)}^{\prime }=\frac{1}{x}\ge 0,\forall x\in {\mathbb{R}}^{+}$$

(e) $\max \left\{x_1,\dots ,x_n\right\}$ is convex on ${\mathbb{R}}^n$.
Mivel $({\mathbb{R}}^n,||\cdot |{|}_{\max })$ normált tér, ahol $||x|{|}_{\max }:=\max \{x_1,\dots ,x_n\}$, ezért

$$||\lambda x+(1-\lambda )y|{|}_{\max }\le ||\lambda x|{|}_{\max }+||(1-\lambda )y|{|}_{\max }=|\lambda |\cdot ||x|{|}_{\max }+|1-\lambda |\cdot ||y|{|}_{\max }$$

Továbbá, mivel $\lambda \in [0,1]$, ezért $|\lambda |=\lambda$ és $|1-\lambda |=1-\lambda$.
Tehát a fenti két széléből kapjuk a következőt:

$$||\lambda x+(1-\lambda )y|{|}_{\max }\le \lambda \cdot ||x|{|}_{\max }+(1-\lambda )\cdot ||y|{|}_{\max }$$

Jelölje $f(x):=\max \{x_1,\dots ,x_n\}=||x|{|}_{\max }$, ekkor pont a konvex függvény definícióját kapjuk, azaz $f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)$.

2.) Consider the optimization problem

$$\begin{array}{cc}\min & x^2+2x+1\\ \text{ s.t. }& (x+2)(x-4)⩽0\end{array}$$

with variable $x\in \mathbb{R}$.
(a) Give the feasible set, the optimal value, and the optimal solution. (1pt)
Ahhoz, hogy a feltétel teljesüljön kell, hogy pontosan az egyik tényező legyen negatív vagy $0$. Tehát $x\in [-2,4]$.
Ekkor a feladat ekvivalens azzal, hogy egy függvénynek keressük a minimum helyét egy zárt intervallumon, amit úgy tudunk megtalálni, hogy megkeressük hol $0$ a deriváltja a függvénynek és megvizsgáljuk az intervallum széleit.

$$0=(x^2+2x+1{)}^{\prime }=2x+2⟹x=-1$$

Tehát a vizsgálandó helyek: $-2,-1,4$

$$f(-2)=1,f(-1)=0,f(4)=25$$

Tehát az optimum hely $x=-1$ és optimum érték $f(-1)=0$.

(b) Plot the objective $x^2+2x+1$ versus $x$. On the same plot, show the feasible set, optimal point and value, and plot the Lagrangian $L(x,\lambda )$ versus $x$ for a few positive values of $\lambda$. Derive and sketch the Lagrange dual function $g$. (2pts)

$$L(x,\lambda )=x^2+2x+1+\lambda (x+2)(x-4)$$ $$g(\lambda )=\underset{x}{\inf }L(x,\lambda )=\underset{x}{\inf }\{x^2+2x+1+\lambda (x+2)(x-4)\}$$

(c) State the dual problem, and verify that it is a concave maximization problem. Find the dual optimal value and dual optimal solution ${\lambda }^{\ast }$. (2pts)

$$\begin{array}{cc}\max & {\inf }_x\{x^2+2x+1+\lambda (x+2)(x-4)\}\\ s.t.& \lambda \ge 0\end{array}$$

A célfüggvény a következőképpen írható fel:

$$\underset{x}{\inf }\{(1+\lambda )x^2+(2-2\lambda )x-7\}$$

Itt az $\inf$ -et lecserélhetjük $\min$ -re és tudjuk, hogy ott van minimum helye egy függvénynek ahol a deriváltja $0$.

$$((1+\lambda )x^2+(2-2\lambda )x-7{)}^{\prime }=0$$ $$\begin{array}{c}2(1+\lambda )x+2-2\lambda =0\\ ⟹x=\frac{\lambda -1}{\lambda +1}\end{array}$$ $$⟹g(\lambda )={\left(\frac{\lambda -1}{\lambda +1}\right)}^2+2\frac{\lambda -1}{\lambda +1}+1+\lambda \left(\frac{\lambda -1}{\lambda +1}+2\right)\left(\frac{\lambda -1}{\lambda +1}-4\right)$$

Erről be kell még látni hogy konkáv, tehát $g(\lambda {)}^{\prime \prime }\le 0$.

Az optimum hely $\lambda =0$ és az optimum érték ${\inf }_x\{x^2+2x+1\}=0$.

related: DL-CO