-
-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathcontent.html
More file actions
1505 lines (1484 loc) · 64.2 KB
/
Copy pathcontent.html
File metadata and controls
1505 lines (1484 loc) · 64.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-GB" xml:lang="en-GB">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta
name="viewport"
content="width=device-width, initial-scale=1.0, user-scalable=yes"
/>
<meta name="author" content="Gabriel Nützi" />
<meta name="author" content="The Community" />
<title>Technical Documents</title>
<style>
code {
white-space: pre-wrap;
}
span.smallcaps {
font-variant: small-caps;
}
div.columns {
display: flex;
gap: min(4vw, 1.5em);
}
div.column {
flex: auto;
overflow-x: auto;
}
div.hanging-indent {
margin-left: 1.5em;
text-indent: -1.5em;
}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class] {
list-style: none;
}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
/* CSS for syntax highlighting */
html {
-webkit-text-size-adjust: 100%;
}
pre > code.sourceCode {
white-space: pre;
position: relative;
}
pre > code.sourceCode > span {
display: inline-block;
line-height: 1.25;
}
pre > code.sourceCode > span:empty {
height: 1.2em;
}
.sourceCode {
overflow: visible;
}
code.sourceCode > span {
color: inherit;
text-decoration: inherit;
}
div.sourceCode {
margin: 1em 0;
}
pre.sourceCode {
margin: 0;
}
@media screen {
div.sourceCode {
overflow: auto;
}
}
@media print {
pre > code.sourceCode {
white-space: pre-wrap;
}
pre > code.sourceCode > span {
text-indent: -5em;
padding-left: 5em;
}
}
pre.numberSource code {
counter-reset: source-line 0;
}
pre.numberSource code > span {
position: relative;
left: -4em;
counter-increment: source-line;
}
pre.numberSource code > span > a:first-child::before {
content: counter(source-line);
position: relative;
left: -1em;
text-align: right;
vertical-align: baseline;
border: none;
display: inline-block;
-webkit-touch-callout: none;
-webkit-user-select: none;
-khtml-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
padding: 0 4px;
width: 4em;
color: #aaaaaa;
}
pre.numberSource {
margin-left: 3em;
border-left: 1px solid #aaaaaa;
padding-left: 4px;
}
div.sourceCode {
background-color: #f8f8f8;
}
@media screen {
pre > code.sourceCode > span > a:first-child::before {
text-decoration: underline;
}
}
code span.al {
color: #ef2929;
} /* Alert */
code span.an {
color: #8f5902;
font-weight: bold;
font-style: italic;
} /* Annotation */
code span.at {
color: #204a87;
} /* Attribute */
code span.bn {
color: #0000cf;
} /* BaseN */
code span.cf {
color: #204a87;
font-weight: bold;
} /* ControlFlow */
code span.ch {
color: #4e9a06;
} /* Char */
code span.cn {
color: #8f5902;
} /* Constant */
code span.co {
color: #8f5902;
font-style: italic;
} /* Comment */
code span.cv {
color: #8f5902;
font-weight: bold;
font-style: italic;
} /* CommentVar */
code span.do {
color: #8f5902;
font-weight: bold;
font-style: italic;
} /* Documentation */
code span.dt {
color: #204a87;
} /* DataType */
code span.dv {
color: #0000cf;
} /* DecVal */
code span.er {
color: #a40000;
font-weight: bold;
} /* Error */
code span.ex {
} /* Extension */
code span.fl {
color: #0000cf;
} /* Float */
code span.fu {
color: #204a87;
font-weight: bold;
} /* Function */
code span.im {
} /* Import */
code span.in {
color: #8f5902;
font-weight: bold;
font-style: italic;
} /* Information */
code span.kw {
color: #204a87;
font-weight: bold;
} /* Keyword */
code span.op {
color: #ce5c00;
font-weight: bold;
} /* Operator */
code span.ot {
color: #8f5902;
} /* Other */
code span.pp {
color: #8f5902;
font-style: italic;
} /* Preprocessor */
code span.sc {
color: #ce5c00;
font-weight: bold;
} /* SpecialChar */
code span.ss {
color: #4e9a06;
} /* SpecialString */
code span.st {
color: #4e9a06;
} /* String */
code span.va {
color: #000000;
} /* Variable */
code span.vs {
color: #4e9a06;
} /* VerbatimString */
code span.wa {
color: #8f5902;
font-weight: bold;
font-style: italic;
} /* Warning */
/* CSS for citations */
div.csl-bib-body {
}
div.csl-entry {
clear: both;
margin-bottom: 0em;
}
.hanging-indent div.csl-entry {
margin-left: 2em;
text-indent: -2em;
}
div.csl-left-margin {
min-width: 2em;
float: left;
}
div.csl-right-inline {
margin-left: 2em;
padding-left: 1em;
}
div.csl-indent {
margin-left: 2em;
}
</style>
<link rel="stylesheet" href="css/main.css" />
<script type="text/javascript">
window.MathJax = {
tex: {
processEnvironments: false,
processEscapes: true,
/* Escape dollar because it's a pandoc template */
inlineMath: [
["\\(", "\\)"],
["$", "$"],
],
displayMath: [
["\\[", "\\]"],
["$$", "$$"],
],
tags: "ams",
packages: {
"[+]": ["extpfeil", "color", "boldsymbol", "newcommand"],
},
},
options: {
ignoreHtmlClass: "tex2jax_ignore",
processHtmlClass: "tex2jax_process",
},
loader: {
load: [
"[tex]/extpfeil",
"[tex]/color",
"[tex]/boldsymbol",
"[tex]/newcommand",
],
},
}
</script>
<script
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"
type="text/javascript"
></script>
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
<script>
// If we have a hash we disable history scrolling restoration and
// really scroll into view.
var c = window.location.hash
if (c.length != 0) {
history.scrollRestoration = "manual"
}
document.addEventListener("DOMContentLoaded", function (event) {
var c = window.location.hash
var e = document.getElementById(c.replace("#", ""))
if (e != null) {
e.scrollIntoView()
}
})
</script>
<script src="https://cdn.jsdelivr.net/npm/anchor-js/anchor.min.js"></script>
<script>
document.addEventListener("DOMContentLoaded", function (event) {
var P = "#main-markdown > header"
var noAnchorHeaders = document.querySelectorAll(
`${P} h1, ${P} h2, ${P} h3, ${P} h4, ${P} h5, ${P} h6`,
)
for (var k = 0; k < noAnchorHeaders.length; k++) {
noAnchorHeaders[k].classList.add("no-anchor")
}
anchors.options = {
placement: "right",
visible: "never",
icon: "§",
}
var P = "#main-markdown"
anchors.add(
`${P} h1:not(.no-anchor),${P} h2:not(.no-anchor),${P} h3:not(.no-anchor),${P} h4:not(.no-anchor),${P} h5:not(.no-anchor),${P} h6:not(.no-anchor)`,
)
})
</script>
<script>
function openSideNav() {
expandWidth = 300
var sidnav = document.getElementById("sidenav")
var m = document.getElementById("main-markdown")
sidnav.style.width = `${expandWidth}px`
if (m.offsetLeft - expandWidth < 0) {
m.style.marginLeft = `${expandWidth + 40}px`
}
document.getElementById("nav-content").style.display = "none"
toc = document.getElementById("TOC")
// Append to sidebar.
toc.parentNode.removeChild(toc)
document.getElementById("sidenav-content").append(toc)
}
function closeSideNav() {
document.getElementById("sidenav").style.width = "0"
document.getElementById("main-markdown").style.marginLeft = null
navContent = document.getElementById("nav-content")
navContent.style.display = "initial"
toc = document.getElementById("TOC")
// Append to inline.
toc.parentNode.removeChild(toc)
document.getElementById("nav-content").append(toc)
}
var EXPAND_ALL = "⊞"
var COLLAPSE_ALL = "⊟"
var toggleExpandCollapse = function () {
var botton = document.getElementById("expand")
if (botton.innerHTML === EXPAND_ALL) {
expandAll()
botton.innerHTML = COLLAPSE_ALL
} else {
collapseAll()
botton.innerHTML = EXPAND_ALL
}
}
var expandAll = function () {
var allListItems = document.querySelectorAll("nav ul li")
for (var k = 0; k < allListItems.length; k++) {
allListItems[k].classList.add("open")
}
}
var collapseAll = function () {
var allListItems = document.querySelectorAll("nav ul li")
for (var k = 0; k < allListItems.length; k++) {
allListItems[k].classList.remove("open")
}
}
var onLoad = function () {
var treeListItems = document.querySelectorAll("nav ul li")
for (var i = 0; i < treeListItems.length; i++) {
var isLeaf = treeListItems[i].getElementsByTagName("ul").length == 0
if (isLeaf) {
treeListItems[i].classList.add("leaf")
continue
}
// click handler
treeListItems[i].addEventListener("click", function (e) {
var target = e.target
var classList = target.classList
if (classList.contains("open")) {
// close the element and its children
classList.remove("open")
var openChildrenList = target.querySelectorAll(":scope li.open")
for (var j = 0; j < openChildrenList.length; j++) {
openChildrenList[j].classList.remove("open")
}
} else {
// open the element
classList.add("open")
}
e.stopPropagation()
})
}
}
window.addEventListener("load", onLoad)
</script>
</head>
<body id="main">
<!--
This is the sidebar stuff.
-->
<a
id="sidenav-btn"
class="button"
href="javascript:void(0)"
onclick="openSideNav()"
>
<svg
xmlns="http://www.w3.org/2000/svg"
width="18"
height="12"
viewBox="0 0 18 12"
>
<path fill="currentColor" d="M0 0h18v2H0zM0 5h18v2H0zM0 10h18v2H0z" />
</svg>
</a>
<div id="sidenav" class="sidenav">
<div id="nav-menu">
<a
class="expand-btn"
id="expand"
href="javascript:void(0)"
onClick="toggleExpandCollapse()"
style="baseline-shift: -10%"
>⊞</a
>
<a class="close-btn" href="javascript:void(0)" onclick="closeSideNav()"
>×</a
>
</div>
<div id="sidenav-content"></div>
</div>
<div id="main-markdown">
<header>
<div class="title-block">
<h1 class="title">Technical Documents</h1>
<h3 class="subtitle">
Demonstrating the Power of Markdown with Pandoc (v3)
</h3>
<p class="author">
<strong>Authors: </strong>Gabriel Nützi, The Community
</p>
<p class="date"><strong>Date: </strong>10. July 2026</p>
<p class="location"><strong>Location: </strong>Zürich, Switzerland</p>
</div>
<div class="title-logo">
<img src="files/logo.svg" />
</div>
</header>
<div class="abstract">
<div class="abstract-title">Abstract</div>
<p>
This is a setup demonstrating the power and use of markdown for
technical documents by using a fully automated conversion sequence
with <a href="https://gradle.org"><code>gradle</code></a> and of
course <a href="https://pandoc.org"><code>pandoc</code></a
>.”
</p>
</div>
<div class="acknowledgement">
<div class="acknowledgement-title">Thanks</div>
<p>Acknowledgements go to the authors of this setup.</p>
</div>
<div id="nav-content">
<h2 id="toc-title">Contents</h2>
<nav id="TOC">
<ul>
<li>
<a href="#intro" id="toc-intro"
><span class="toc-section-number">1</span> Intro</a
>
</li>
<li>
<a href="#samples" id="toc-samples"
><span class="toc-section-number">2</span> Samples</a
>
<ul>
<li>
<a href="#konvexe-probleme" id="toc-konvexe-probleme"
><span class="toc-section-number">2.1</span> Konvexe
Probleme</a
>
<ul>
<li>
<a href="#konvexe-menge" id="toc-konvexe-menge"
><span class="toc-section-number">2.1.1</span> Konvexe
Menge</a
>
</li>
<li>
<a href="#proximaler-punkt" id="toc-proximaler-punkt"
><span class="toc-section-number">2.1.2</span>
Proximaler Punkt</a
>
</li>
<li>
<a href="#normalkegel" id="toc-normalkegel"
><span class="toc-section-number">2.1.3</span>
Normalkegel</a
>
</li>
<li>
<a
href="#zusammenhang-von-normalkegel-und-proximaler-punkt"
id="toc-zusammenhang-von-normalkegel-und-proximaler-punkt"
><span class="toc-section-number">2.1.4</span>
Zusammenhang von Normalkegel und Proximaler Punkt</a
>
</li>
<li>
<a
href="#zusammenhang-von-normalkegel-und-konvexer-optimierung"
id="toc-zusammenhang-von-normalkegel-und-konvexer-optimierung"
><span class="toc-section-number">2.1.5</span>
Zusammenhang von Normalkegel und Konvexer Optimierung</a
>
</li>
</ul>
</li>
<li>
<a href="#code-sample" id="toc-code-sample"
><span class="toc-section-number">2.2</span> Code Sample</a
>
</li>
<li>
<a href="#pdf-include-sample" id="toc-pdf-include-sample"
><span class="toc-section-number">2.3</span> PDF Include
Sample</a
>
</li>
<li>
<a href="#questionnaire-sample" id="toc-questionnaire-sample"
><span class="toc-section-number">2.4</span> Questionnaire
Sample</a
>
</li>
<li>
<a href="#tables" id="toc-tables"
><span class="toc-section-number">2.5</span> Tables</a
>
<ul>
<li>
<a href="#html-table" id="toc-html-table"
><span class="toc-section-number">2.5.1</span> HTML
Table</a
>
</li>
<li>
<a href="#sec:tables" id="toc-sec:tables"
><span class="toc-section-number">2.5.2</span> Markdown
Tables</a
>
</li>
</ul>
</li>
</ul>
</li>
<li><a href="#references" id="toc-references">References</a></li>
</ul>
</nav>
</div>
<div class="latex-math-define">
$$ \newcommand{\vvec}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}}
\newcommand{\cs}[1]{\mathrm{#1}} \newcommand{\rp}[1]{{_\cs{#1}}}
\newcommand{\csT}[2]{\mat{A}_{\mathrm{#1#2}}}
\newcommand{\genT}[2]{\mat{T}_{\mathrm{#1#2}}}
\newcommand{\affcsT}[2]{\mat{H}_{\mathrm{#1#2}}}
\newcommand{\affcsTdx}[2]{\mat{H}_{\mathrm{#1#2}}^{\transp}}
\newcommand{\basevec}[2]{\vvec{e}_{\mathrm{#1}}^{\cs{#2}}}
\newcommand{\homArr}[1]{\left[\begin{array}{c}#1 \\ 1
\end{array}\right]} \newcommand{\homArrTr}[1]{\left[\begin{array}{c}#1
&& 1 \end{array}\right]}
\newcommand{\homMat}[2]{\left[\begin{array}{cc}#1 & #2 \\ \vvec{0}
& 1 \end{array}\right]}
\newcommand{\arr}[2]{\left[\begin{array}{#1}#2\end{array}\right]}
\newcommand{\transp}{\top} \newcommand{\rot}[2]{\mat{R}_\mathrm{#1#2}}
\newcommand{\norm}[1]{\|#1\|} \newcommand{\mdet}[1]{\det(#1)}
\newcommand{\set}[1]{\mathcal{#1}}
\newcommand{\prox}[1]{\mathbf{prox}_{\set{C}}}
\DeclareMathOperator*{\argmin}{argmin}
\newcommand{\ncone}[1]{\mathcal{N}_{\set{#1}}}
\newcommand{\indf}[1]{I_{\set{#1}}} $$
</div>
<h1 data-number="1" id="intro">
<span class="header-section-number">1</span> Intro
</h1>
<p>
Read the
<a
href="https://github.com/gabyx/technical-markdown/blob/master/Readme.md"
>Readme.md</a
>
for further information.
</p>
<h1 data-number="2" id="samples">
<span class="header-section-number">2</span> Samples
</h1>
<h2 data-number="2.1" id="konvexe-probleme">
<span class="header-section-number">2.1</span> Konvexe Probleme
</h2>
<p>
In diesem Abschnitt geht es darum ein besseres Verständnis zu geben über
Algorithmen und Konzepte welche zum Beispiel bei der
<span class="math inline">\(2\)</span>d-/<span class="math inline"
>\(3\)</span
>d-Kollisionsdetektion oder in Optimierungs-Algorithmen genutzt werden.
Die Erklärungen sind eine stärkere und vereinfachte Zusammenfassung aus
<span class="citation" data-cites="nuetzig_thesis_2016"
><a href="#ref-nuetzig_thesis_2016" role="doc-biblioref"
>[1, Ch. 6]</a
></span
>. Dieses Kapitel möchte nicht mathematisch abschliessend sein, sondern
lediglich (nach der Ansicht des Autors) ein paar wichtige Grundkonzepte
vermitteln, welche einen wunderbaren Einstieg in dieses Thema geben. Die
erwähnten Konzepte sind in der generellsten Form der konvexen Analysis
zu finden und können sehr wohl als die wichtigsten Standbeine
verinnerlicht werden. Auf Beweise wird bewusst verzichtet. Es wird
versucht die mathematischen Definitionen anschaulich zu erklären.
</p>
<p>
Das Vorhandensein eines <em>konvexen</em> Optimierungsproblems oder auch
einer <em>konvexen Menge</em> beim Lösen eines Problems in
<span class="math inline">\(3\)</span>D, oder auch mehr Dimensionen,
erlaubt es, auf eine Fülle von mathematisch sehr etablierten
Definitionen und Konzepte aus der
<em>konvexen Analysis</em> zurückzugreifen. Diese schon fast 50-jährige
Theorie ist sehr fundiert und ein abgeschlossenes Untergebiet in der
Mathematik.
</p>
<p>
Die <em>konvexe Analysis</em> ist ein Grenzgebiet von
<em>Geometrie</em>, <em>Analysis</em> und <em>Funktionalanalysis</em>,
das sich mit den Eigenschaften <strong>konvexer Mengen</strong> und
<strong>konvexer Funktionen</strong> befaßt und Anwendungen sowohl in
der reinen Mathematik besitzt (von Existenzsätzen in der Theorie der
Differential- und Integralgleichungen bis zum Gitterpunktsatz von
Minkowski in der Zahlentheorie) als auch in Bereichen wie der
mathematischen Ökonomie und den Ingenieurswissenschaften, wo man es oft
mit Optimierungs- und Gleichgewichtsproblemen zu tun hat. Als
einschlägige Referenz auf diesem Gebiet sei hier mal das Standardwerk
<span class="citation" data-cites="rockafellar_convex_2015"
><a href="#ref-rockafellar_convex_2015" role="doc-biblioref"
>[2]</a
></span
>
gegeben.
</p>
<h3 data-number="2.1.1" id="konvexe-menge">
<span class="header-section-number">2.1.1</span> Konvexe Menge
</h3>
<p>
Eine Menge <span class="math inline">\(\set{C} \subseteq V\)</span>,
also eine Teilmenge eines Vektorraums
<span class="math inline">\(V\)</span>, wird
<strong>konvex</strong> genannt, falls und nur falls
</p>
<p>
<span class="math display"
>\[\begin{align} \lambda \vvec{a} + (1-\lambda) \vvec{b} \in \set{C}
\quad \forall \vvec{a},\vvec{b} \in \set{C}, \ \lambda \in [0,1] \ .
\end{align}\]</span
>
gilt.
</p>
<p>
Das heisst alle Punkte auf einer geraden Linie zwischen zwei beliebigen
Punkten aus der Menge
<span class="math inline">\(\set{C}\)</span> müssen
<strong>auch</strong> in dieser Menge liegen damit es
<strong>konvex</strong> ist. Stellt man sich eine Banane vor oder eine
Oberfläche eines <span class="math inline">\(3\)</span>d-Würfels, dann
erfüllen diese Mengen das Kriterium nicht. Ein ausgefülltes
<span class="math inline">\(2\)</span>d-Rechteck , ein gefüllter
<span class="math inline">\(3\)</span>d-Würfel oder eine gefüllte Kugel
jedoch schon. Eine <strong>konvexe</strong> Menge ist eine Teilmenge
eines Vektorraums. Ein Beispiel ist der euklidische Raum
<span class="math inline">\(\mathbb{E}^3\)</span> in
<span class="math inline">\(3\)</span>D.
</p>
<p>
Man interessiert sich nun zum Beispiel für die Projektion eines Punktes
<span class="math inline">\(\vvec{x}\)</span> auf ein konvexe Menge
<span class="math inline">\(\set{C}\)</span>. Die Projektion sollte so
sein, dass der Abstand zwischen dem Punkt
<span class="math inline">\(\vvec{x}\)</span> und dem projezierten Punkt
<span class="math inline">\(\vvec{y} \in \set{C}\)</span>
<strong>minimal</strong> ist.
</p>
<p>
Der Abstand wird über eine Metrik
<span class="math inline">\(d(\vvec{x},\vvec{y}) \geq 0\)</span>
definiert - die <em>Distanzfunktion</em>. Der euklidische Vektorraum
<span class="math inline">\(\mathbb{E}^3\)</span> ist ein Vektorraum mit
einer Metrik und ist daher ein <em>metrischer Raum</em>. Das
Standard-Skalarprodukt
<span class="math inline">\(\vvec{x}^\transp \vvec{y}\)</span> im
euklidischen Raum
<span class="math inline">\(\mathbb{E}^3\)</span> induziert direkt die
Standardnorm
<span class="math inline"
>\(\norm{\vvec{x}}_2 := \sqrt{\vvec{x}^\transp \vvec{x}} \geq
0\)</span
>. Diese wiederum induziert direkt die Metrik
<span class="math display"
>\[\begin{align} d(\vvec{x},\vvec{y}) := \norm{\vvec{x} - \vvec{y}}_2.
\end{align}\]</span
>
</p>
<p>
Wir können somit über die Metrik
<span class="math inline">\(d(\vvec{x},\vvec{y})\)</span> die Länge
zwischen zwei Vektoren
<span class="math inline">\(\vvec{x},\vvec{y} \in \mathbb{E}^3\)</span>
berechnen.
</p>
<h3 data-number="2.1.2" id="proximaler-punkt">
<span class="header-section-number">2.1.2</span> Proximaler Punkt
</h3>
<p>
Mit der Metrik, also unserem Lineal zum Messen von Distanzen, lässt sich
nun die Projektion
<span class="math inline">\(\prox{C}(\vvec{p})\)</span> eines Punktes
<span class="math inline">\(\vvec{p}\)</span> mit minimaler Distanz auf
eine konvexe Menge <span class="math inline">\(\set{C}\)</span> relativ
leicht definieren zu
<span class="math display"
>\[\begin{align} \prox{C}(\vvec{p}) := \underset{\vvec{x} \ \in \
\set{C}}{\argmin} \norm{\vvec{x} - \vvec{p}}_2. \end{align}\]</span
>
</p>
<p>
Das heisst
<span class="math inline">\(\prox{C}(\vvec{p})\)</span> minimiert den
Punkt <span class="math inline">\(\vvec{x}\)</span> in der Menge
<span class="math inline">\(\set{C}\)</span> so, dass sein Abstand zu
<span class="math inline">\(\vvec{p}\)</span> minimal ist.
</p>
<h3 data-number="2.1.3" id="normalkegel">
<span class="header-section-number">2.1.3</span> Normalkegel
</h3>
<p>
Eines der <strong>wichtigsten</strong> Konzepte der konvexen Analysis
ist die des <strong>Normalkegels</strong>. Wie der Name schon sagt,
handelt es sich um einen Kegel welcher durch Normalenvektoren auf der
Oberfläche einer konvexen Menge aufgespannt wird. Wir geben hier direkt
die Definition und sehen im Anschluss wie sich dieser Kegel
visualisiert:
</p>
<p>
Ein Normalkegel <span class="math inline">\(\ncone{C}\)</span> auf ein
konvexes Set <span class="math inline">\(\set{C}\)</span> im Punkt
<span class="math inline">\(\vvec{x} \in \set{C}\)</span> ist definiert
als
<span class="math display"
>\[\begin{align} \ncone{C}(\vvec{x}) := \left\{ \vvec{y} \ | \
\vvec{y}^\transp(\vvec{x}^* - \vvec{x}) \leq 0, \quad \forall
\vvec{x}^* \in \set{C} \right\} \end{align}\]</span
>
</p>
<p>
Das ist nun ein wenig kryptisch, heisst jedoch nichts anderes als
folgendes: Der Normalkegel
<span class="math inline">\(\ncone{C}(\vvec{x})\)</span> besteht aus
allen Vektoren (das wäre <span class="math inline">\(\vvec{y}\)</span>)
ausgehend von <span class="math inline">\(\vvec{x}\)</span> welche mit
<strong>allen</strong> Vektoren welche vom Punkt
<span class="math inline">\(\vvec{x}\)</span> in die Menge
<span class="math inline">\(\set{C}\)</span> zeigen (das wäre
<span class="math inline">\(\vvec{x}^* - \vvec{x}\)</span>), einen
<strong>stumpfen</strong> Winkel bilden (das wäre das Skalarprodukt mit
<span class="math inline">\(\leq 0\)</span>). Der Ursprung der Menge
<span class="math inline">\(\ncone{C}(\vvec{x})\)</span> ist im Punkt
<span class="math inline">\(\vvec{x}\)</span>.
</p>
<p>
Die Abbildung <a href="#fig:normalcone">1</a> visualisiert für eine
konvexe Menge <span class="math inline">\(\set{C}\)</span> die
verschiedenen Normalkegel.
</p>
<figure id="fig:normalcone">
<img
src="files/normal-cone.svg"
style="width: 100%; max-width: 7cm"
alt="Figure 1: Normalkegel an die Punkte \vvec{x}, \vvec{y} und \vvec{z}. Der Normalkegel an einen innerhalb der Menge \set{C} liegenden Punkt \vvec{z} degeneriert zum \vvec{0}-Vektor. Der Vektor \vvec{v} ist in der Menge des Normalkegels an \vvec{x}."
/>
<figcaption aria-hidden="true">
Figure 1: Normalkegel an die Punkte
<span class="math inline">\(\vvec{x}\)</span>,
<span class="math inline">\(\vvec{y}\)</span> und
<span class="math inline">\(\vvec{z}\)</span>. Der Normalkegel an
einen innerhalb der Menge
<span class="math inline">\(\set{C}\)</span> liegenden Punkt
<span class="math inline">\(\vvec{z}\)</span> degeneriert zum
<span class="math inline">\(\vvec{0}\)</span>-Vektor. Der Vektor
<span class="math inline">\(\vvec{v}\)</span> ist in der Menge des
Normalkegels an <span class="math inline">\(\vvec{x}\)</span>.
</figcaption>
</figure>
<h3
data-number="2.1.4"
id="zusammenhang-von-normalkegel-und-proximaler-punkt"
>
<span class="header-section-number">2.1.4</span> Zusammenhang von
Normalkegel und Proximaler Punkt
</h3>
<p>
Man fragt sich natürlich nun:
<em>Was bringen uns diese mathematische Definitionen?</em>
</p>
<p>
Es stellt sich heraus, dass es einen Zusammenhang gibt zwischen
<span class="math inline">\(\prox{C}\)</span> und
<span class="math inline">\(\ncone{C}\)</span> welcher extremst nützlich
ist und heute im Feld der konvexen Optimierung, beim Machine-Learning,
in der Starrkörper-Mechanik (Starrkörper-Simulationen und
Physics-Engines in Games) oder auch in der Kollisionsdetektion (GJK
Algorithmus) durch projektive Iterationen direkte Anwendung findet.
</p>
<p>
Der Zusammenhang ist wie folgt:
<span class="math display"
>\[\begin{align} \vvec{y} \in \ncone{C}(\vvec{x}) \quad
\Leftrightarrow \quad \vvec{x} = \prox{C}(\vvec{x} + \vvec{y})
\label{eq:prox-to-ncone} \end{align}\]</span
>
</p>
<p>
Das heisst, eine Normalkegel-<em>Inklusion</em> (die Relation
<span class="math inline">\(\vvec{a} \in \set{B}\)</span> wird
<em>Mengen-Inklusion</em> genannt) ist direkt an eine
<strong>implizite</strong> <em>projektive</em> Gleichung gekoppelt.
</p>
<p>
Damit lässt sich nun ein interessanter wichtiger Fakt ableiten. Aus der
Visualisierung <a href="#fig:normalcone">1</a> entnehmen wir, dass
<span class="math inline">\(\vvec{p}-\vvec{x}\)</span> in der Menge
<span class="math inline">\(\ncone{C}(\vvec{x})\)</span> liegt, also
lässt sich schreiben
<span class="math display"
>\[\begin{align} \vvec{p}-\vvec{x} \in \ncone{C}(\vvec{x}).
\end{align}\]</span
>
</p>
<p>
Dies lässt sich mit obiger Beziehung direkt zu
<span class="math display"
>\[\begin{align} \vvec{x} &= \prox{C}(\vvec{x} + \vvec{p} -
\vvec{x}) \\ &= \prox{C}(\vvec{p}). \end{align}\]</span
>
umschreiben. Aus dem erkennen wir, dass der Ursprung des Normalkegels,
worin ein <strong>beliebiger</strong> Punkt
<span class="math inline">\(\vvec{p}\)</span> liegt, direkt der
<strong>proximale</strong> Punkt ist zu
<span class="math inline">\(\vvec{p}\)</span>.
</p>
<p>
Müssten wir nun eine Projektionsfunktion auf ein
<span class="math inline">\(2\)</span>d-Dreieck herleiten, würden wir
folgendes Bild malen:
</p>
<figure id="fig:normalconetri">
<img
src="files/normal-cone-triangle.svg"
style="width: 100%; max-width: 7cm"
alt="Figure 2: Normalkegel an die Punkte \vvec{a}, \vvec{b} und \vvec{c} eines Dreiecks."
/>
<figcaption aria-hidden="true">
Figure 2: Normalkegel an die Punkte
<span class="math inline">\(\vvec{a}\)</span>,
<span class="math inline">\(\vvec{b}\)</span> und
<span class="math inline">\(\vvec{c}\)</span> eines Dreiecks.
</figcaption>
</figure>
<p>
Das heisst es gibt genau 3 nicht triviale Normalkegel und 3 einfachere
Normalkegel (bestehend lediglich aus den Normalen auf die
Seitenflächen). Eine Projektionsfunktion auf ein Dreieck muss diese 6
Bereiche beachten und ist so auch optimal und richtig implementiert.
</p>
<h3
data-number="2.1.5"
id="zusammenhang-von-normalkegel-und-konvexer-optimierung"
>
<span class="header-section-number">2.1.5</span> Zusammenhang von
Normalkegel und Konvexer Optimierung
</h3>
<p>
Um hier mathematisch nicht in einen Exzess zu geraten, wird hier nur
eine abgespeckte Erklärung gegeben. Für mehr Informationen sei auf
<span class="citation" data-cites="nuetzig_thesis_2016"
><a href="#ref-nuetzig_thesis_2016" role="doc-biblioref"
>[1, Ch. 6]</a
></span
>
verwiesen und die darin enthaltenen Referenzen.
</p>
<p>
Betrachtet man folgendes allgemeine restriktierte
<strong>konvexe</strong> Optimierungsproblem:
<span class="math display"
>\[\begin{align} \vvec{x}^* = \underset{\vvec{x} \ \in \
\set{C}}{\argmin} f(\vvec{x}), \label{eq:convexproblem}
\end{align}\]</span
>
wobei die Funktion
<span class="math inline">\(f(\vvec{x}) \in \mathbb{R}\)</span>
<strong>strikt konvex</strong> und <strong>differenzierbar</strong> (man
stelle sich den oberen Teil eines Weinglases vor, wobei
<span class="math inline">\(\vvec{x} \in \mathbb{R}^2\)</span>) ist und
die minimierenden Punkte
<span class="math inline">\(\vvec{x}\)</span> auf eine
<strong>konvexe</strong> Menge
<span class="math inline">\(\set{C}\)</span> restriktiert sind. Der
minimierende Punkt ist hier mit
<span class="math inline">\(\vvec{x}^*\)</span> bezeichnet. Es gibt nur
<strong>einen</strong> solchen globalen minimierenden Punkt
</p>
<p>
Dann kann man das Problem in ein freies
<strong>konvexes</strong> Programm umschreiben indem man die
Einschränkung
<span class="math inline">\(\vvec{x} \in \set{C}\)</span> mit einer
Bestrafungsfunktion
<span class="math inline">\(\indf{C}(\vvec{x})\)</span> ersetzt
<span class="math display"
>\[\begin{align} \vvec{x}^* = \underset{\vvec{x}}{\argmin} f(\vvec{x})
+ \indf{C}(\vvec{x}). \end{align}\]</span
>
</p>
<p>
Die Bestrafungsfunktion
<span class="math inline">\(\indf{C}(\vvec{x})\)</span> liefert
<span class="math inline">\(0\)</span> falls
<span class="math inline">\(\vvec{x} \in \set{C}\)</span> und sonst
<span class="math inline">\(+\infty\)</span>. Diese Funktion wird
<strong>Indikatorfunktion</strong> genannt.
</p>
<p>
Die Frage ist nun wie kriegen wir eine Bedingung an den optimalen
(minimierenden) Punkt <span class="math inline">\(\vvec{x}^*\)</span>.
Das geht ziemlich analog zu der Bedingung für Minima/Maxima einer
differenzierbaren Funktion <span class="math inline">\(f\)</span> :
<span class="math display"
>\[\begin{align} \vvec{0} = \frac{df}{d\vvec{x}}(\vvec{x}^*)
\label{eq:optimality-difffunc} \end{align}\]</span
>
was konkret heisst, dass der Nullvektor
<span class="math inline">\(\vvec{0}\)</span> gleich dem Gradient
<span class="math inline">\(\frac{df}{d\vvec{x}}\)</span> ist an der
optimalen Stelle <span class="math inline">\(\vvec{x}^*\)</span>.
</p>
<p>
Da wir aber bei unserem Problem
<span class="math inline">\(\eqref{eq:convexproblem}\)</span> diese
<strong>unstetige</strong>,
<strong>nicht-differenzierbare</strong> Bestrafungsfunktion
<span class="math inline">\(\indf{C}\)</span> eingebaut haben, ist dies
nicht direkt mit der normalen Differentiation zu machen. Man braucht in
der konvexen Analysis eine verallgemeinerte Ableitung - das
<strong>Subdifferential</strong>, welches nicht mehr nur einfache
Steigungen (d.h. die Steigung für
<span class="math inline">\(1\)</span>-dimensionale Funktionen
<span class="math inline">\(f(x)\)</span> oder allgemeiner der Gradient
für <span class="math inline">\(n\)</span>-dimensionale Funktionen
<span class="math inline">\(f(\vvec{x})\)</span>) zurück geben kann
sondern auch <strong>ganze Mengen</strong> von solchen Steigungen. Das
heisst, das Subdifferential an einem Punkt ist eine Menge aller
Gradienten an diesen Punkt der Funktion. Das heisst direkt, dass eine
Gleichheit zu <span class="math inline">\(\vvec{0}\)</span> wie in
<span class="math inline">\(\eqref{eq:optimality-difffunc}\)</span>
nicht mehr richtig wäre und hier eine Mengen-Inklusion
<span class="math inline">\(\vvec{0} \in \dots\)</span> stehen muss.
</p>
<p>