论文标题
Optima在免费半决赛程序中的经验特性
Empirical properties of optima in free semidefinite programs
论文作者
论文摘要
半芬矿编程基于对线性矩阵不等式定义的线性函数的优化，即形式的不等式$$ l_a（x）= i-a_1x_1- \ dots-a_g dots-a_g x_g x_g x_g x_g x_g x_g \ succeq0。当$ x_i $是任何大小的对称矩阵时，这些不平等是有意义的矩阵的尺寸。 在本文中，我们报告了从限制于矩阵的免费频谱上优化线性函数获得的优化器的经验观察到的属性$ x_i $的固定尺寸$ n \ times n $。 我们发现的优化者始终是经典的极端要点。令人惊讶的是，在许多合理的参数范围内，超过99.9 \％也是免费的极端点。此外，活动约束的尺寸，$ \ ker（l_a（x^\ ell））$，大约是我们预期的两倍。另一个独特的模式涉及优化元组$（x_1^\ ell，\ dots，x_g^\ ell）$的降低性。 我们给出了一种算法，用于表示自由谱的元素作为自由极点的矩阵凸组合；这些表示形式满足了很少的自由点需要的界限
Semidefinite programming is based on optimization of linear functionals over convex sets defined by linear matrix inequalities, namely, inequalities of the form $$L_A(X)=I-A_1X_1-\dots-A_g X_g\succeq0.$$ Here the $X_j$ are real numbers and the set of solutions is called a spectrahedron. These inequalities make sense when the $X_i$ are symmetric matrices of any size, $n\times n$, and enter the formula though tensor product $A_i\otimes X_i$: The solution set of $L_A(X)\succeq0$ is called a free spectrahedron since it contains matrices of all sizes and the defining ``linear pencil" is ``free" of the sizes of the matrices. In this article, we report on empirically observed properties of optimizers obtained from optimizing linear functionals over free spectrahedra restricted to matrices $X_i$ of fixed size $n\times n$. The optimizers we find are always classical extreme points. Surprisingly, in many reasonable parameter ranges, over 99.9\% are also free extreme points. Moreover, the dimension of the active constraint, $\ker(L_A(X^\ell))$, is about twice what we expected. Another distinctive pattern regards reducibility of optimizing tuples $(X_1^\ell,\dots,X_g^\ell)$. We give an algorithm for representing elements of a free spectrahedron as matrix convex combinations of free extreme points; these representations satisfy a very low bound on the number of free extreme points neede
