  In this paper, we study the predict-then-optimize problem where the output of
a machine learning prediction task is used as the input of some downstream
optimization problem, say, the objective coefficient vector of a linear
program. The problem is also known as predictive analytics or contextual linear
programming. The existing approaches largely suffer from either (i)
optimization intractability (a non-convex objective function)/statistical
inefficiency (a suboptimal generalization bound) or (ii) requiring strong
condition(s) such as no constraint or loss calibration. We develop a new
approach to the problem called \textit{maximum optimality margin} which designs
the machine learning loss function by the optimality condition of the
downstream optimization. The max-margin formulation enjoys both computational
efficiency and good theoretical properties for the learning procedure. More
importantly, our new approach only needs the observations of the optimal
solution in the training data rather than the objective function, which makes
it a new and natural approach to the inverse linear programming problem under
both contextual and context-free settings; we also analyze the proposed method
under both offline and online settings, and demonstrate its performance using
numerical experiments.
