Entropy and Young programs: relations and self-concordance

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.