符号单项式凸性识别被证明为强NP难:三条可解性路径同时失效
该工作研究符号单项式(实指数广义单项式的有限和)的凸性识别问题,证明判断一个符号单项式是否在原变量下凸、是否在对数变量变换后凸、以及在其为正时是否在再取对数值后凸(即纪律化几何规划所依赖的结构)这三种形式,在紧致域上和全局范围内均为强NP难,证明从多项式凸性的间隙-承诺变体出发,构造了在相应对数变换下保持曲率间隙的多项式到符号单项式的归约。
该工作研究符号单项式(实指数广义单项式的有限和)的凸性识别问题,证明判断一个符号单项式是否在原变量下凸、是否在对数变量变换后凸、以及在其为正时是否在再取对数值后凸(即纪律化几何规划所依赖的结构)这三种形式,在紧致域上和全局范围内均为强NP难,证明从多项式凸性的间隙-承诺变体出发,构造了在相应对数变换下保持曲率间隙的多项式到符号单项式的归约。
已读完全部报道