Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List

Full text release has been delayed at the author's request until June 02, 2025

ETD Abstract Container

Abstract Header

Analysis of Order Strategies for Alternating Algorithms in Optimization

Ntiamoah, Daniel
http://orcid.org/0000-0001-7485-4015
http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1680627356236556

Abstract Details

2023, Doctor of Philosophy (PhD), Ohio University, Mathematics (Arts and Sciences).
We investigate the choice of order of directions for Alternating Coordinate or Block Coordinate Descent algorithms. It is known that when starting the algorithm, the ordering of blocks in the first few steps can be important. We find for three blocks that it is beneficial to begin an alternating algorithm by testing different permutations of the blocks, i.e. 6 different orders for the first three steps. We study which combinations of orders are most effective and design a testing strategy that involves testing 6 permutations for 2 full passes. This strategy outperforms both random, fixed order and other testing strategies in fair comparisons. On quadratic test problems, we prove that our strategy for three directions is optimal among strategies employing two full passes and never gives bad results. For 4 search directions we find a similar search strategy for testing 2 full passes, with 24 permutations. We observe that testing orders is the most beneficial on hard (i.e. ill-conditioned) problems. As the number of directions and dimensions of the problem grows, the initial search orders still matter, but the number of steps needed for the best order to emerge grows. Further, as the number is directions grows, the number of permutations of directions grows factorially. It may become impossible to find the optimal order in an efficient way, but our observations suggest efficient strategies to find a good order for the first steps.
Todd Young (Advisor)
100 p.
Mathematics
Block Coordinate Descent; Alternating Least Squares; Tensor Approximation; Diagonal Valley.

Recommended Citations

Citations

  • Ntiamoah, D. (2023). Analysis of Order Strategies for Alternating Algorithms in Optimization [Doctoral dissertation, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1680627356236556

    APA Style (7th edition)

  • Ntiamoah, Daniel. Analysis of Order Strategies for Alternating Algorithms in Optimization. 2023. Ohio University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1680627356236556.

    MLA Style (8th edition)

  • Ntiamoah, Daniel. "Analysis of Order Strategies for Alternating Algorithms in Optimization." Doctoral dissertation, Ohio University, 2023. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1680627356236556

    Chicago Manual of Style (17th edition)

ohiou1680627356236556
© 2023, all rights reserved.
This open access ETD is published by Ohio University and OhioLINK.