Submodulära set-funktioner har många applikationer i combinatorial optimering, eftersom de kan minimeras och ungefär maximeras i polynom tid. Ett viktigt element i många av algoritmerna och analyserna är möjligheten att utöka den submodulära set-funktionen till en konvex funktion, som öppnar upp verktyg från konvex optimering. Submodularitet går utöver set-funktioner och har naturligtvis övervägts för problem med flera etiketter eller för funktioner som definieras på kontinuerliga domäner, där det i huvudsak motsvarar kors-second-derivatives som är icke-positiva. I detta dokument visar vi att de flesta resultat som rör submodularitet och konvexitet för set-funktioner kan utvidgas till alla submodulära funktioner. I synnerhet (a) vi definierar naturligt en kontinuerlig förlängning i en uppsättning sannolikhetsåtgärder, (b) visar att utbyggnaden är konvex om och endast om den ursprungliga funktionen är submodulär, (c) bevisa att problemet med att minimera en submodulär funktion är likvärdigt med ett typiskt icke-smooth konvex optimering problem, och (d) föreslå en annan konvex optimering problem med bättre beräkningsegenskaper (t.ex. ett jämnt dubbelt problem). De flesta av dessa förlängningar från set-function situationen erhålls genom att dra kopplingar till teorin om multi-marginal optimal transport, vilket också ger en ny tolkning av befintliga resultat för set-functions. Vi tillhandahåller sedan praktiska algoritmer för att minimera generiska submodulära funktioner på diskreta domäner, med tillhörande konvergensgrader.
REF visade kopplingar mellan kontinuerliga submodulära funktioner och konvexa funktioner i samband med minimering.
Submodular Functions: from Discrete to Continous Domains
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}