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

Halfspace(slope, constant)

Define a halfspace {x: dot(slope, x) ≤ constant}. Note that slope is internally normalized.

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.

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.

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.

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.

is_completely_positive(A)

Test if the matrix A is completely positive through an analytic center cutting plane method.

See also: completely_positive_cut

Compute lower bound by minimizing over the outer approximation

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

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.

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!

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

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

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