记得和北京12年的压轴题很类似。。

上次爆照撕逼已经很有存在感了。

1.25

我会不做。

n=4时，a=0

mark下

前排等级太高不敢说话，后排围观

看了下是nonconvex optimization。3阶或许还能做做，n阶我很怀疑能做出来

可以化成一个nonconvex的QCQP，此后尝试了各种convexify的方法，给出的都是屎一样的结果。

不会 小学没学

喔唷人。。。。

马一个

目前能想到的保证globally optimal solution的方法太复杂了，只能提供一个能收敛到kkt点的算法
先写一下优化问题，记I是3*3的全1矩阵。X是任意3*3矩阵。>=和<=号都是对矩阵的每个元素的，例如A<=B意思是a_ij<=b_ij(for any i,j)
max_X min (|[1;1;1]*X*[1,0,0]|,|[1;1;1]*X*[0,1,0]|,|[1;1;1]*X*[0,0,1]|,|[1;0;0]*X*[1,1,1]|,|[0;1;0]*X*[1,1,1]|,|[0;0;1]*X*[1,1,1]|)
s.t. -I<=X<=I
[1;1;1]*X*[1,1,1]=0
加入一个new variable t=min(|[1;1;1]*X*[1,0,0]|,|[1;1;1]*X*[0,1,0]|,|[1;1;1]*X*[0,0,1]|,|[1;0;0]*X*[1,1,1]|,|[0;1;0]*X*[1,1,1]|,|[0;0;1]*X*[1,1,1]|)
优化问题等价于
max_(X,t) t
s.t. |[1;1;1]*X*[1,0,0]|>=t,....,|[0;0;1]*X*[1,1,1]|>=t
-I<=X<=I
[1;1;1]*X*[1,1,1]=0
|[1;1;1]*X*[1,0,0]|>=t,....,|[0;0;1]*X*[1,1,1]|>=t这些约束是nonconvex的，我们可以近似转化一下，例如对于第一个约束|[1;1;1]*X*[1,0,0]|>=t
定义f1(X)=|[1;1;1]*X*[1,0,0]|
f1(X)关于X是convex的，但是f1(X)不是处处可微的，所以要引入subgradient
f1(X)>=f1(X0)+trace(g1(X0)'*(X-X0)) (g1(X0)是f1在X0处的subgradient，如果X0处可微，subgradient就是gradient)
然后就成找到原优化问题的一个可以解的上届
max_(X,t) t
s.t. f1(X0)+trace(g1(X0)'*(X-X0))>=t,....,f6(X0)+trace(g6(X0)'*(X-X0))>=t
-I<=X<=I
[1;1;1]*X*[1,1,1]=0
这是一个convex的问题，可以保证很容易解出来
然后假设解出来的最优解是X_opt,把X_opt代入X0得到一个更加tight的上届
max_(X,t) t
s.t. f1(X_opt)+trace(g1(X_opt)'*(X-X_opt))>=t,....,f6(X_opt)+trace(g6(X_opt)'*(X-X_opt))>=t
-I<=X<=I
[1;1;1]*X*[1,1,1]=0
然后以此类推，把每次优化问题的最优解当成下一次优化问题中的X0，直到收敛

n=4时，a=4/3
Objective value: 1.333333
Variable Value Reduced Cost
A 1.333333 0.000000
X11 -0.8412698 0.000000
X12 -0.8412698 0.000000
X13 -0.6507937 0.000000
X14 1.000000 0.000000
X21 -0.8095238 0.000000
X22 -0.8412698 0.000000
X23 -0.6825397 0.000000
X24 1.000000 0.000000
X31 -0.6825397 0.000000
X32 -0.6507937 0.000000
X33 -1.000000 0.000000
X34 1.000000 0.000000
X41 1.000000 0.000000
X42 1.000000 0.000000
X43 1.000000 0.000000
X44 1.000000 0.000000