## SigmoidalProgramming.jl

Julia Package for Sigmoidal Programming
Popularity
12 Stars
Updated Last
1 Year Ago
Started In
November 2014

# SigmoidalPrograming

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.

## Installation

You can install the package from the Julia prompt

``````Pkg.add("SigmoidalProgramming")
``````

## Linear Sigmoidal Programs

The `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 `i`. A sigmoidal function is a function `f(x)` that, for some number `z`, is convex in `x` for `x <= z` and is concave in `x` for `x >= z`. (Convex functions are sigmoidal with `z = float("inf")`, and concave functions are sigmoidal with `z = -float("inf")`.)

The functions `f` are specified with three lists:

1. `fs`, a list of functions such that `fs[i](x)` computes the value of `f_i` at `x`.
2. `dfs`, a list of functions such that `dfs[i](x)` computes the derivative of `f_i` at `x`.
3. `z`, a list of numbers such that `f_i` is convex in its argument `x` for `x <= z` and is concave in `x` for `x >= z`.

Let's see how to use it to solve a random sigmoidal program with only inequality constraints. We'll let `f_i = x -> 1/(1 + exp(-x))` be the `logistic` function for every `i`. The logistic function and its derivative `logistic_prime` are defined in the file `functions.jl`.

``````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.

## Solver parameters

The accuracy of the solution can be controlled with the parameters

• `maxiters`, the maximum number of branch and bound iterations (default: `100`)
• `TOL`, the desired gap between the upper and lower bound on the optimal value (default: `1e-2`)

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 than `TOL`.

The call signature for `solve_sp` is as follows:

``````solve_sp(l, u, problem::SigmoidalProgram;
TOL = 1e-2, maxiters = 100, verbose = false)
``````

### Required Packages

View all packages

### Used By Packages

No packages found.