Graduate Exam Abstract
Yajing LiuPh.D. Final
June 29, 2018, 10:00 am - 12: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 arising in
decision making with multiple actions.
Under some cases, the decision
problems have a special structure
called submodularity. We consider two
classes of optimization problems where
the objective function is submodular.
The first is submodular set
optimization, which is to choose a set
of actions to optimize a submodular set
function, and the second is submodular
string optimization, which is to choose
an ordered set of actions to optimize a
string submodular function. Our
emphasis here is on performance
bounds for the greedy strategy in
submodular optimization problems.
Specifically, for set optimization
problems, we first obtain performance
bounds for the batched greedy
strategy, where the greedy strategy is a
special case with batch size equal to 1;
then we provide improved bounds for
the greedy strategy in terms of a
parameter called curvature. For string
optimization problems, we first review
performance bounds for string
optimization problems. Then we
consider stochastic optimization
problems with a path-dependent
objective function and prove that every
path-dependent action optimization
(PDAO) scheme is a greedy strategy
so that PDAO schemes are bounded
by our results for the greedy strategy;
then we show how to apply our
framework to stochastic optimal control
problems to bound the approximate
dynamic programming algorithms.
Adviser: Edwin Chong
Co-Adviser: Ali Pezeshki
Non-ECE Member: Dan Bates, Mathematics
Member 3: J. Rockey Luo, ECE
Addional Members: N/A
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.
Y. Liu, E. K. P. Chong, and A. Pezeshki, "Extending Polymatroid Set Functions with Curvature and Bounding the Greedy Strategy," 2018 IEEE Statistical Signal Processing Workshop, to appear.
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, vol. 5, no. 1, 2018, pp. 1--18.
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, vol. 177, no. 2, 2018, pp. 535--562.
Y. Liu, A. Pezeshki, S. Roy, B. M. Notaros, T. Chen, and A. A. Maciejewski, "Why Math Matters: Demonstrating the Relevance of Mathematics in ECE Education," in 2017 ASEE, Columbus, Ohio, June 25--28, 2017.
Y. Liu, E. K. P. Chong, and A. Pezeshki, "Performance Bounds for the k-batch Greedy Strategy in Optimization Problems with Curvature," in 2016 ACC, Boston, Massachusetts, July 6--8, 2016, pp. 7177--7182.
Y. Liu, E. K. P. Chong, and A. Pezeshki, "Bounding the Greedy Strategy in Finite-Horizon String Optimization," in 54th IEEE CDC, Osaka, Japan, December 15--18, 2015, pp. 3900--3905.
Y. Liu, E. K. P. Chong, A. Pezeshki, and W. Moran, "Bounds for Approximate Dynamic Programming Based on String Optimization and Curvature," in 53rd IEEE CDC, Los Angeles, CA, December 15--17, 2014, pp. 6653--6658.
Program of Study: