SELF-CONCORDANT BARRIERS FOR STRUCTURED CONVEX PROBLEMS

Many of the well-known structured optimization problems one can find in the
literature are convex or can be easily convexified, and can thus be studied in
the framework of convex optimization.

The formulation of these convex problems can be either standard, using a set
of convex constraints defining a convex feasible region, or conic, defining
the feasible space as the intersection of a convex cone and an affine subspace.

In both cases, it is interesting to find self-concordant barriers for the
feasible region, since this allows the seamless derivation of interior-point
methods with polynomial complexity depending on the parameter of the barrier.

In this talk, we build on the work of den Hertog, Jarre, Roos and Terlaky and
review various convex structured problems, formulated in the standard and
conic way, and present associated self-concordant barriers. The value of the
barrier parameter and its dependence on the problem dimensions will be
emphasized, improving in some cases the currently best known values.