English

运筹学学报 >

2017 , Vol. 21 >Issue 2: 39 - 45

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.02.005

运筹学

离散优化与连续优化的复杂性概念

展开
  • 1. 清华大学数学科学系, 北京 100084

收稿日期: 2017-04-04

  网络出版日期: 2017-06-15

基金资助

国家自然科学基金(No. 11571029)

收起

Complexity concepts for combinatorial and continuous optimization problems

Expand
  • 1. Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Received date: 2017-04-04

  Online published: 2017-06-15

Fold

摘要

问题的复杂性概念起源于离散的图灵计算机理论的研究, 在离散优化问题的研究中被广泛的接受. 近期连续优化领域的很多文章中提及NP难这个概念. 从而来对比介绍离散优化和连续优化研究中这两个概念的差异.

关键词： 复杂性概念; 离散优化; 连续优化

本文引用格式

邢文训 . 离散优化与连续优化的复杂性概念[J]. 运筹学学报, 2017 , 21(2) : 39 -45 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.02.005

Abstract

 Complexity concepts oriented from the theoretical Turing machine are widely accepted in study of combinatorial optimization problems. The polynomially computable and NP-hard concepts are frequently used in recent papers on continuous optimization problems. This paper presents a very brief introduction to show their relationship and difference used in the two fields.

Key words： complexity concepts; combinatorial optimization; continuous optimization

参考文献

[1] Cook S A. The complexity of theorem-proving procedures[C]//ACM Symposium on Theory of Computing,  Ohio: Shaker Heights, 1971, 151-158.
[2] Karmarkar N. A new polynomial-time algorithm for linear programming [J]. Combinatorica, 1984, 4: 373-395.
[3] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. San Francisco: W. H. Freeman and Company, 1979.
[4] Blum L, Shub M, Smale S. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines [J]. Bulletin of the American Mathematical Society, 1989, 21(1): 1-46.
[5] Nemirovski A S, Yudin D B. Problem Complexity and Method Efficiency in Optimization [M]. New York: Wiley-Interscience,  1983.
[6] Vavasis S A. Nonlinear Optimization: Complexity Issues [M]. New York: Oxford University Press, 1991.
[7] Frenk H, Roos K, Terlaky T, et al. High Performance Optimization [M]. New York: Springer, 1999.
[8] 方述诚, 邢文训. 线性锥优化 [M]. 北京: 科学出版社, 2013.
[9] Pardalos P M, Vavasis S A. Quadratic programming with one negative eigenvalue is NP-hard [J]. Journal of Global Optimization, 1991, 1(1): 15-22.
[10] 邢文训, 谢金星. 现代优化计算方法 [M]. 北京: 清华大学出版社, 2005.
Options
文章导航

/

〈 〉