Analytic center

From Glossary

Jump to: navigation, search

Given the set, LaTeX: \{x \in X : g(x) \ge 0 \}, which we assume is non-empty and compact, such that LaTeX: g is concave on LaTeX: X, with a non-empty strict interior, its analytic center is the (unique) solution to the maximum entropy problem:

\max \left\{ \sum_i \ln(g_i(x)) : x \in X, g(x) > 0 \right\}.

Note that the analytic center depends on how the set is defined -- i.e., the nature of LaTeX: g, rather than just the set, itself. For example, consider the analytic center of the box, LaTeX: [0,1]^n. One form is to have LaTeX: 2n functions as: LaTeX:  \{ x : x \ge 0,  1-x \ge 0\} . In this case, the analytic center is LaTeX: x^*_j = y^* for all LaTeX: j, where LaTeX: y^* is the solution to:

\max \left\{ \ln(y) + \ln(1 - y) : 0 < y < 1 \right\}.

Since LaTeX: y^* = 1/2, the analytical center is what we usually think of as the center of the box. However, the upper bounds could be defined by LaTeX: 1 - (x_j)^p \ge 0 for all LaTeX: j, where LaTeX: p > 1 (so LaTeX: 1 - (x_j)^p is concave). This changes the functional definition, but not the set -- it's still the unit box. The analytic center is skewed towards the corner because the defining mathematical program is:

\max \left\{ \ln(y) + \ln(1 - y^p) : 0 < y < 1 \right\}.

The solution is LaTeX: y^* = (1/(1+p))^{(1/p)}, so the analytic center approaches LaTeX: (1,1,...,1) as LaTeX: p \rightarrow \infty.

Personal tools