  Non-linear, especially convex, objective functions have been extensively
studied in recent years in which approaches relies crucially on the convexity
property of cost functions. In this paper, we present primal-dual approaches
based on configuration linear programs to design competitive online algorithms
for problems with arbitrarily-grown objective. This approach is particularly
appropriate for non-linear (non-convex) objectives in online setting.
  We first present a simple greedy algorithm for a general cost-minimization
problem. The competitive ratio of the algorithm is characterized by the mean of
a notion, called smoothness, which is inspired by a similar concept in the
context of algorithmic game theory. The algorithm gives optimal (up to a
constant factor) competitive ratios while applying to different contexts such
as network routing, vector scheduling, energy-efficient scheduling and
non-convex facility location.
  Next, we consider the online $0-1$ covering problems with non-convex
objective. Building upon the resilient ideas from the primal-dual framework
with configuration LPs, we derive a competitive algorithm for these problems.
Our result generalizes the online primal-dual algorithm developed recently by
Azar et al. for convex objectives with monotone gradients to non-convex
objectives. The competitive ratio is now characterized by a new concept, called
local smoothness --- a notion inspired by the smoothness. Our algorithm yields
tight competitive ratio for the objectives such as the sum of $\ell_{k}$-norms
and gives competitive solutions for online problems of submodular minimization
and some natural non-convex minimization under covering constraints.
