一类组合优化问题与非凸二次规划的等价

本文研究一类著名的组合优化问题,如旅行商问题,k-着色问题和最大切割问题等。首先构造了它们的一个特殊的二次0-1规划模型(Ⅰ),然后证明了(Ⅰ)与其松驰问题(Ⅱ)在最优性意义下的等价性,从而建立了这类组合优化问题与一类特殊的非凸二次(连续)规划之间的联系,提供了一种用连续二次规划的算法求解这类组合优化问题的途径,为这类难题的算法研究开辟了一个新的方向。

非光滑规划的Lagrange鞍点定理

本文所涉及的是一个带不等式约束的非凸非可微规划。在这类非光滑规划中,本文引进了Kuhn—Tucker向量及Lagrange鞍点的概念,研究了该非光滑问题的最优解的性质,并证明了在一定条件下,Lagrange鞍点定理成立。