nonsmooth optimization with applications in network design and machine learning
Open Access
- Author:
- Liu, Hongcheng
- Graduate Program:
- Industrial Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- None
- Committee Members:
- Tao Yao, Committee Chair/Co-Chair
Terry Lee Friesz, Committee Chair/Co-Chair
Necdet S Aybat, Committee Member
Runze Li, Committee Member - Keywords:
- Nonsmooth optimization
machine learning
network design
folded concave penalty
sparse recovery - Abstract:
- This dissertation concerns three specific optimization problems in applications to traffic network design and machine leaning. The formulations of these problems are all featured with nonsmoothness and potential nonconvexity in the objective and/or constraint functions. We first study a mathematical program with equilibrium constraints (MPEC) that stems from equilibrium network design problems in traffic systems, such as the optimal path-based congestion tolling and the designing of tradable credits. An MPEC is known to be computationally challenging due to the presence of a semi-infinite constraint, which renders the program both nonconvex and nonsmooth in general. This dissertation considers an even less desirable application scenario where the equilibrium constraint entails a non-closed-form operator. To address this computational issue, we propose a finite sampling approximation with a tunable bound on the approximation error. Under some regularity conditions, the approximation allows the MPEC to be solvable with any gradient-based local schemes to achieve an approximate first-order KKT solution with bounded infeasiblity. Such an approach is applied to the MPEC formulation of a congestion toll pricing problem and is shown to outperform other counterpart algorithms. The second problem concerns system optimal real-time signal control for a traffic network where the incoming traffic flow is uncertain and the available knowledge on the underlying distribution is limited. Such a problem is formulated as a distributionally robust optimization (DRO) model, which determines an optimal decision rule for traffic signal timing that is effective even when the underlying distribution is the most adversarial to the designer. Such a decision rule can be implemented as a signal strategy responsive to real-time traffic information. The DRO model is intrinsically nonsmooth. To facilitate computation, we employ a sampling-based approximation to reduce the DRO model, which originally involves binary variables, into a mixed integer linear program. The efficacy of the approximation is theoretically guaranteed and numerically verified. We further test the proposed signal control procedure in the simulation of a realistic traffic network in Glasgow, and demonstrate its potential in on-line operation on realistic networks. For the third problem, we focus on folded concave penalized sparse linear regression (FCSLR), an important regression model aimed for high-dimensional learning problems. Due to the presence of a folded concave penalty, the problem formulation involves both nonsmoothness and nonconvexity. Therefore, computing a global solution is challenging. In this dissertation, we show that for the regression problems with random design matrices, some easily computable local solutions satisfying a second order necessary condition (SONC) entail good estimation accuracy with a probability guarantee when the sample size is sufficient. To compute SONC solutions with different levels of accuracy, we discuss two different techniques: (1) a novel potential reduction method (PR); and (2) a new mixed integer linear programming-based global optimization (MIPGO) scheme. Numerical comparison indicates an improved solution quality by PR and MIPGO in comparison with the state-of-the-art benchmark algorithm, the local linear approximation.