  We study the online decision making problem (ODMP) as a natural
generalization of online linear programming. In ODMP, a single decision maker
undertakes a sequence of decisions over $T$ time steps. At each time step, the
decision maker makes a locally feasible decision based on information available
up to that point. The objective is to maximize the accumulated reward while
satisfying some convex global constraints called goal constraints. The decision
made at each step results in an $m$-dimensional vector that represents the
contribution of this local decision to the goal constraints. In the online
setting, these goal constraints are soft constraints that can be violated
moderately. To handle potential nonconvexity and nonlinearity in ODMP, we
propose a Fenchel dual-based online algorithm. At each time step, the algorithm
requires solving a potentially nonconvex optimization problem over the local
feasible set and a convex optimization problem over the goal set. Under certain
stochastic input models, we show that the algorithm achieves $O(\sqrt{mT})$
goal constraint violation deterministically, and $\tilde{O}(\sqrt{mT})$ regret
in expected reward. Numerical experiments on an online knapsack problem and an
assortment optimization problem are conducted to demonstrate the potential of
our proposed online algorithm.
