CopositiveAnalyticCenter.CopositiveCheckerType
CopositiveChecker(sd::Int)

Initialize a copositivity checker for matrices with side dimension sd. Sets up

$minimize -μ subject to Ax + μ e - λ = 0 e'x = 1 0 ≤ x_j ≤ z_j 0 ≤ λ_j ≤ (1-z_j)M_j z_j ∈ {0,1},$

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

$minimize x'Ax subject to e'x = 1 x ≥ 0.$

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.accpFunction
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.
• maxiter=50: maximum number of Newton steps.
• α=0.9: maximum step to boundary - should satisfy 0 < α < 1.
CopositiveAnalyticCenter.completely_positive_cutMethod
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_methodMethod
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.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.

CopositiveAnalyticCenter.pruneFunction
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.vec2matMethod
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

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];

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