-
Notifications
You must be signed in to change notification settings - Fork 251
/
Basic.lean
681 lines (508 loc) Β· 23.1 KB
/
Basic.lean
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
/-
Copyright (c) 2020 Yury Kudryashov. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yury Kudryashov, FrΓ©dΓ©ric Dupuis
-/
import Mathlib.Analysis.Convex.Hull
#align_import analysis.convex.cone.basic from "leanprover-community/mathlib"@"915591b2bb3ea303648db07284a161a7f2a9e3d4"
/-!
# Convex cones
In a `π`-module `E`, we define a convex cone as a set `s` such that `a β’ x + b β’ y β s` whenever
`x, y β s` and `a, b > 0`. We prove that convex cones form a `CompleteLattice`, and define their
images (`ConvexCone.map`) and preimages (`ConvexCone.comap`) under linear maps.
We define pointed, blunt, flat and salient cones, and prove the correspondence between
convex cones and ordered modules.
We define `Convex.toCone` to be the minimal cone that includes a given convex set.
## Main statements
In `Mathlib/Analysis/Convex/Cone/Extension.lean` we prove
the M. Riesz extension theorem and a form of the Hahn-Banach theorem.
In `Mathlib/Analysis/Convex/Cone/Dual.lean` we prove
a variant of the hyperplane separation theorem.
## Implementation notes
While `Convex π` is a predicate on sets, `ConvexCone π E` is a bundled convex cone.
## References
* https://en.wikipedia.org/wiki/Convex_cone
* [Stephen P. Boyd and Lieven Vandenberghe, *Convex Optimization*][boydVandenberghe2004]
* [Emo Welzl and Bernd GΓ€rtner, *Cone Programming*][welzl_garter]
-/
assert_not_exists NormedSpace
assert_not_exists Real
open Set LinearMap
open scoped Classical
open Pointwise
variable {π E F G : Type*}
/-! ### Definition of `ConvexCone` and basic properties -/
section Definitions
variable (π E)
variable [OrderedSemiring π]
/-- A convex cone is a subset `s` of a `π`-module such that `a β’ x + b β’ y β s` whenever `a, b > 0`
and `x, y β s`. -/
structure ConvexCone [AddCommMonoid E] [SMul π E] where
carrier : Set E
smul_mem' : β β¦c : πβ¦, 0 < c β β β¦x : Eβ¦, x β carrier β c β’ x β carrier
add_mem' : β β¦xβ¦ (_ : x β carrier) β¦yβ¦ (_ : y β carrier), x + y β carrier
#align convex_cone ConvexCone
end Definitions
namespace ConvexCone
section OrderedSemiring
variable [OrderedSemiring π] [AddCommMonoid E]
section SMul
variable [SMul π E] (S T : ConvexCone π E)
instance : SetLike (ConvexCone π E) E where
coe := carrier
coe_injective' S T h := by cases S; cases T; congr
@[simp]
theorem coe_mk {s : Set E} {hβ hβ} : β(@mk π _ _ _ _ s hβ hβ) = s :=
rfl
#align convex_cone.coe_mk ConvexCone.coe_mk
@[simp]
theorem mem_mk {s : Set E} {hβ hβ x} : x β @mk π _ _ _ _ s hβ hβ β x β s :=
Iff.rfl
#align convex_cone.mem_mk ConvexCone.mem_mk
/-- Two `ConvexCone`s are equal if they have the same elements. -/
@[ext]
theorem ext {S T : ConvexCone π E} (h : β x, x β S β x β T) : S = T :=
SetLike.ext h
#align convex_cone.ext ConvexCone.ext
@[aesop safe apply (rule_sets := [SetLike])]
theorem smul_mem {c : π} {x : E} (hc : 0 < c) (hx : x β S) : c β’ x β S :=
S.smul_mem' hc hx
#align convex_cone.smul_mem ConvexCone.smul_mem
theorem add_mem β¦xβ¦ (hx : x β S) β¦yβ¦ (hy : y β S) : x + y β S :=
S.add_mem' hx hy
#align convex_cone.add_mem ConvexCone.add_mem
instance : AddMemClass (ConvexCone π E) E where add_mem ha hb := add_mem _ ha hb
instance : Inf (ConvexCone π E) :=
β¨fun S T =>
β¨S β© T, fun _ hc _ hx => β¨S.smul_mem hc hx.1, T.smul_mem hc hx.2β©, fun _ hx _ hy =>
β¨S.add_mem hx.1 hy.1, T.add_mem hx.2 hy.2β©β©β©
@[simp]
theorem coe_inf : ((S β T : ConvexCone π E) : Set E) = βS β© βT :=
rfl
#align convex_cone.coe_inf ConvexCone.coe_inf
theorem mem_inf {x} : x β S β T β x β S β§ x β T :=
Iff.rfl
#align convex_cone.mem_inf ConvexCone.mem_inf
instance : InfSet (ConvexCone π E) :=
β¨fun S =>
β¨β s β S, βs, fun _ hc _ hx => mem_biInter fun s hs => s.smul_mem hc <| mem_iInterβ.1 hx s hs,
fun _ hx _ hy =>
mem_biInter fun s hs => s.add_mem (mem_iInterβ.1 hx s hs) (mem_iInterβ.1 hy s hs)β©β©
@[simp]
theorem coe_sInf (S : Set (ConvexCone π E)) : β(sInf S) = β s β S, (s : Set E) :=
rfl
#align convex_cone.coe_Inf ConvexCone.coe_sInf
theorem mem_sInf {x : E} {S : Set (ConvexCone π E)} : x β sInf S β β s β S, x β s :=
mem_iInterβ
#align convex_cone.mem_Inf ConvexCone.mem_sInf
@[simp]
theorem coe_iInf {ΞΉ : Sort*} (f : ΞΉ β ConvexCone π E) : β(iInf f) = β i, (f i : Set E) := by
simp [iInf]
#align convex_cone.coe_infi ConvexCone.coe_iInf
theorem mem_iInf {ΞΉ : Sort*} {x : E} {f : ΞΉ β ConvexCone π E} : x β iInf f β β i, x β f i :=
mem_iInterβ.trans <| by simp
#align convex_cone.mem_infi ConvexCone.mem_iInf
variable (π)
instance : Bot (ConvexCone π E) :=
β¨β¨β
, fun _ _ _ => False.elim, fun _ => False.elimβ©β©
theorem mem_bot (x : E) : (x β (β₯ : ConvexCone π E)) = False :=
rfl
#align convex_cone.mem_bot ConvexCone.mem_bot
@[simp]
theorem coe_bot : β(β₯ : ConvexCone π E) = (β
: Set E) :=
rfl
#align convex_cone.coe_bot ConvexCone.coe_bot
instance : Top (ConvexCone π E) :=
β¨β¨univ, fun _ _ _ _ => mem_univ _, fun _ _ _ _ => mem_univ _β©β©
theorem mem_top (x : E) : x β (β€ : ConvexCone π E) :=
mem_univ x
#align convex_cone.mem_top ConvexCone.mem_top
@[simp]
theorem coe_top : β(β€ : ConvexCone π E) = (univ : Set E) :=
rfl
#align convex_cone.coe_top ConvexCone.coe_top
instance : CompleteLattice (ConvexCone π E) :=
{ SetLike.instPartialOrder with
le := (Β· β€ Β·)
lt := (Β· < Β·)
bot := β₯
bot_le := fun _ _ => False.elim
top := β€
le_top := fun _ x _ => mem_top π x
inf := (Β· β Β·)
sInf := InfSet.sInf
sup := fun a b => sInf { x | a β€ x β§ b β€ x }
sSup := fun s => sInf { T | β S β s, S β€ T }
le_sup_left := fun _ _ => fun _ hx => mem_sInf.2 fun _ hs => hs.1 hx
le_sup_right := fun _ _ => fun _ hx => mem_sInf.2 fun _ hs => hs.2 hx
sup_le := fun _ _ c ha hb _ hx => mem_sInf.1 hx c β¨ha, hbβ©
le_inf := fun _ _ _ ha hb _ hx => β¨ha hx, hb hxβ©
inf_le_left := fun _ _ _ => And.left
inf_le_right := fun _ _ _ => And.right
le_sSup := fun _ p hs _ hx => mem_sInf.2 fun _ ht => ht p hs hx
sSup_le := fun _ p hs _ hx => mem_sInf.1 hx p hs
le_sInf := fun _ _ ha _ hx => mem_sInf.2 fun t ht => ha t ht hx
sInf_le := fun _ _ ha _ hx => mem_sInf.1 hx _ ha }
instance : Inhabited (ConvexCone π E) :=
β¨β₯β©
end SMul
section Module
variable [Module π E] (S : ConvexCone π E)
protected theorem convex : Convex π (S : Set E) :=
convex_iff_forall_pos.2 fun _ hx _ hy _ _ ha hb _ =>
S.add_mem (S.smul_mem ha hx) (S.smul_mem hb hy)
#align convex_cone.convex ConvexCone.convex
end Module
section Maps
variable [AddCommMonoid E] [AddCommMonoid F] [AddCommMonoid G]
variable [Module π E] [Module π F] [Module π G]
/-- The image of a convex cone under a `π`-linear map is a convex cone. -/
def map (f : E ββ[π] F) (S : ConvexCone π E) : ConvexCone π F where
carrier := f '' S
smul_mem' := fun c hc _ β¨x, hx, hyβ© => hy βΈ f.map_smul c x βΈ mem_image_of_mem f (S.smul_mem hc hx)
add_mem' := fun _ β¨xβ, hxβ, hyββ© _ β¨xβ, hxβ, hyββ© =>
hyβ βΈ hyβ βΈ f.map_add xβ xβ βΈ mem_image_of_mem f (S.add_mem hxβ hxβ)
#align convex_cone.map ConvexCone.map
@[simp, norm_cast]
theorem coe_map (S : ConvexCone π E) (f : E ββ[π] F) : (S.map f : Set F) = f '' S :=
rfl
@[simp]
theorem mem_map {f : E ββ[π] F} {S : ConvexCone π E} {y : F} : y β S.map f β β x β S, f x = y :=
Set.mem_image f S y
#align convex_cone.mem_map ConvexCone.mem_map
theorem map_map (g : F ββ[π] G) (f : E ββ[π] F) (S : ConvexCone π E) :
(S.map f).map g = S.map (g.comp f) :=
SetLike.coe_injective <| image_image g f S
#align convex_cone.map_map ConvexCone.map_map
@[simp]
theorem map_id (S : ConvexCone π E) : S.map LinearMap.id = S :=
SetLike.coe_injective <| image_id _
#align convex_cone.map_id ConvexCone.map_id
/-- The preimage of a convex cone under a `π`-linear map is a convex cone. -/
def comap (f : E ββ[π] F) (S : ConvexCone π F) : ConvexCone π E where
carrier := f β»ΒΉ' S
smul_mem' c hc x hx := by
rw [mem_preimage, f.map_smul c]
exact S.smul_mem hc hx
add_mem' x hx y hy := by
rw [mem_preimage, f.map_add]
exact S.add_mem hx hy
#align convex_cone.comap ConvexCone.comap
@[simp]
theorem coe_comap (f : E ββ[π] F) (S : ConvexCone π F) : (S.comap f : Set E) = f β»ΒΉ' S :=
rfl
#align convex_cone.coe_comap ConvexCone.coe_comap
@[simp] -- Porting note: was not a `dsimp` lemma
theorem comap_id (S : ConvexCone π E) : S.comap LinearMap.id = S :=
rfl
#align convex_cone.comap_id ConvexCone.comap_id
theorem comap_comap (g : F ββ[π] G) (f : E ββ[π] F) (S : ConvexCone π G) :
(S.comap g).comap f = S.comap (g.comp f) :=
rfl
#align convex_cone.comap_comap ConvexCone.comap_comap
@[simp]
theorem mem_comap {f : E ββ[π] F} {S : ConvexCone π F} {x : E} : x β S.comap f β f x β S :=
Iff.rfl
#align convex_cone.mem_comap ConvexCone.mem_comap
end Maps
end OrderedSemiring
section LinearOrderedField
variable [LinearOrderedField π]
section MulAction
variable [AddCommMonoid E]
variable [MulAction π E] (S : ConvexCone π E)
theorem smul_mem_iff {c : π} (hc : 0 < c) {x : E} : c β’ x β S β x β S :=
β¨fun h => inv_smul_smulβ hc.ne' x βΈ S.smul_mem (inv_pos.2 hc) h, S.smul_mem hcβ©
#align convex_cone.smul_mem_iff ConvexCone.smul_mem_iff
end MulAction
section OrderedAddCommGroup
variable [OrderedAddCommGroup E] [Module π E]
/-- Constructs an ordered module given an `OrderedAddCommGroup`, a cone, and a proof that
the order relation is the one defined by the cone.
-/
theorem to_orderedSMul (S : ConvexCone π E) (h : β x y : E, x β€ y β y - x β S) : OrderedSMul π E :=
OrderedSMul.mk'
(by
intro x y z xy hz
rw [h (z β’ x) (z β’ y), β smul_sub z y x]
exact smul_mem S hz ((h x y).mp xy.le))
#align convex_cone.to_ordered_smul ConvexCone.to_orderedSMul
end OrderedAddCommGroup
end LinearOrderedField
/-! ### Convex cones with extra properties -/
section OrderedSemiring
variable [OrderedSemiring π]
section AddCommMonoid
variable [AddCommMonoid E] [SMul π E] (S : ConvexCone π E)
/-- A convex cone is pointed if it includes `0`. -/
def Pointed (S : ConvexCone π E) : Prop :=
(0 : E) β S
#align convex_cone.pointed ConvexCone.Pointed
/-- A convex cone is blunt if it doesn't include `0`. -/
def Blunt (S : ConvexCone π E) : Prop :=
(0 : E) β S
#align convex_cone.blunt ConvexCone.Blunt
theorem pointed_iff_not_blunt (S : ConvexCone π E) : S.Pointed β Β¬S.Blunt :=
β¨fun hβ hβ => hβ hβ, Classical.not_not.mpβ©
#align convex_cone.pointed_iff_not_blunt ConvexCone.pointed_iff_not_blunt
theorem blunt_iff_not_pointed (S : ConvexCone π E) : S.Blunt β Β¬S.Pointed := by
rw [pointed_iff_not_blunt, Classical.not_not]
#align convex_cone.blunt_iff_not_pointed ConvexCone.blunt_iff_not_pointed
theorem Pointed.mono {S T : ConvexCone π E} (h : S β€ T) : S.Pointed β T.Pointed :=
@h _
#align convex_cone.pointed.mono ConvexCone.Pointed.mono
theorem Blunt.anti {S T : ConvexCone π E} (h : T β€ S) : S.Blunt β T.Blunt :=
(Β· β @h 0)
#align convex_cone.blunt.anti ConvexCone.Blunt.anti
end AddCommMonoid
section AddCommGroup
variable [AddCommGroup E] [SMul π E] (S : ConvexCone π E)
/-- A convex cone is flat if it contains some nonzero vector `x` and its opposite `-x`. -/
def Flat : Prop :=
β x β S, x β (0 : E) β§ -x β S
#align convex_cone.flat ConvexCone.Flat
/-- A convex cone is salient if it doesn't include `x` and `-x` for any nonzero `x`. -/
def Salient : Prop :=
β x β S, x β (0 : E) β -x β S
#align convex_cone.salient ConvexCone.Salient
theorem salient_iff_not_flat (S : ConvexCone π E) : S.Salient β Β¬S.Flat := by
simp [Salient, Flat]
#align convex_cone.salient_iff_not_flat ConvexCone.salient_iff_not_flat
theorem Flat.mono {S T : ConvexCone π E} (h : S β€ T) : S.Flat β T.Flat
| β¨x, hxS, hx, hnxSβ© => β¨x, h hxS, hx, h hnxSβ©
#align convex_cone.flat.mono ConvexCone.Flat.mono
theorem Salient.anti {S T : ConvexCone π E} (h : T β€ S) : S.Salient β T.Salient :=
fun hS x hxT hx hnT => hS x (h hxT) hx (h hnT)
#align convex_cone.salient.anti ConvexCone.Salient.anti
/-- A flat cone is always pointed (contains `0`). -/
theorem Flat.pointed {S : ConvexCone π E} (hS : S.Flat) : S.Pointed := by
obtain β¨x, hx, _, hxnegβ© := hS
rw [Pointed, β add_neg_self x]
exact add_mem S hx hxneg
#align convex_cone.flat.pointed ConvexCone.Flat.pointed
/-- A blunt cone (one not containing `0`) is always salient. -/
theorem Blunt.salient {S : ConvexCone π E} : S.Blunt β S.Salient := by
rw [salient_iff_not_flat, blunt_iff_not_pointed]
exact mt Flat.pointed
#align convex_cone.blunt.salient ConvexCone.Blunt.salient
/-- A pointed convex cone defines a preorder. -/
def toPreorder (hβ : S.Pointed) : Preorder E where
le x y := y - x β S
le_refl x := by change x - x β S; rw [sub_self x]; exact hβ
le_trans x y z xy zy := by simpa using add_mem S zy xy
#align convex_cone.to_preorder ConvexCone.toPreorder
/-- A pointed and salient cone defines a partial order. -/
def toPartialOrder (hβ : S.Pointed) (hβ : S.Salient) : PartialOrder E :=
{ toPreorder S hβ with
le_antisymm := by
intro a b ab ba
by_contra h
have h' : b - a β 0 := fun h'' => h (eq_of_sub_eq_zero h'').symm
have H := hβ (b - a) ab h'
rw [neg_sub b a] at H
exact H ba }
#align convex_cone.to_partial_order ConvexCone.toPartialOrder
/-- A pointed and salient cone defines an `OrderedAddCommGroup`. -/
def toOrderedAddCommGroup (hβ : S.Pointed) (hβ : S.Salient) : OrderedAddCommGroup E :=
{ toPartialOrder S hβ hβ, show AddCommGroup E by infer_instance with
add_le_add_left := by
intro a b hab c
change c + b - (c + a) β S
rw [add_sub_add_left_eq_sub]
exact hab }
#align convex_cone.to_ordered_add_comm_group ConvexCone.toOrderedAddCommGroup
end AddCommGroup
section Module
variable [AddCommMonoid E] [Module π E]
instance : Zero (ConvexCone π E) :=
β¨β¨0, fun _ _ => by simp, fun _ => by simpβ©β©
@[simp]
theorem mem_zero (x : E) : x β (0 : ConvexCone π E) β x = 0 :=
Iff.rfl
#align convex_cone.mem_zero ConvexCone.mem_zero
@[simp]
theorem coe_zero : ((0 : ConvexCone π E) : Set E) = 0 :=
rfl
#align convex_cone.coe_zero ConvexCone.coe_zero
theorem pointed_zero : (0 : ConvexCone π E).Pointed := by rw [Pointed, mem_zero]
#align convex_cone.pointed_zero ConvexCone.pointed_zero
instance instAdd : Add (ConvexCone π E) :=
β¨fun Kβ Kβ =>
{ carrier := { z | β x β Kβ, β y β Kβ, x + y = z }
smul_mem' := by
rintro c hc _ β¨x, hx, y, hy, rflβ©
rw [smul_add]
use c β’ x, Kβ.smul_mem hc hx, c β’ y, Kβ.smul_mem hc hy
add_mem' := by
rintro _ β¨xβ, hxβ, xβ, hxβ, rflβ© y β¨yβ, hyβ, yβ, hyβ, rflβ©
use xβ + yβ, Kβ.add_mem hxβ hyβ, xβ + yβ, Kβ.add_mem hxβ hyβ
abel }β©
@[simp]
theorem mem_add {Kβ Kβ : ConvexCone π E} {a : E} :
a β Kβ + Kβ β β x β Kβ, β y β Kβ, x + y = a :=
Iff.rfl
#align convex_cone.mem_add ConvexCone.mem_add
instance instAddZeroClass : AddZeroClass (ConvexCone π E) where
zero_add _ := by ext; simp
add_zero _ := by ext; simp
instance instAddCommSemigroup : AddCommSemigroup (ConvexCone π E) where
add := Add.add
add_assoc _ _ _ := SetLike.coe_injective <| add_assoc _ _ _
add_comm _ _ := SetLike.coe_injective <| add_comm _ _
end Module
end OrderedSemiring
end ConvexCone
namespace Submodule
/-! ### Submodules are cones -/
section OrderedSemiring
variable [OrderedSemiring π]
section AddCommMonoid
variable [AddCommMonoid E] [Module π E]
/-- Every submodule is trivially a convex cone. -/
def toConvexCone (S : Submodule π E) : ConvexCone π E where
carrier := S
smul_mem' c _ _ hx := S.smul_mem c hx
add_mem' _ hx _ hy := S.add_mem hx hy
#align submodule.to_convex_cone Submodule.toConvexCone
@[simp]
theorem coe_toConvexCone (S : Submodule π E) : βS.toConvexCone = (S : Set E) :=
rfl
#align submodule.coe_to_convex_cone Submodule.coe_toConvexCone
@[simp]
theorem mem_toConvexCone {x : E} {S : Submodule π E} : x β S.toConvexCone β x β S :=
Iff.rfl
#align submodule.mem_to_convex_cone Submodule.mem_toConvexCone
@[simp]
theorem toConvexCone_le_iff {S T : Submodule π E} : S.toConvexCone β€ T.toConvexCone β S β€ T :=
Iff.rfl
#align submodule.to_convex_cone_le_iff Submodule.toConvexCone_le_iff
@[simp]
theorem toConvexCone_bot : (β₯ : Submodule π E).toConvexCone = 0 :=
rfl
#align submodule.to_convex_cone_bot Submodule.toConvexCone_bot
@[simp]
theorem toConvexCone_top : (β€ : Submodule π E).toConvexCone = β€ :=
rfl
#align submodule.to_convex_cone_top Submodule.toConvexCone_top
@[simp]
theorem toConvexCone_inf (S T : Submodule π E) :
(S β T).toConvexCone = S.toConvexCone β T.toConvexCone :=
rfl
#align submodule.to_convex_cone_inf Submodule.toConvexCone_inf
@[simp]
theorem pointed_toConvexCone (S : Submodule π E) : S.toConvexCone.Pointed :=
S.zero_mem
#align submodule.pointed_to_convex_cone Submodule.pointed_toConvexCone
end AddCommMonoid
end OrderedSemiring
end Submodule
namespace ConvexCone
/-! ### Positive cone of an ordered module -/
section PositiveCone
variable (π E) [OrderedSemiring π] [OrderedAddCommGroup E] [Module π E] [OrderedSMul π E]
/-- The positive cone is the convex cone formed by the set of nonnegative elements in an ordered
module.
-/
def positive : ConvexCone π E where
carrier := Set.Ici 0
smul_mem' _ hc _ (hx : _ β€ _) := smul_nonneg hc.le hx
add_mem' _ (hx : _ β€ _) _ (hy : _ β€ _) := add_nonneg hx hy
#align convex_cone.positive ConvexCone.positive
@[simp]
theorem mem_positive {x : E} : x β positive π E β 0 β€ x :=
Iff.rfl
#align convex_cone.mem_positive ConvexCone.mem_positive
@[simp]
theorem coe_positive : β(positive π E) = Set.Ici (0 : E) :=
rfl
#align convex_cone.coe_positive ConvexCone.coe_positive
/-- The positive cone of an ordered module is always salient. -/
theorem salient_positive : Salient (positive π E) := fun x xs hx hx' =>
lt_irrefl (0 : E)
(calc
0 < x := lt_of_le_of_ne xs hx.symm
_ β€ x + -x := (le_add_of_nonneg_right hx')
_ = 0 := add_neg_self x
)
#align convex_cone.salient_positive ConvexCone.salient_positive
/-- The positive cone of an ordered module is always pointed. -/
theorem pointed_positive : Pointed (positive π E) :=
le_refl 0
#align convex_cone.pointed_positive ConvexCone.pointed_positive
/-- The cone of strictly positive elements.
Note that this naming diverges from the mathlib convention of `pos` and `nonneg` due to "positive
cone" (`ConvexCone.positive`) being established terminology for the non-negative elements. -/
def strictlyPositive : ConvexCone π E where
carrier := Set.Ioi 0
smul_mem' _ hc _ (hx : _ < _) := smul_pos hc hx
add_mem' _ hx _ hy := add_pos hx hy
#align convex_cone.strictly_positive ConvexCone.strictlyPositive
@[simp]
theorem mem_strictlyPositive {x : E} : x β strictlyPositive π E β 0 < x :=
Iff.rfl
#align convex_cone.mem_strictly_positive ConvexCone.mem_strictlyPositive
@[simp]
theorem coe_strictlyPositive : β(strictlyPositive π E) = Set.Ioi (0 : E) :=
rfl
#align convex_cone.coe_strictly_positive ConvexCone.coe_strictlyPositive
theorem positive_le_strictlyPositive : strictlyPositive π E β€ positive π E := fun _ => le_of_lt
#align convex_cone.positive_le_strictly_positive ConvexCone.positive_le_strictlyPositive
/-- The strictly positive cone of an ordered module is always salient. -/
theorem salient_strictlyPositive : Salient (strictlyPositive π E) :=
(salient_positive π E).anti <| positive_le_strictlyPositive π E
#align convex_cone.salient_strictly_positive ConvexCone.salient_strictlyPositive
/-- The strictly positive cone of an ordered module is always blunt. -/
theorem blunt_strictlyPositive : Blunt (strictlyPositive π E) :=
lt_irrefl 0
#align convex_cone.blunt_strictly_positive ConvexCone.blunt_strictlyPositive
end PositiveCone
end ConvexCone
/-! ### Cone over a convex set -/
section ConeFromConvex
variable [LinearOrderedField π] [AddCommGroup E] [Module π E]
namespace Convex
/-- The set of vectors proportional to those in a convex set forms a convex cone. -/
def toCone (s : Set E) (hs : Convex π s) : ConvexCone π E := by
apply ConvexCone.mk (β (c : π) (_ : 0 < c), c β’ s) <;> simp only [mem_iUnion, mem_smul_set]
Β· rintro c c_pos _ β¨c', c'_pos, x, hx, rflβ©
exact β¨c * c', mul_pos c_pos c'_pos, x, hx, (smul_smul _ _ _).symmβ©
Β· rintro _ β¨cx, cx_pos, x, hx, rflβ© _ β¨cy, cy_pos, y, hy, rflβ©
have : 0 < cx + cy := add_pos cx_pos cy_pos
refine' β¨_, this, _, convex_iff_div.1 hs hx hy cx_pos.le cy_pos.le this, _β©
simp only [smul_add, smul_smul, mul_div_assoc', mul_div_cancel_leftβ _ this.ne']
#align convex.to_cone Convex.toCone
variable {s : Set E} (hs : Convex π s) {x : E}
theorem mem_toCone : x β hs.toCone s β β c : π, 0 < c β§ β y β s, c β’ y = x := by
simp only [toCone, ConvexCone.mem_mk, mem_iUnion, mem_smul_set, eq_comm, exists_prop]
#align convex.mem_to_cone Convex.mem_toCone
theorem mem_toCone' : x β hs.toCone s β β c : π, 0 < c β§ c β’ x β s := by
refine' hs.mem_toCone.trans β¨_, _β©
Β· rintro β¨c, hc, y, hy, rflβ©
exact β¨cβ»ΒΉ, inv_pos.2 hc, by rwa [smul_smul, inv_mul_cancel hc.ne', one_smul]β©
Β· rintro β¨c, hc, hcxβ©
exact β¨cβ»ΒΉ, inv_pos.2 hc, _, hcx, by rw [smul_smul, inv_mul_cancel hc.ne', one_smul]β©
#align convex.mem_to_cone' Convex.mem_toCone'
theorem subset_toCone : s β hs.toCone s := fun x hx =>
hs.mem_toCone'.2 β¨1, zero_lt_one, by rwa [one_smul]β©
#align convex.subset_to_cone Convex.subset_toCone
/-- `hs.toCone s` is the least cone that includes `s`. -/
theorem toCone_isLeast : IsLeast { t : ConvexCone π E | s β t } (hs.toCone s) := by
refine' β¨hs.subset_toCone, fun t ht x hx => _β©
rcases hs.mem_toCone.1 hx with β¨c, hc, y, hy, rflβ©
exact t.smul_mem hc (ht hy)
#align convex.to_cone_is_least Convex.toCone_isLeast
theorem toCone_eq_sInf : hs.toCone s = sInf { t : ConvexCone π E | s β t } :=
hs.toCone_isLeast.isGLB.sInf_eq.symm
#align convex.to_cone_eq_Inf Convex.toCone_eq_sInf
end Convex
theorem convexHull_toCone_isLeast (s : Set E) :
IsLeast { t : ConvexCone π E | s β t } ((convex_convexHull π s).toCone _) := by
convert (convex_convexHull π s).toCone_isLeast using 1
ext t
exact β¨fun h => convexHull_min h t.convex, (subset_convexHull π s).transβ©
#align convex_hull_to_cone_is_least convexHull_toCone_isLeast
theorem convexHull_toCone_eq_sInf (s : Set E) :
(convex_convexHull π s).toCone _ = sInf { t : ConvexCone π E | s β t } :=
Eq.symm <| IsGLB.sInf_eq <| IsLeast.isGLB <| convexHull_toCone_isLeast s
#align convex_hull_to_cone_eq_Inf convexHull_toCone_eq_sInf
end ConeFromConvex