● 摘要
在非光滑多体系统动力学及区间矩阵等问题的研究中,会遇到含变量绝对值的方程组, 记为Ax-B|x|=b, 其中我们称之为绝对值方程问题. Mangasarian已经证明绝对值方程是NP-难问题. 关于其在理论方面的研究, 最早的讨论是Rohn(2004)通过区间矩阵理论得到的一个择一定理, 此外就是Mangasarian 和Meyer 给出的$B$为单位矩阵时,绝对值方程解的存在性结论.而与算法有关的唯一工作则是Mangasarian提出的凹极化小算法. 本文并没有直接研究绝对值方程,而是试探性地从一些与之密切相关的数学问题出发来间接地对其进行研究,在研究中我们发现其等价于一个水平线性互补问题,通过对该水平线性互补问题,并利用已有结论得到了绝对值方程解的唯一性结论. 同时,根据Mehrotra关于线性规划的原-对偶内点法,设计了求解绝对值方程的内点算法; 此外,在研究中我们还发现在绝对值方程有解的情况下,可以通过一个不定二次规划问题来求解, 由此我们根据Fletcher以及Bunch和Kaufman关于不定二次规划的算法,同时针对绝对值方程在转化为二次规划时,其海森矩阵的高度稀疏性与不等式约束为简单非负约束这些特性,设计了两个求解其的不定二次规划法.数值实验说明了这些算法的可行性与有效性.
相关内容
相关标签