优化是一门应用相当广泛的学科,其方法已普遍用于科学、工程与经济等重要领域,成为政府部门、科研机构和产业部门进行科学决策的有力工具。非凸优化问题的有效解法与复杂性分析研究是重要的研究方向。复杂性理论结果对算法的使用和发展具有一定的启示作用。复杂性理论领域一方面设计和分析有效算法,另一方面从两个对立的角度来看待算法问题。一个有效的算法,可直接用于解决问题,并且其本身就是问题的有效的可解性的证明。相反,复杂性理论的目标是证明难的问题不能用有限的资源量来解决。现有的大多数关于约束优化的算法都只能求出局部极小点（或稳定点）,而诸多的实际问题都要求得到全局极小点。我们借鉴全局优化中的某些方法（填充函数法、打洞函数法）,融水平值下降思想,对一类非凸优化问题的全局算法进行了研究。我们知道,用组合方法研究凸规划时发现,无需增加其它条件（与解存在性条件相同）便可得到相应算法的大范围收敛性；而且在通常假设条件下（自和谐条件）,通过分段分析技巧,克服了组合同伦路径不单调所带来的困难,得到了与其它内点法类似的多项式复杂度估计,同时也相应地对线性互补问题与非线性互补问题的复杂性估计也已得到了类似成果。但对非凸情形该算法的复杂度还无任何结果,对此进行研究十分必要。本文首先研究了可行域满足法锥条件的非凸规划组合同伦算法的复杂性,在平凡的条件下（假设目标函数在一个大的范围内有界）,证明了解非凸规划的组合同伦算法的复杂性。其次,利用了多项式第二判别矩阵,基于水平值下降思想,构建了多项式函数极小化问题的全局优化算法,数值实验表明新的算法十分有效。