If this is not the case, the perceptron algorithm will not terminate, but surprisingly it will stay bounded. See Block and Levin, "On the Boundedness of an Iterative Procedure for Solving a System of Linear Inequalities", Proc. Amer. Math. Soc., Vo. 26., No. 2, (1970), 229-245.

There exists \(M\) only dependent on the vectors \(v_1, \dots, v_m\), such that

$$ |\alpha_i| \leq |\alpha_1| + M $$

for every \(i = 1, 2, \dots\). In particular, if the vectors have rational coordinates, the algorithm will eventually cycle.

Use Lemma 4.29 (and Exercise 4.33).

``` from scipy.optimize import linprog

Maximize x1 + x2 <=> minimize -(x1 + x2)

c = [-350, -300] A = [[18, 12], [1, 1], [6, 8], [-1, 0], [0, -1]] <br /> b = [3132, 200, 1440, 0, 0]

res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None))

print("Optimal Value:", -res.fun) print("occurs in") for i, v in enumerate(res.x, start=1): print("x_%d = %f" % (i, v)) ```

Bonus question: can you generalize this to a criterion for \(A\) being positive semidefinite? Why is it not enough to simply require

$$ a\geq 0\qquad\text{and}\qquad a b - c^2 \geq 0? $$

Composition in python

``` from sympy import symbols

x, y = symbols('x y')

def f(w): u, v = w return [5u + 6v, 7u + 8v]

def g(w): x, y = w return [x + 2y, 3x + 4*y]

f(g([x, y])) ```

def f(n:int)->int: return(n+1) shows python with type annotations. Are they enforced?

from sympy import Rational, N

N(Rational(355, 113), 120)

Another example is here just

$$ \frac{1}{2} + \frac{1}{2} = \frac{2}{4} $$

But \(\frac{2}{4} = \frac{1}{2}\) so that you end up not adding anything!

\(\mathbb{N}\) denotes the natural numbers i.e., \({1, 2, 3, \dots}\). \(\emptyset\) denotes the empty set i.e., the set containing no elements.

Forgot to include Or

One of the better ones relates to viewing \(p\implies q\) as a promise, so the promise is broken (false) if and only if \(p\) is true and \(q\) is false. You promise that \(q\) is true if \(p\) is true. You do not promise anything if \(p\) is false, so technically there you have kept your promise.

Notation \(m\) clashes with notation \(m\) below.

The entry \(2\) should here be \(1\).

This should be

$$ \alpha = \lambda_1 y_1 v_1 + \cdots + \lambda_m y_m v_m $$

Notice that \(\beta\) can be found of the binding condition in the primal problem for some \(\lambda_i > 0\).

Differentiable

roots

Compare this with the limit notation introduced in Chapter 5 below the definition of continuity.

If this is not the case, the perceptron algorithm will not terminate, but surprisingly it will stay bounded. See Block and Levin, "On the Boundedness of an Iterative Procedure for Solving a System of Linear Inequalities", Proc. Amer. Math. Soc., Vo. 26., No. 2, (1970), 229-245.

There exists \(M\) only dependent on the vectors \(v_1, \dots, v_m\), such that

$$ |\alpha_i| \leq |\alpha_1| + M $$

for every \(i = 1, 2, \dots\). In particular, if the vectors have rational coordinates, the algorithm will eventually cycle.

$$ f^{-1}(U) $$

Tak til Christian (Ottosen) for denne rettelse.

$$ n $$

Consider \(f: \mathbb{R}\rightarrow \mathbb{R}\) given by

$$ f(x) = x^2. $$

Is \(f\) injective? Surjective? Can you adjust the domain and the codomain so that \(f\) becomes bijective?

You may also view the table form as in the abstract definition of a function

$$ f = {(1, \sqrt{2}), (2, \pi), (3, -1)} \subseteq {1, 2, 3}\times \mathbb{R}. $$

Here \(p\) is the logical exclusive or (XOR) function. It is usually denoted

$$ p(x, y) = x \oplus y. $$

Later it will become important that function composition is associative i.e.,

$$ f\circ( g\circ h) = (f \circ g) \circ h $$

whenever these compositions are well defined.

Try to do binary search in a natural way in the tree for recovering the classical approximation \(22/7\) for \(\pi\). Here you actually need to descend to more than depth \(10\) in the tree!

The famous approximation \(355/113\) is above depth \(25\).

satisfied

Please do check out The Natural Number Game at

https://www.ma.imperial.ac.uk/~buzzard/xena/natural_number_game/index2.html

Here you can see LEAN in action with every step of a proof spelled out!

Her skal der stå \(q_3\).

Begin by putting

$$ \texttt{left} = \frac{0}{1}\quad\texttt{mediant} = \frac{1}{1}\quad\texttt{right}=\frac{1}{0}. $$

If you move left, keep \(\texttt{left}\), put \(\texttt{right}\) equal to \(\texttt{mediant}\) and compute new \(\texttt{mediant}\). If you move right keep the \(\texttt{right}\) etc.

