Give


Graduate Exam Abstract


Yajing Liu

Ph.D. Preliminary

October 24, 2017, 2:00 pm - 4:00 pm

C101B ECE Conference Room

Performance Bounds for the Greedy Strategy in Optimization Problems


Abstract: The greedy strategy is an approximation algorithm to solve optimization problems where the optimal solution is hard to obtain. We consider two classes of optimization problems. The first is set optimization, which is to choose a set of actions to optimize an objective function, and the second is string optimization, which is to choose an ordered set of actions to optimize an objective function. This presentation aims to: 1) provide performance bounds for the greedy strategy in string optimization problems under matroid constraints; 2) provide performance bounds for the batched greedy strategy in set optimization problems under matroid constraints; 3) provide performance bounds for group Nash equilibria in game theory.

Adviser: Edwin K.P. Chong
Co-Adviser: Ali Pezeshki
Non-ECE Member: Dan Bates, Mathematics
Member 3: J. Rockey Luo, ECE
Addional Members: N/A

Publications:

1: Y. Liu, E. K. P. Chong, A. Pezeshki, and W. Moran, "Bounds for approximate dynamic programming based on string optimization and curvature," in Proceedings of the 53rd IEEE Conference on Decision and Control, Los Angeles, CA, December 15--17, 2014, pp. 6653--6658.
2: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Bounding the greedy strategy in finite-horizon string optimization," in Proceedings of the 54th IEEE Conference on Decision and Control, Osaka, Japan, December 15--18, 2015, pp. 3900--3905.
3: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Performance bounds for the k-batch greedy strategy in optimization problems with curvature," in Proceedings of the 2016 American Control Conference, Boston, Massachusetts, July 6--8, 2016, pp. 7177--7182.
4: Y. Liu, Z. Zhang, E. K. P. Chong, and A. Pezeshki, "Performance bounds with curvature for batched greedy optimization," Journal of Optimization Theory and Applications, to appear.
5: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Performance bounds for Nash equilibria in submodular utility systems with user groups," Journal of Control and Decision, to appear.
6: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Improved Bounds for the Greedy Strategy in Optimization Problems with Curvatures," Discrete Applied Mathematics, under review.


Program of Study:
ECE512
ECE513
ECE514
ECE516
ECE651
ECE652
ECE656
STAT720