## CopositiveAnalyticCenter.jl

Analytic center cutting plane method to solve copositive optimization problems
Popularity
0 Stars
Updated Last
10 Months Ago
Started In
June 2020

# CopositiveAnalyticCenter.jl

Solves problems of the form:

``````minimize    dot(obj, x)
subject to  norm(x) ≤ r
oracle(x) == true,
``````

where `obj` is an `AbstractVector`, and `oracle` tests membership of some convex body. The main workhorse is the `accp` function, which solves this problem using an Analytic Center Cutting Plane method. It yields a near-optimal vector `x`.

For some vector `x`, `oracle(x)` should return `true` if `x` lies in the feasible set, or else a `Halfspace` containing the feasible set but not `x`. `Halfspace(slope, constant)` denotes the set `{z: dot(slope, z) ≤ constant}`.

For background information on this algorithm, see this preprint.

## Installation

Simply run

`julia> import Pkg; Pkg.add("CopositiveAnalyticCenter")`

This package will test if Gurobi.jl is installed properly. If not, ECOS.jl and Cbc.jl will be installed.

## Testing copositivity

The package provides the `testcopositive` function, which may be used in defining your `oracle`. For some symmetric matrix `A`, `testcopositive(A)` returns a `Tuple` containing the optimal value and optimal solution to

``````minimize    y' * A * y
subject to  sum(y) = 1
y ≥ 0.
``````

To avoid having to set up the problem above from scratch every time `testcopositive` is called, you can create a `CopositiveChecker` instance `cc`, e.g. `cc = CopositiveChecker(10);` to set up an environment for testing 10-by-10 matrices. To test the 10-by-10 matrix `A` for copositivity using `cc`, call `testcopositive(A, cc)`.

## Transforming vectors to symmetric matrices

To transform a vector to a symmetric matrix, you can use the `vec2mat` function included in the package. Its inverse is `vec2matinv`.

```julia> using CopositiveAnalyticCenter

julia> A = vec2mat([1, 2, 3, 4, 5, 6])
3×3 Array{Int64,2}:
1  2  4
2  3  5
4  5  6

julia> vec2matinv(A)
6-element Array{Int64,1}:
1
2
3
4
5
6```

The adjoint of `vec2mat` with respect to `dot` from LinearAlgebra.jl is `vec2matadj`.

```julia> A = [1 2; 2 3];

3-element Array{Int64,1}:
1
4
3

julia> using LinearAlgebra: dot

julia> dot(vec2matadj(A), [0, 1, 0]) == dot(A, vec2mat([0, 1, 0]))
true```

## Example usage

To solve the problem

``````minimize    dot(A, X)
subject to  norm(vec2matinv(X)) ≤ 1
X is copositive,
``````

use the following function:

```using CopositiveAnalyticCenter

function test_completely_positive(A)
# X = vec2mat(x), so dot(A, X) = dot(vec2matadj(A), x)
cc = CopositiveChecker(size(A,1))
function oracle(x::AbstractVector)
# Test if X = vec2mat(x) is copositive
val, y = testcopositive(vec2mat(x), cc)
if val >= 0
# If val ≥ 0, X = vec2mat(x) is copositive, so the oracle returns
# true.
return true
else
# Otherwise, y ≥ 0 satisfies y' X y < 0, while any copositive matrix
# lies in the halfspace
# {Z: y' Z y ≥ 0} = {vec2mat(z): dot(vec2matadj(-y*y'), z) ≤ 0}.
end
end
r = 1.
x = accp(obj, oracle, r)
return vec2mat(x)
end```

The package ships with the function `completely_positive_cut` which does the same thing as `test_completely_positive` above, but with some additional options.

Users interested in a yes-no answer to the question if `A` is completely positive can call `is_completely_positive(A)`.

### Required Packages

View all packages

### Used By Packages

No packages found.