Suppose \(x \neq 0\). Why is \(x^2 > 0\)?

Here the everyday negative number \(-0.8\) is represented as

$$ -1.20000\dots $$

We could also have used a signed model, where \(\sigma = \pm 1\) was added to the representation. This would make the model agree with everyday notation.

You can deduce this formula for addition by using the identity

$$ b d \left(\frac{a}{b} + \frac{c}{d}\right) = a d + b c. $$

For this formula for addition to make sense, we should have

$$ \frac{1}{2} + \frac{2}{3} = \frac{3}{5} \quad\ = \quad \frac{2}{4} + \frac{2}{3} = \frac{4}{7}. $$

by replacing \(\frac{1}{2}\) by \(\frac{2}{4}\). According to Definition 1.8 it is not true that \(\frac{3}{5} = \frac{4}{7}\).

Perhaps clearer: $$ v\not\in V(J_r) \iff r \text{ is defined at } v $$

open

A very interesting operation is negative and or NAND. Let us define \(p\cdot q = \neg (p\land q)\). Prove that

$$ p\lor q = (p\cdot q)\cdot (q\cdot q). $$

In fact, all of our operators \(\land, \lor, \implies, \neg\) can be implemented using NAND.

En god anvendelse her er i tilfældet, hvor bibetingelserne i \(C\) er lineære. Så kan man teste om \(v_0\) er en optimal løsning ved at løse det lineære optimeringsproblem.

$$ \min \nabla f(v_0) v $$

for \(v\in C\). Hvis den optimale værdi er \(\geq \nabla f(v_0) v_0\), så er \(v_0\) en optimal løsning.

Implicit definition af et konvekst optimeringsproblem.

A critical point

Et saddelpunkt antages at være kritisk til at begynde med. Eksemplet

$$ f(x, y, z) = x^2 - y^2 + z $$

har \( (0,0,0)\) som saddelpunkt i henhold til definitionen. Dette punkt er ikke kritisk!

Præcise kriterier for hvorrnår en diagonalmatrix er indefinit bør nævnes.

With more than 2 edges!

\(\mathbb{R}\)

Skal være \(u\)

Sød lille opgave: Vis at \(S^o\) er åben.

Mangler transponering

More precisely \(q\equiv f\). Typically \(q = r \land \neg r\) for some proposition \(r\).

Lidt sjov i gaden. Under forelæsningen spurgte jeg ChatGPT om en formel for summen

$$ 1^3 + 2^3 + \cdots + n^3 $$

hvortil den svarede

$$ \left(\cfrac{n (n+1)}{2}\right)^2 $$

Her virker induktion på samme måde og den distributive lov bruges ved at sætte \((n+1)^2\) udenfor en parentes.

Her mangler \(C=\)

Notice also that \(\mathbb{Z}^2\) (and \(\mathbb{R}^2\) ) is not defined at this point. See below (section 1.6.6).

As pointed out by a careful listener during the lecture, this is important. If backtracking to only \(p_2\) we cannot pinpoint that \(p_1\) is false.

ChatGPT is quite useful here:

Notice that \(\implies\) in the chain of arguments implies that a solution is unique!

In a sense you are solving linear equations here by coming up with the clever Lagrange polynomials.

Well the new OpenAI model o1 does:

ChatGPT, o1 magic

Here is another example:

ChatGPT example

Thanks for asking for yet another example during the lecture.

\(\geq\) not defined here

Here \(x_1\land (x_2\lor x_3)\) displays as a right answer, but it is wrong.

Empty set not defined here.

Hmmm. It seems that

$$ \frac{\lambda}{g} \equiv \frac{\lambda}{g(3)} \pmod{x-3}, $$

where \(\lambda\in \mathbb{C}\).

In general $$ f\in \sqrt{J} \iff J + (1 - t f) = K[x_1, \dots, x_n, t]. $$

\(\implies\) is proved using the familiar identity $$ \frac{1-a^n}{1-a} = 1 + a + a^2 + \cdots + a^{n-1}. $$

NEJ! Annoteringer skal ikke laves i Public gruppen. De skal laves i IMO23 gruppen!

Nope. The world record is rank >= 28.

Why is this?

Closure of a subset \(Y\subset X\) is denoted \(\overline{Y}\). It is the intersection of the closed subsets containing \(Y\). If

$$ X = U_1 \cup \cdots \cup U_n $$

is an open cover, then

$$ \overline{Y} = \overline{Y\cap U_1} \cup \cdots \cup \overline{Y\cap U_n}, $$

where \(\overline{Y\cap U_i}\subseteq U_i\) denotes closure in the induced topology.

Consider \(X = [0, 1]\) and \(\sim\) with \(0\sim 1\) and \(x\sim x\) for \(x\in X\). Show that $$ \pi([0, \frac{1}{2})) \subset X/\sim $$ is not an open subset.

t

Er det nu rigtigt? At \(G\rightarrow G/H\) er åben?

