NCtraceMin

description:

[opt,decom_sohs,decom_S,base,SDP_data,Z,Zg,H,Hg,decom_err] = NCtraceMin(f,S,d,params,rand) computes the lower bound for the minimum trace of f on all matrices A = D_S, where S contains polynomials, i.e. lower bound for

  inf trace (f(A))

  s.t. g(A)\succeq 0 for all g in S

This is dual to:

  sup eps

  s.t. f-eps ~ SOHS + \sum_{g\in S}\sum_i h_j^*gh_j where degree of each summand <=d

It solves the dual:

  min <L_f,H>

  H ... hankel (moment) matrix (i.e. H(u,v)=H(p,q) iff u^*v cyc. eq. p^*q

  H(1) = 1

  H >= 0

  H^g >= 0

  (H^g)_p,q = L(p^*gq), for all g in S

where H is of order |W_{d/2}| and H_g is of order |W_{d/2-deg(g)/2}| and d is input

If rand is not empty then we solve

  min <R,H>

  H ... hankel (moment) matrix (i.e. H(u,v)=H(p,q) iff u^*v cyc. eq. p^*q

  H(1) = 1

  H >= 0

  H^g >= 0

  (H^g)_p,q = L(p^*gq), for all g in S

  H_{leftupper} = rand.H0 ... rand.H0 is optimal solution of problem for smaller d (usually d-1)

where H is of order |W_{d/2}| and H_g is of order |W_{d/2-deg(g)/2}| and d is

 R...random Gram matrix

arguments:

f is an NCpoly representing a polynomial

S is a set of nc polynomails defining D_S

d is a starting degree for the hierarchy (even number)

With params.precision we can set the smallest value that is considered to be nonzero in numerical calculations; if the command is called without it, we assume the precision set with the command NCsetPrecision or the value set in NCparam.m.

params.messages is used to optionally turn on (1) and off (0) verbose output; default value is 1 (on).

params.solver sets the solver to be used for SDP and overrides the value set in the global option file NCparam.m. (currently SeDuMi, SDPA-M or SDPT3 are supported) 

params.eps sets the desired accuracy iy you are using SeDuMi as SDP solver. Setting params.eps=0 lets SeDuMi run as long as it can make progress.

params.justSDP_data == 1 means that the program ends when the SDP_data is prepared and nothing else is computed. It is optional; the default value is 0.

params.decomposition == 0 means that no SOHS decomposition over an nc ball will actually be computed. It is optional; the default value is 1.

rand  ... data for Nie randomization procedure rand.H0  - left upper corner (solution of NCtraceMin for smaller d

output:

opt ... optimal value of the SDP

decom_sohs ... sohs part of the sohs decomposition over nc ball

decom_S ... weights of polynomials g\in S

base ... is a list of monomials which appear in the SOHS decomposition over S

SDP_data ... is a structure holding all the data used in SDP solver

Z ... dual solution, that represent cycsohs

Zg.... dual solution that contains weights

H ... Hankel matrix

Hg ... shifted Hankel matrices for g in S

decom_err ... norm(nccycrep(f-opt- SOHS - \sum_{g\in S}\sum_i h_j^*gh_j))

possible usage:

NCtraceMin(f,S,d), NCtraceMin(f,S,d,params), NCtraceMin(f,S,d,params,rand)