Minty condition

新算法以多项式时间解决了变分不等式

研究人员开发了一种新的多项式时间算法，用于解决具有 Minty 条件的变分不等式，这个问题在历史上一直具有计算挑战性。该算法利用了一种新颖的椭球方法变体，通过实现复杂度与维度和所需精度倒数的对数成多项式增长，显著优于先前的方法。这项工作还表明，确定 Minty 条件解的存在性是 coNP 完全的，而寻找解或证明不可行性的析取是多项式时间可解的。这些发现直接应用于计算多玩家和谐博弈和一般和凹博弈的纳什均衡。