Code Directory
 Visual Basic & VB.NET
New Code
OrgChart JS 4.9.7
iScripts CyberMatch 1.3.3
AnyGantt JS Gantt Charts 8.7.0
Database Workbench Pro 5.6.8
Devart SSIS Data Flow Components 1.10.1
SentiMask SDK Trial 2.0.193121
dbForge Studio for SQL Server 5.8
ODBC Driver for ASE 2.1.2
The C# OCR Library 4.4.0
ODBC Driver for xBase 2.1
Rapid PHP 2018 15.5
Online Course Booking Script 1.3.3
Job Portal Script 1.3.2
The C# PDF Library 5.2
Top Code
Azizi search engine script PHP 4.1.10
Faculty Evaluation System 1.1
16-APSK Simulink Block 1.0
SecureBridge 8.0
War Game V4
Moving Star Field 1.1
Active Shape Model (ASM) and Active Appearance Model (AAM) 1.0
ICGroupDeal - Daily deals site 1.0
DTMF tones detection 1.0
Devart SSIS Data Flow Components 1.0
DTMF Encoder/Decoder with GUI using FFT,goertzel,Filter Banks 1.0
TGPS 1.11
Newest MySQL manual in HTML Help (.chm) 4.1.1-alpha
Rapid PHP 2018 15.5 3.02
Top Rated
VisualNEO Web 2018.12.15
Azizi search engine script PHP 4.1.10
Paste phpSoftPro 1.4.1
Extreme Injector 3.7
Deals and Discounts Website Script 1.0.2
ADO.NET Provider for ExactTarget 1.0
Solid File System OS edition 5.1
Classified Ad Lister 1.0
Aglowsoft SQL Query Tools 8.2
Invoice Manager by PHPJabbers 3.0
ICPennyBid Penny Auction Script 4.0
PHP Review Script 1.0
ATN Resume Finder 2.0
ATN Site Builder 3.0
Availability Booking Calendar PHP 1.0
Submodular Function Optimization 1.0
File ID: 80097

Submodular Function Optimization 1.0
Download Submodular Function Optimization 1.0http://www.mathworks.comReport Error Link
License: Freeware
File Size: 266.2 KB
Downloads: 12
Submit Rating:
Submodular Function Optimization 1.0 Description
Description: Matlab Toolbox for Submodular Function Optimization (v 2.0)

By Andreas Krause (
Slides, videos and detailed references available at

Tested in MATLAB 7.0.1 (R14), 7.2.0 (R2006a), 7.4.0 (R2007a, MAC), 7.9.0 (MAC)

This toolbox provides functions for optimizing submodular set functions, i.e., functions that take a subset A of a finite ground set V to the real numbers, satisfying

$$F(A)+F(B)geq F(Acup B)+F(Acap B)$$

It also presents several examples of applying submodular function optimization to important machine learning problems, such as clustering, inference in probabilistic models and experimental design. There is a demo script: sfo_tutorial.m

Some information on conventions:

All algorithms will use function objects (see sfo_tutorial.m for examples). For example, to measure variance reduction in a Gaussian model, call
F = sfo_fn_varred(sigma,V)
where sigma is the covariance matrix and V is the ground set, e.g., 1:size(sigma,1) They will also take an index set V, and A must be a subset of V.

Implemented algorithms:

1) Minimization:

* sfo_min_norm_point: Fujishige's minimum-norm-point algorithm for minimizing general submodular functions
* sfo_queyranne: Queyranne's algorithm for minimizing symmetric submodular functions
* sfo_ssp: Submodular-supermodular procedure of Narasimhan & Bilmes for minimizing the difference of two submodular functions
* sfo_s_t_min_cut: For solving min F(A) s.t. s in A, t not in A
* sfo_minbound: Return an online bound on the minimum solution
* sfo_greedy_splitting: Greedy splitting algorithm for clustering of Zhao et al

2) Maximization:

