Submodular Function Optimization 1.0
File ID: 80097
Submodular Function Optimization 1.0
File Size: 266.2 KB
Submodular Function Optimization 1.0 Description
Description: Matlab Toolbox for Submodular Function Optimization (v 2.0)
By Andreas Krause (firstname.lastname@example.org).
Slides, videos and detailed references available at http://www.submodularity.org
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.
* 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
* 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
* 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).
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
|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)))
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