Extra. Show that a positive definite matrix \(A\) is invertible and that \(A^{-1}\) is positive definite.

Corollary tag missing.

Here we may also use Corollary 7.14 (in the textbook) for \(f(x) = x^3\) on \((-\infty, 0)\) and \((0, \infty)\) and then handle the separate cases by hand.

Use the trick $$ f = \left(\frac{f}{g}\right) g $$ and then apply the product rule.

Also, check this using the Sage window after Example 7.7 by doing the appropriate modifications.

Se

https://en.wikipedia.org/wiki/Basel_problem

Exercise 5.31 kan være nyttig her (specielt første del med infimum).

Definitionen af infimum siger i dette tilfælde at der for alle \(\epsilon >0\) findes \(x_n\) med $$ x_n < \text{inf} + \epsilon \iff x_n - \text{inf} < \epsilon. $$

Indrømmet. Denne defintion er pebret og kræver tilvænning. En god første ide er helt præcist at benytte definitionen til i detaljer at vise $$ \lim_{n\to\infty} \frac{1}{n} = 0. $$

sequence not series

Faktisk gælder dette også for uendeligt mange lukkede mængder. Det interessant i denne forbindelse er at foreningsmængden

$$ F_1\cup F_2\cup \cdots \cup F_n $$

er lukket.

Et eksempel: For \(f(x) = x^2\) er

$$ f^{-1}([0,1]) = [-1, 1]. $$

Læg mærke til den helt naturlige algoritme for at finde nulpunktet \(x_0\): Først sættes

$$ c = \dfrac{a+b}{2} $$

Hvis \(f(c)=0\) er vi færdige. Hvis \(f(c) < 0\) rykker vi venstre endepunkt og sætter \(a = c\) og fortsætter med gennemsnittet ovenfor.

Hvis \(f(c) > 0\) rykker vi højre endepunkt og sætter \(b = c\) og fortsætter med gennemsnittet ovenfor.

Denne algoritme kaldes bisektionsmetoden, da den hver gang halverer længden af intervallet \([a, b]\).

I forelæsningerne viste vi også $$ |\lambda v| = |\lambda| |v|. $$

I forelæsningen så vi hvordan identiteten

$$ \sqrt{2} = 1 + \sqrt{2} - 1 $$

ledte frem til identiteten

$$ \sqrt{2} = 1 + \dfrac{1}{1 + \sqrt{2}} $$

som så førte til en konvergent følge af brøker med grænseværdi \(\sqrt{2}\):

$$ 1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12},\dots $$

I forelæsningen talte vi om uendelige decimaltal (decimalbrøker) som model for de reelle tal. Her skal man passe lidt på, da f.eks.

$$ 0.99999\dots = 1 $$

Do this also for

any

Lille ekstra opgave: Lad \(A\) og \(B\) være to \(n\times n\) matricer, hvor \(A\) antages at være invertibel. Vis at \(B\) er invertibel hvis og kun hvis \(A B\) er invertibel.

Til forelæsningerne berørte vi hvornår en diagonalmatrix var invertibel. Kan du huske hvad betingelsen var her?

Lader ikke til at matricer vises korrekt i LaTeX i annotationerne (tak til Andreas for denne observation). Eksempel:\begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} vises som $$ \begin{pmatrix} 1 & 0\ 0 & 1 \end{pmatrix}. $$

Under forelæsningerne så vi at numpy gik i skoven i eksemplet med 3x3 matricen [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Denne matrix er ikke invertibel, men numpy returnerer en invers matrix pga afrundingsfejl.

Læg mærke til at dette også kan bruges til at afgøre om en matrix ikke er invertibel: Hvis \(A\) er invertibel og \(A v = 0\) så medfører det at \(v=0\). En invertibel matrix kan ikke sende en vektor forskellig fra \(0\) til \(0\).

Overvej at benytte logaritmen med grundtal \(2\) og uligheden

$$ 2^n n < n! $$

for \(n>5\).

Der er her tale om et bevis med ord og forklaringer uden brug af implikationspile som \(\implies\) og \(\iff\). Du er velkommen til i din opgaveløsning at bruge pilene, som er defineret længere nede i teksten.

Se også

https://www.nytimes.com/2019/08/21/science/math-equation-triangles-pemdas.html

Vel ikke alt for moderne? Her en formel: $$ \int_{-\infty}^\infty e^{-x^2} d x = \sqrt{\pi} $$

Uddyb determinanten!

Hvad er proof of work?

Hvad betyder dette?

What du you mean? Is it not cleat that \(x^2+y^2 = z^2\). Or in display $$ x^3 + y^3 = z^3 $$

Tilføjelse per 27/11.

Skulle denne video have været længere og indeholdt feks Lagrangeinterpolation?

Er det ikke for kompliceret?

Her betaler det sig måske at tegne den retvinklede trekant med hypotenuselængde 1.

Er det ikke lidt af en overdrivelse. Her mangler en kildeangivelse!