Minimizing a KS function

Question

For convex functions $f_i, \ i \in I$, the KS function is defined as the following for any $\rho > 0$:

$$KS[\{ f_i \}_{i \in I}](x):= (1/ \rho) \ln \left[ \sum_{i \in I} \exp(\rho f_i(x)) \right].$$

It can be shown that the KS function is convex and smooth.

I am wondering, which algorithm should I be using to minimize $KS[\{ f_i \}_{i \in I}]$ over some 'easy' constraints such as convex quadratic constraints? Is there an optimization solver that would solve this problem easily? I imagine this depends on the functions $f_i$, so as a starting point, I am happy with them being convex quadratic or geometric functions.

Answer 1

I see two interesting options, the first one is a generic NLP solver which might use an interior point (IPOPT) or an SQP (List) approach. The other options is that according to my vague (and maybe wrong) understanding of conic programming that conic programming might be an interesting approach. the $\ln$ and $\exp$ terms could be model as exponential cones while convex quadratic constraints could be expressed in a power cone. As for how far your f can be modeled in that framework i can't tell, just if it is non-convex then conic programming will not work and you have to rely on a generic NLP solver, which is no longer guaranteed to find a global optimum either. In this case you have to look into global NLP solvers and best ask a separate question.

For conic problem Mosek has a solver. However i would recommend using the JuMP modeling language as that can create problems that can be called by many solvers including free solvers. For an introduction have a look into this publication.

Answer 2

Some NLP solvers may be sensitive to how the model is formulated/presented, so you may wish to try alternative formulations for each NLP solver you try. At one extreme, the "atomic" formulation is:

  minimize (1/rho)*LN( w);
   w = sum( i: u_i);
   For each i:
    { u_i = exp( v_i);
      v_i = rho*f_i(x_i);
    };

So if early in the optimization iterations the solver decides that certain of the x_i should be at a bound, the solver can avoid recomputing the associated f_i(x_i) and exp( v_i).