* sfo_polyhedrongreedy: For solving an LP over the submodular polytope
* sfo_greedy_lazy: The greedy algorithm for constrained maximization / coverage using lazy evaluations
* sfo_greedy_welfare: The greedy algorithm for solving allocation problems
* sfo_cover: Greedy coverage algorithm using lazy evaluations
* sfo_celf: The CELF algorithm of Leskovec et al. for budgeted maximization
* sfo_ls_lazy: Local search algorithm for maximizing nonnegative submodular functions
* sfo_saturate: The _SATURATE_ algorithm of Krause et al. for robust optimization of submodular functions
* sfo_max_dca_lazy: The Data Correcting algorithm of Goldengorin et al. for maximizing general (not necessarily nondecreasing) submodular functions
* sfo_maxbound: Return an online bound on the maximum solution
* sfo_pspiel: pSPIEL algorithm for trading off information and communication cost
* sfo_pspiel_orienteering: pSPIEL algorithm for submodular orienteering
* sfo_balance: eSPASS algorithm for simultaneous placement and balanced scheduling

3) Miscellaneous

* sfo_lovaszext: Computes the Lovasz extension for a submodular function
* sfo_mi_cluster: Example clustering algorithm using both maximization and minimization
* sfo_pspiel_get_path: Convert a tree into a path using the MST heuristic algorithm
* sfo_pspiel_get_cost: Compute the Steiner cost of a tree / path

4) Submodular functions:

* sfo_fn_cutfun: Cut function
* sfo_fn_detect: Outbreak detection / facility location
* sfo_fn_infogain: Information gain about gaussian random variables
* sfo_fn_entropy: Entropy of Gaussian random variables
* sfo_fn_mi: Gaussian mutual information
* sfo_fn_varred: Variance reduction (truncatable, for use in SATURATE)
* sfo_fn_example: Two-element submodular function example from tutorial slides
* sfo_fn_iwata: Iwata's test function for testing minimization code
* sfo_fn_ising: Energy function for Ising model for image denoising
* sfo_fn_residual: For defining residual submodular functions
* sfo_fn_invert: For defining F(A) = F'(VA)-F(V)
* sfo_fn_lincomb: For defining linear combinations of submodular functions

If you use the toolbox for your research, please cite
A. Krause. "SFO: A Toolbox for Submodular Function Optimization". Journal of Machine Learning Research (2010).

License: Freeware

Related: they will also, important machine, Toolbox, submodular polytope, saturate algorithm, steiner cost, measure variance, Real, trading information, tree path submodular, toolbox functions, toolbox submodular, real numbers, mst heuristic, testing minimization

O/S:BSD, Linux, Solaris, Mac OS X

File Size: 266.2 KB

Downloads: 12

More Similar Code

This is a wrapper function to solve optimization problems (using FMINCON) of the form:

min w.r.t. X of
CostFunc(X) = beta*(W_ls*F(X)) + (1 - beta)*(max(W_mm*F(X)))

subject to:
A*X <= B, Aeq*X = Beq (linear constraints)
C(X) <= 0, Ceq(X) = 0 (nonlinear constraints)
LB <= X <= UB (bounds)

A new hybrid population-based
algorithm (PSOGSA) is proposed with the combination of
Particle Swarm Optimization (PSO) and Gravitational Search
Algorithm (GSA). The main idea is to integrate the ability of
exploitation in PSO...

Auto2Fit is a revolution tools and beats all other simliar ones in the area of nonlinear regression.Almost all data analysis software packages (SPSS, SAS, Statistical, Origin Pro, DataFit, Stata or Systat) need end-users to provide/guess initial...

This software contains one example taken from the reference paper given with this program..By running the file P1.m as they are in the default ABC-eld folder the economic dispatch problem can be solved. The allocation minimum fuel cost and...

An animated simulation of Particles in 2D searching for a global minima of a simple function using Particle Swarm Optimization algorithm

Demonstration of finding the minimum of a noisy function using gradient-based optimization.
This model was developed for use in teaching optimization in graduate engineering courses. It demonstrates one approach for attempting to find the...

This upload contains a hybrid Particle Swarm Optimization algorithm for functions in the real space. An options file is also provided, which lets the user fully parameterize the process. The hybrid function used is the @fminsearch, which is...

GANSO is a programming library for global and nonsmooth, nonlinear optimization. Unlike local methods (e.g., quasi-Newton), global optimization methods aim at locating the absolute minimum of a function, not the nearest stationary point. GANSO...

This function solves the mixed integer linear programming problems. It uses the linprog.m function that comes with the optimization toolbox of MATLAB. It employs the branch and bound algorithm. It uses depth first search

This function is a simple but flexible and usefull tool to implement genetic optimization algorithms that work with populations of custom units. This tool allows to customize the fitness function, the stopping criteria and the cross-over and...

User Review for Submodular Function Optimization
- required fields

Please enter text on the image