Interior point meta-algorithm for handling nonlinear semidefinite constraints

Description

If you need to keep your any matrix-valued function of the decision variables positive semidefinite, Nonconvex supports an interface for the barrier method for semidefinite programming, which is a meta-algorithm transforming the optimization problem to a series of nonlinear programming problems and solving them using the pre-specified sub_alg and sub_options.

Quick start

Optimizing over a multivariate gaussian distribution with artificial samples using Ipopt:

using Nonconvex, Distributions
Nonconvex.@load Semidefinite Ipopt

# Draw random multivariate gaussian samples
# Random groundtruth
mat_dim = 3
μ = randn(mat_dim)
Σ = rand(mat_dim, mat_dim)
Σ = Σ + Σ' + 2I
# Generate
n_sample = 1000
samples = rand(MvNormal(μ, Σ), n_sample)

# Define objective function
function f((x_L, x_D))
    return -loglikelihood(MvNormal(μ, decompress_symmetric(x_L, x_D)), samples)
end
# Define the matrix-valued function
function sd_constraint((x_L, x_D))
    return decompress_symmetric(x_L, x_D)
end

# Define settings
model = Model(f)
mat_x0 = rand(mat_dim, mat_dim)
mat_x0 = mat_x0 + mat_x0' + I

x0 = [mat_x0[NonconvexSemidefinite.lowertriangind(mat_x0)], diag(mat_x0)]
lbs = [fill(-Inf, length(x0[1])), zeros(length(x0[2]))]
ubs = [fill(Inf, length(x0[1])), fill(Inf, length(x0[2]))]
addvar!(model, lbs, ubs)
add_sd_constraint!(model, sd_constraint)
alg = SDPBarrierAlg(sub_alg=IpoptAlg())
options = SDPBarrierOptions(sub_options=IpoptOptions(max_iter=200), n_iter = 20)

# Optimize
result = optimize(model, alg, x0, options = options)

# Relative error norm
norm(sd_constraint(result.minimizer) - Σ) / norm(Σ)

Options

NonconvexSemidefinite.SDPBarrierOptions — Type

SDPBarrierOptions(; kwargs...)

The keyword arguments which can be specified are:

c_init: (default 1.0) initial value for the coefficient c that is multiplied by the barrier term, could be a real number or vector in the case of multiple semidefinite constraints.
c_decr: (default 0.1) decreasing rate (< 1) that multiplies the barrier term in every iteration, could be either a real number or a vector in the case of multiple semidefinite constraints.
n_iter: (default 20) number of sub-problems to solve in the barrier method.
sub_options: options for the sub-problem's solver
keep_all: (default falue) if set to true, SDPBarrierResult stores the results from all the iterations

source

Optimizer

NonconvexSemidefinite.SDPBarrierAlg — Type

SDPBarrierAlg(sub_alg)

A meta-algorithm that handles semidefinite constraints on nonlinear functions using a barrier approach. The coefficient of the barrier term is exponentially decayed and the sub-problems are solved using sub_alg. sub_alg can be any other compatible solver from Nonconvex.jl. The solver must be able to solve the sub-problem after removing the semidefinite constraints. The options to the solver should be pased to the SDPBarrierOptions struct and passed in as the options to the optimize function. Call ? SDPBarrierOptions to check all the different options that can be set.

source

Matrix interfaces

For every n*n real positive semidefinite matrix that optimization objective contains, please have two inputs x_L and x_D representing the lower-triangular and the diagonal part of it. In the function, call decompress_symmetric(x_L, x_d) to represent that matrix, which will be handled by Nonocnvex automatically

NonconvexSemidefinite.decompress_symmetric — Function

decompress_symmetric

For example: a 3*3 positive semidefinite matrix: [ a b d; b c e; d e f ] represents by: [ x_D[1] x_L[3] x_L[2]; x_L[1] x_D[2] x_L[1]; x_L[2] x_L[3] x_D[3] ]

x_L::AbstractArray: representing lower triangular part of a n*n matrix, length should be (n^2-n)÷2
x_D::AbstractArray: representing diagonal part of a n*n matrix, length should be n

source