SigmoidalProgramming is a Julia package for solving sigmoidal programming problems. It solves problems using a branch and bound method described here, and solves the convex subproblems using a cutting plane method.
Usage examples can be found in the examples directory.
You can install the package from the Julia prompt
Linear Sigmoidal Programs
LinearSP problem class can be used to solve any sigmoidal programming problem
with linear equality and inequality constraints, of the form
minimize sum_i f_i(x_i) subject to A x <= b C x == d l <= x <= u
with variable x, where
f_i is a sigmoidal function for every
A sigmoidal function is a function
f(x) that, for some number
z, is convex
x <= z and is concave in
x >= z.
(Convex functions are sigmoidal with
z = float("inf"), and concave functions are sigmoidal with
z = -float("inf").)
f are specified with three lists:
fs, a list of functions such that
fs[i](x)computes the value of
dfs, a list of functions such that
dfs[i](x)computes the derivative of
z, a list of numbers such that
f_iis convex in its argument
x <= zand is concave in
x >= z.
Let's see how to use it to solve a random sigmoidal program with only inequality constraints.
f_i = x -> 1/(1 + exp(-x)) be the
logistic function for every
The logistic function and its derivative
logistic_prime are defined in the file
using SigmoidalProgramming # generate problem data srand(4) nvar = 200 nineqconstr = 20 l = -rand(nvar) u = rand(nvar) A = rand(nineqconstr, nvar) b = rand(nineqconstr) z = zeros(nvar) fs = fill(logistic, nvar) dfs = fill(logistic_prime, nvar) problem = LinearSP(fs, dfs, z, A, b) # branch and bound to solve the problem # pq is a priority queue of the branch and bound nodes at the leaves of the tree # bestnodes is a list of the best branch and bound nodes found, in the order they were found pq, bestnodes, lbs, ubs = solve_sp(l, u, problem) # the best node found yet is the top node on the priority queue node = dequeue!(pq) # println("best node has node.ub = $(node.ub) and solution $(node.x)") # lbs and ubs record the upper and lower bounds on the optimal value # found at each iteration println("lbs: ",lbs) println("ubs: ",ubs)
A problem with equality constraints
C x = d as well can be solved using
problem = LinearSP(fs, dfs, z, A, b, C, d)
A few simple examples of usage can be found in the examples directory.
The accuracy of the solution can be controlled with the parameters
maxiters, the maximum number of branch and bound iterations (default:
TOL, the desired gap between the upper and lower bound on the optimal value (default:
The solver terminates as soon as either
maxiters branch and bound nodes have been split,
or the gap between the upper and lower bound on the optimal value has been proved to be less
The call signature for
solve_sp is as follows:
solve_sp(l, u, problem::SigmoidalProgram; TOL = 1e-2, maxiters = 100, verbose = false)