Entropy and Young programs: relations and self-concordance

Zehra Boratas, Tibor Illés, Péter Kas

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper we study a special class of linearly constrained problems with convex separable objective functions usually called entropy programming problems. Den Hertog et. al (1995) proved that the logarithmic barrier function for the extended entropy programming problems is self-concordant, hence polynomial complexity for this class of problems can be derived from the theory of Nesterov and Nemirovsky (1994) on self-concordant functions. Furthermore, it is easy to show that the entropy optimization problem, as it is defined in the paper of Potra and Ye (1993), forms a subclass of the class of extended entropy programming problems. Another related class of problems called Young-programming, was introduced by Kas et. al (1999). The intersection of extended entropy programming and Young-programming contains most of the classical entropy programming problems, thus those Young-programs are polynomially solvable. However, it is shown in this paper that the symmetric difference of these problem classes is not empty (in set theoretical sense), and the structure of Young-programs enables us to present a Young-program whose logarithmic barrier function is not self-concordant and is not known to be polynomially solvable.
Original languageEnglish
Pages (from-to)261-276
Number of pages16
JournalCentral European Journal of Operations Research
Volume10
Issue number4
Publication statusPublished - 1 Dec 2002

Keywords

  • separable convex functions
  • entropy optimization
  • Young-programming
  • self-concordance
  • polynominally solvable problems

Fingerprint

Dive into the research topics of 'Entropy and Young programs: relations and self-concordance'. Together they form a unique fingerprint.

Cite this