### Abstract

Language | English |
---|---|

Pages | 261-276 |

Number of pages | 16 |

Journal | Central European Journal of Operations Research |

Volume | 10 |

Issue number | 4 |

Publication status | Published - 1 Dec 2002 |

### Fingerprint

### Keywords

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

### Cite this

*Central European Journal of Operations Research*,

*10*(4), 261-276.

}

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

Research output: Contribution to journal › Article

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 -