Matematické Fórum

Neth · 28. 01. 2015 00:36

Zdravím všechny, potřebovala bych poradit s následujícím příkladem.

Mám z definice konvexní množiny dokázat, že tato množina je konvexní:

$\lbrace \:\textbf{x}\in \mathbb{R}^{n} |\:\textbf{x}^{T}\textbf{Ax} \le 1 \rbrace$ , kde A je pozitivně semidefinitní.

V předchozích příkladech jsme si vždycky zvolili dva vektory patřící do této množiny a a dokázali jsme, že tam patří i jejich konvexní kombinace. V tomhle případu si ale nejsem ale úplně jistá, jak to provést. Pokud si vezmu například nějaké vektory x a y a budu předpokládat, že:

$\alpha\textbf{x}^{T}\textbf{Ax} \le \alpha$

a

$(1-\alpha)\textbf{y}^{T}\textbf{Ay} \le (1-\alpha)$

a to sečtu dostanu:

$\alpha\textbf{x}^{T}\textbf{Ax} +(1-\alpha)\textbf{y}^{T}\textbf{Ay} \le 1$

tak mi není jasné, jak z tohoto dostanu požadovaný (nebo alespoň podle mě požadovaný) tvar:

$(\alpha\textbf{x}+(1-\alpha)\textbf{y})^{T}\textbf{A}(\alpha\textbf{x}+(1-\alpha)\textbf{y}) \le 1$

Jdu na to dobře? Špatně? Mám správné předpoklady?

Předem moc děkuju za odpověď.

kafe_arabica

Ahoj.

Choď na to od konca. Roznásob si posledný riadok a odhaduj koeficienty a potom členy. Napr., vieš, že platí $\alpha\leq1$ , rovnako $1-\alpha\leq1$ , a pre x,y platí $x^TAx\leq1$ .

Rumburak

↑ Neth:

Zdravím také.

Je užitečné dokazované tvrzení přesně zformulovat:

Platí-li $\textbf{x}, \textbf{y} \in \mathbb{R}^{n} , \textbf{x}^{T}\textbf{Ax} \le 1, \textbf{y}^{T}\textbf{Ay} \le 1$ , kde matice $A$ je pozitivně semidefinitní,
potom pro libovolná $\alpha \ge 0, \beta \ge 0$ splňující $\alpha + \beta = 1$ je $(\alpha\textbf{x}+ \beta\textbf{y})^{T}\textbf{A}(\alpha\textbf{x}+ \beta\textbf{y}) \le 1$ .

Neth · 28. 01. 2015 15:17

↑ Rumburak:

Děkuju moc za přesnější zápis :)

Neth · 03. 02. 2015 20:13

Neví, prosím, někdo?

Rumburak · 09. 02. 2015 10:01

↑ Neth:

A jak Ti vyšlo roznásobení výrazu $(\alpha\textbf{x}+ \beta\textbf{y})^{T}\textbf{A}(\alpha\textbf{x}+ \beta\textbf{y})$ ? (Viz rada od ↑ kafe_arabica:)

Neth · 09. 02. 2015 17:11

Takhle:

$\alpha^2\textbf{x}^T\textbf{Ax} + 2\alpha \beta\textbf{x}^T\textbf{Ay} + \beta^2\textbf{y}^T\textbf{Ay}$

Rumburak

↑ Neth:

Mně to vychází

$... = \alpha^2\textbf{x}^T\textbf{Ax} + \alpha \beta(\textbf{x}^T\textbf{Ay}+ \textbf{y}^T\textbf{Ax}) + \beta^2\textbf{y}^T\textbf{Ay}$ .

Ale nechci si hrát na chytrého - další postup zatím nevidím.

Neth · 09. 02. 2015 17:42

Ty prostřední dva členy jsou stejné, kdyby sis to roznásobil po složkách, tak by to bylo vidět hned.

jarrro · 09. 02. 2015 19:34

$\alpha^2\textbf{x}^T\textbf{Ax} + 2\alpha \beta\textbf{x}^T\textbf{Ay} + \beta^2\textbf{y}^T\textbf{Ay}\leq \alpha^2+2\alpha\beta+\beta^2=1$

Rumburak · 10. 02. 2015 10:42

↑ Neth:

O.K. Na to roznásobení po složkách jsem bohužel neměl dost času.

