Entropy and Young programs: relations and self-concordance

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

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages261-276
Number of pages16
JournalCentral European Journal of Operations Research
Volume10
Issue number4
Publication statusPublished - 1 Dec 2002

Fingerprint

Concordance
Programming
Entropy
Optimization problem
Objective function
Polynomials

Keywords

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

Cite this

Boratas, Zehra ; Illés, Tibor ; Kas, Péter. / Entropy and Young programs : relations and self-concordance. In: Central European Journal of Operations Research. 2002 ; Vol. 10, No. 4. pp. 261-276.
@article{b257091aeaff48f9b6c0bf734259bb0b,
title = "Entropy and Young programs: relations and self-concordance",
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.",
keywords = "separable convex functions, entropy optimization, Young-programming, self-concordance, polynominally solvable problems",
author = "Zehra Boratas and Tibor Ill{\'e}s and P{\'e}ter Kas",
year = "2002",
month = "12",
day = "1",
language = "English",
volume = "10",
pages = "261--276",
journal = "Central European Journal of Operations Research",
issn = "1435-246X",
number = "4",

}

Boratas, Z, Illés, T & Kas, P 2002, 'Entropy and Young programs: relations and self-concordance' Central European Journal of Operations Research, vol. 10, no. 4, pp. 261-276.

Entropy and Young programs : relations and self-concordance. / Boratas, Zehra; Illés, Tibor; Kas, Péter.

In: Central European Journal of Operations Research, Vol. 10, No. 4, 01.12.2002, p. 261-276.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Entropy and Young programs

T2 - Central European Journal of Operations Research

AU - Boratas, Zehra

AU - Illés, Tibor

AU - Kas, Péter

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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.

AB - 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.

KW - separable convex functions

KW - entropy optimization

KW - Young-programming

KW - self-concordance

KW - polynominally solvable problems

M3 - Article

VL - 10

SP - 261

EP - 276

JO - Central European Journal of Operations Research

JF - Central European Journal of Operations Research

SN - 1435-246X

IS - 4

ER -