`CopositiveAnalyticCenter.CopositiveChecker`

— Type`CopositiveChecker(sd::Int)`

Initialize a copositivity checker for matrices with side dimension `sd`

. Sets up

to check some matrix $A$ for copositivity. It can be shown^{[1]} that for suitable $M_j$ this is equivalent to

We can bound $λ$ as follows: it follows from stationarity of the Lagrangian that $λ = μe + Ax$, such that $e'x = 1$ and $λ∘x = 0$ imply $0 = μ + x'Ax$. Then $|μ| ≤ max_ij |A_ij|$ and $λ_i ≤ max_ij |A_ij| + (Ax)_i ≤ max_ij |A_ij| + max_j A_ij$.

`CopositiveAnalyticCenter.Halfspace`

— Type`Halfspace(slope, constant)`

Define a halfspace `{x: dot(slope, x) ≤ constant}`

. Note that slope is internally normalized.

`CopositiveAnalyticCenter.accp`

— Function`accp(obj::AbstractVector, oracle::Function, r::Number, x0::AbstractVector)`

Run an analytic center cutting plane method to minimize `dot(obj, x)`

such that `norm(x) ≤ r`

and `oracle(x) == true`

. `oracle(x)`

should either return `true`

or a `Halfspace`

. The starting point `x0`

does not have to be feasible. Returns a near-optimal solution `x`

at default settings.

**Arguments**

`opttol=1e-6`

: the maximum relative optimality gap at termination`maxcons=4`

: multiple of the number of variables indicating the number of constraints that are kept. The default`maxcons=4`

keeps`4n`

constraints, where`n`

is the number of variables.`verbose=true`

: display output. If the analytic center computation fails, this includes the spectrum of the matrix in the linear system that should be solved.`trackcalls=false`

: the method returns`(x, calls)`

when`trackcalls==true`

, where`calls`

is the number of calls to`oracle`

.

`CopositiveAnalyticCenter.analytic_center!`

— Method`analytic_center!(A::AbstractMatrix, b::AbstractVector, r::Number, x::AbstractVector)`

Approximate the analytic center of `{x: Ax ≤ b, norm(x) ≤ r}`

, starting from `x`

and storing the result in `x`

.

**Arguments**

`verbose=true`

: displays the spectrum of the linear system if the method fails.`grad_atol=1e-8`

: maximum norm of the Lagrangian gradient for successful termination.`maxiter=50`

: maximum number of Newton steps.`α=0.9`

: maximum step to boundary - should satisfy`0 < α < 1`

.

`CopositiveAnalyticCenter.completely_positive_cut`

— Method`completely_positive_cut(A)`

Compute a copositive matrix `X`

that approximately minimizes `dot(A,X)`

subject to the condition `norm(vec2matinv(X)) ≤ 1`

.

**Arguments**

`useaccp=true`

: uses an analytic center cutting plane method, otherwise an ellipsoid method.`verbose=true`

: display output. If the analytic center computation fails, this includes the spectrum of the matrix in the linear system that should be solved.`trackcalls=false`

: the method returns`(X, calls)`

when`trackcalls==true`

, where`calls`

is the number of calls to`oracle`

.

`CopositiveAnalyticCenter.ellipsoid_method`

— Method`ellipsoid_method(obj::AbstractVector, oracle::Function, r::Number)`

Run an ellipsoid method to minimize `dot(obj, x)`

such that `norm(x) ≤ r`

and `oracle(x) == true`

. `oracle(x)`

should either return `true`

or a `Halfspace`

.

`CopositiveAnalyticCenter.is_completely_positive`

— Method`is_completely_positive(A)`

Test if the matrix `A`

is completely positive through an analytic center cutting plane method.

See also: `completely_positive_cut`

`CopositiveAnalyticCenter.lowerbound`

— MethodCompute lower bound by minimizing over the outer approximation

`CopositiveAnalyticCenter.optimize_copositive!`

— Function`optimize_copositive!(cc::CopositiveChecker, ub=Inf)`

Solve the model in `cc`

such that $x$ and $λ$ are complementary and $z$ is binary. Refine the solution if $x$ and $λ$ are not complementary and the value of that solution is below `ub`

.

See also: `CopositiveChecker`

`CopositiveAnalyticCenter.prune`

— Function`prune(A::AbstractMatrix, b::AbstractVector, r::Number, ac::AbstractVector, oa::OuterApproximation, maxconabs::Int=Inf)`

Prune the constraints from `{x: Ax ≤ b, norm(x) ≤ r}`

that are redundant, using the set's analytic center `ac`

. Also prune the least relevant constraints such that at most `maxconabs`

constraints remain. Returns `(Ap,bp)`

, where `Ap`

and `bp`

are the pruned versions of `A`

and `b`

. Also prunes the constraints from `oa`

.

`CopositiveAnalyticCenter.testcopositive`

— Method`testcopositive(A::AbstractMatrix, cc::CopositiveChecker; maxcoef=2^32)`

Set up the CopositiveChecker `cc`

to check `A`

, and call `optimize_copositive!`

. If any coefficient exceeds `maxcoef`

, the matrix is scaled first.

See also: `CopositiveChecker`

, `optimize_copositive!`

`CopositiveAnalyticCenter.vec2mat`

— Method`vec2mat(v)`

Convert the vector `v`

to a symmetric matrix by stacking the entries.

**Examples**

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

`CopositiveAnalyticCenter.vec2matadj`

— Method`vec2matadj(M)`

Convert matrix `M`

to a vector such that `dot(vec2matadj(M), u) == dot(M, vec2mat(u))`

for any vector `u`

.

**Examples**

```
julia> M = [1 2; 2 3];
julia> vec2matadj(M)
3-element Array{Int64,1}:
1
4
3
julia> using LinearAlgebra: dot
julia> dot(vec2matadj(M), [0, 1, 0]) == dot(M, vec2mat([0, 1, 0]))
true
```

`CopositiveAnalyticCenter.vec2matinv`

— Method`vec2matinv(M)`

Convert matrix `M`

to a vector such that `vec2mat(vec2matinv(M))`

equals `M`

.

**Examples**

```
julia> M = vec2mat([1, 2, 3, 4, 5, 6])
3×3 Array{Int64,2}:
1 2 4
2 3 5
4 5 6
julia> vec2matinv(M)
6-element Array{Int64,1}:
1
2
3
4
5
6
```

- 1Wei Xia, Juan Vera, and Luis F. Zuluaga. Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques.
**INFORMS Journal on Computing**, 2018.