Rumburak · 10. 02. 2015 10:43

↑ jarrro:

Ahoj.

Zdá se, že jsi použil vztah $\textbf{x}^T\textbf{Ay} \le 1$ . Můžeš, prosím, naznačit, jak k němu dojít ?

Neth · 10. 02. 2015 11:29

↑ Rumburak:

To naprosto chápu.

↑ jarrro:

Mohla bych se, prosím, zeptat, jak jsi k tomu došel?

Rumburak · 10. 02. 2015 11:52

↑ Neth:

Jestliže z původních předpokladů $\textbf{x}^T\textbf{Ax} \le 1$ , $\textbf{y}^T\textbf{Ay} \le 1$ plyne i $\textbf{x}^T\textbf{Ay} \le 1$
(viz můj dotaz ↑ Rumburak: na kolegu ↑ jarrro:), potom

$\alpha^2\textbf{x}^T\textbf{Ax} + 2\alpha \beta\textbf{x}^T\textbf{Ay} + \beta^2\textbf{y}^T\textbf{Ay} \le \alpha^2\cdot 1 + 2\alpha \beta \cdot 1 + \beta^2\cdot 1 = (\alpha + \beta)^2$ .

O nezáporných číslech $\alpha, \beta$ jsme přadpokládali, že jejich součet je 1.

Neth · 10. 02. 2015 12:02

↑ Rumburak:

Děkuju mnohokrát, už to tam vidím! Jen mám neblahý pocit, že $\textbf{x}^T\textbf{Ay} \le 1$ z toho automaticky neplyne.

Neth · 10. 02. 2015 12:11

Nepomůže nějak vědomí, že výraz $\textbf{x}^T\textbf{Ax} + 2\textbf{x}^T\textbf{Ay} + \textbf{y}^T\textbf{Ay}$ je vždy kladný nebo rovno nula (kvůli matici pozitivně semidefinitní)?

jarrro · 11. 02. 2015 11:58

tiež som sa pozastavoval na tom či platí $\textbf{x}^T\textbf{Ay} \le 1$ (písal som príspevok za predpokladu, že platí)
nepomohol by rozklad matice A na B.B ?

xxMari · 11. 02. 2015 17:11

Matica $A=A^T$ určuje na $\mathbb{R}^n$ skalárny súčin $\langle x,y\rangle_A=x^TAy$ pre $x,y\in\mathbb{R}^n$ v prípade, že je pozitívne definitná. Pretože v našom uvažovanom prípade je $A$ pozitívne semidefinitná neplatí $\langle x,x\rangle_A=x^TAx=0\Leftrightarrow x=0$ , avšak pri dôkaze Cauchy-Schwarzovej nerovnosti [1] sa tento fakt používa až pri určovaní podmienok pre rovnosť, preto ihneď máme

[1] napr. http://www.artofproblemsolving.com/Wiki … Inequality Proof1

Matematické Fórum

#1 28. 01. 2015 00:36

Konvexní množina

#2 28. 01. 2015 10:36 — Editoval kafe_arabica (28. 01. 2015 10:36)

Re: Konvexní množina

#3 28. 01. 2015 12:27 — Editoval Rumburak (28. 01. 2015 13:46)

Re: Konvexní množina

#4 28. 01. 2015 15:17

Re: Konvexní množina

#5 03. 02. 2015 20:13

Re: Konvexní množina

#6 09. 02. 2015 10:01

Re: Konvexní množina

#7 09. 02. 2015 17:11

Re: Konvexní množina

#8 09. 02. 2015 17:33 — Editoval Rumburak (09. 02. 2015 17:37)

Re: Konvexní množina

#9 09. 02. 2015 17:42

Re: Konvexní množina

#10 09. 02. 2015 19:34

Re: Konvexní množina

#11 10. 02. 2015 10:42

Re: Konvexní množina

#12 10. 02. 2015 10:43

Re: Konvexní množina

#13 10. 02. 2015 11:29

Re: Konvexní množina

#14 10. 02. 2015 11:52

Re: Konvexní množina

#15 10. 02. 2015 12:02

Re: Konvexní množina

#16 10. 02. 2015 12:11

Re: Konvexní množina

#17 11. 02. 2015 11:58

Re: Konvexní množina

#18 11. 02. 2015 17:11

Re: Konvexní množina

Zápatí