We would describe the recent developments in exploring randomness in optimization algorithm design and analysis. We present two sets of results
- We establish dual concentration and convergence results of online linear programming algorithm when the problem data are generated i.i.d. from an unknown distribution and revealed sequentially over time. We also develop a new adaptive-learning algorithm which improves the previous algorithm performances by taking into account the past input data as well as the decisions/actions already made. Inspired by the findings of the online LP problem, we present a fast algorithm for approximately solving large-scale binary integer LPs. The algorithm is free of any matrix multiplication and requires only one single pass over the input data of the problem.
- We show how randomization techniques can be adapted to improve the performance of the Alternating Direction Method of Multipliers (ADMM) in both theory and practical computation. We illustrate the algorithm performance by solving a few selected difficult bench-mark optimization problems such as quadratic-assignment, max-cut, binary QP; and machine learning problems such as LASSO, Elastic-Net, SVM.
