Frank–Wolfe algorithm
ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ ನಿರ್ಬಂಧಿತ ಕನ್ವೆಕ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ಗಾಗಿ ಪುನರಾವರ್ತಿತ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಷರತ್ತುಬದ್ಧ ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನ, ಕಡಿಮೆ ಗ್ರೇಡಿಯಂಟ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಕನ್ವೆಕ್ಸ್ ಸಂಯೋಜನೆಯ ಅಲ್ಗಾರಿದಮ್ ಎಂದೂ ಕರೆಯಲ್ಪಡುವ ಈ ವಿಧಾನವನ್ನು ಮೂಲತಃ ಮಾರ್ಗರೇಟ್ ಫ್ರಾಂಕ್ ಮತ್ತು ಫಿಲಿಪ್ ವೋಲ್ಫ್ ಅವರು 1956 ರಲ್ಲಿ ಪ್ರಸ್ತಾಪಿಸಿದರು. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ, ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯದ ರೇಖೀಯ ಅಂದಾಜನ್ನು ಪರಿಗಣಿಸುತ್ತದೆ ಮತ್ತು ಈ ರೇಖೀಯ ಕಾರ್ಯದ ಮಿನಿಮೈಸರ್ ಕಡೆಗೆ ಚಲಿಸುತ್ತದೆ (ಅದೇ ಡೊಮೇನ್ನಲ್ಲಿ ತೆಗೆದುಕೊಳ್ಳಲಾಗಿದೆ). ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆ ವೆಕ್ಟರ್ ಸ್ಪೇಸ್ನಲ್ಲಿ ಕಾಂಪ್ಯಾಕ್ಟ್ ಕನ್ವೆಕ್ಸ್ ಸೆಟ್ ಆಗಿದೆ ಮತ್ತು ಇದು ಕನ್ವೆಕ್ಸ್, ಡಿಫರೆನ್ಷಿಯಬಲ್ ರಿಯಲ್-ವ್ಯಾಲ್ಯೂಡ್ ಫಂಕ್ಷನ್ ಎಂದು ಭಾವಿಸೋಣ. ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ ಮಿನಿಮೈಸ್ಗೆ ಒಳಪಟ್ಟು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಇನಿಶಿಯಲೈಸೇಶನ್ಃ ಯಾವುದೇ ಬಿಂದುವಾಗಿರಲಿ. ಹಂತ 1. ನಿರ್ದೇಶನ-ಹುಡುಕುವ ಉಪಪ್ರಶ್ನೆಃ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದನ್ನು ಕಂಡುಕೊಳ್ಳಿ (ವಿಷಯಕ್ಕೆ ಒಳಪಟ್ಟು ಕನಿಷ್ಠಗೊಳಿಸಿಃ ಮೊದಲ-ಕ್ರಮಾಂಕದ ಟೇಲರ್ ಅಂದಾಜು ನೀಡಿದ ಸಮಸ್ಯೆಯ ರೇಖಾತ್ಮಕ ಅಂದಾಜನ್ನು ಕಡಿಮೆ ಮಾಡಿ. ಹಂತ 2. ಹಂತ ಗಾತ್ರದ ನಿರ್ಣಯಃ ಹೊಂದಿಸಿ, ಅಥವಾ ಪರ್ಯಾಯವಾಗಿ ಕನಿಷ್ಠವಾಗಿರುವುದನ್ನು ಹುಡುಕಿ. ಹಂತ 3. ಅಪ್ಡೇಟ್ಃ ಲೆಟ್, ಲೆಟ್ ಮತ್ತು ಹಂತ 1 ಕ್ಕೆ ಹೋಗಿ. ಗುಣಲಕ್ಷಣಗಳು ನಿರ್ಬಂಧಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ಗಾಗಿ ಗ್ರೇಡಿಯಂಟ್ ಡಿಸೆಂಟ್ನಂತಹ ಸ್ಪರ್ಧಾತ್ಮಕ ವಿಧಾನಗಳಿಗೆ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿನ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸೆಟ್ಗೆ ಒಂದು ಪ್ರೊಜೆಕ್ಷನ್ ಹೆಜ್ಜೆ ಬೇಕಾಗಿದ್ದರೂ, ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ಗೆ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿನ ಅದೇ ಗುಂಪಿನ ಮೇಲೆ ರೇಖೀಯ ಸಮಸ್ಯೆಯ ಪರಿಹಾರ ಮಾತ್ರ ಬೇಕಾಗುತ್ತದೆ ಮತ್ತು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸೆಟ್ನಲ್ಲಿ ಉಳಿಯುತ್ತದೆ. ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ನ ಒಮ್ಮುಖವು ಸಾಮಾನ್ಯವಾಗಿ ಸಬ್ಲೀನಿಯರ್ ಆಗಿದೆಃ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯದಲ್ಲಿನ ದೋಷವು ಗರಿಷ್ಠಕ್ಕೆ k ಪುನರಾವರ್ತನೆಗಳ ನಂತರ ಇರುತ್ತದೆ, ಗ್ರೇಡಿಯಂಟ್ ಕೆಲವು ಮಾನದಂಡಗಳಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಲಿಪ್ಸಿಟ್ಜ್ ನಿರಂತರವಾಗಿರುತ್ತದೆ. ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಸರಿಸುಮಾರು ಮಾತ್ರ ಪರಿಹರಿಸಿದರೆ ಅದೇ ಒಮ್ಮುಖದ ದರವನ್ನು ಸಹ ತೋರಿಸಬಹುದು. ಅಲ್ಗಾರಿದಮ್ನ ಪುನರಾವರ್ತನೆಗಳನ್ನು ಯಾವಾಗಲೂ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಗುಂಪಿನ ತೀವ್ರ ಬಿಂದುಗಳ ವಿರಳ ಕನ್ವೆಕ್ಸ್ ಸಂಯೋಜನೆಯಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಇದು ಯಂತ್ರ ಕಲಿಕೆ ಮತ್ತು ಸಿಗ್ನಲ್ ಸಂಸ್ಕರಣಾ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ವಿರಳ ದುರಾಸೆಯ ಆಪ್ಟಿಮೈಸೇಶನ್ಗಾಗಿ ಅಲ್ಗಾರಿದಮ್ನ ಜನಪ್ರಿಯತೆಗೆ ಸಹಾಯ ಮಾಡಿದೆ, ಜೊತೆಗೆ ಉದಾಹರಣೆಗೆ ಸಾರಿಗೆ ಜಾಲಗಳಲ್ಲಿ ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಹರಿವಿನ ಆಪ್ಟಿಮೈಸೇಶನ್. ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸೆಟ್ ಅನ್ನು ರೇಖೀಯ ನಿರ್ಬಂಧಗಳ ಗುಂಪಿನಿಂದ ನೀಡಿದರೆ, ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಪರಿಹರಿಸಬೇಕಾದ ಉಪಪ್ರಶ್ನೆ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಆಗುತ್ತದೆ. ಅತ್ಯಂತ ಕೆಟ್ಟ ಒಮ್ಮುಖದ ಪ್ರಮಾಣವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಸುಧಾರಿಸಲಾಗದಿದ್ದರೂ, ಕೆಲವು ಬಲವಾದ ಕನ್ವೆಕ್ಸ್ ಸಮಸ್ಯೆಗಳಂತಹ ವಿಶೇಷ ಸಮಸ್ಯೆಯ ವರ್ಗಗಳಿಗೆ ವೇಗವಾಗಿ ಒಮ್ಮುಖವನ್ನು ಪಡೆಯಬಹುದು. ಪರಿಹಾರದ ಮೌಲ್ಯದ ಮೇಲಿನ ಕಡಿಮೆ ಮಿತಿಗಳು, ಮತ್ತು ಪ್ರೈಮಲ್-ಡ್ಯುಯಲ್ ವಿಶ್ಲೇಷಣೆ ಏಕೆಂದರೆ ಇದು ಕನ್ವೆಕ್ಸ್ ಆಗಿರುವುದರಿಂದ, ನಾವು ಹೊಂದಿರುವ ಯಾವುದೇ ಎರಡು ಬಿಂದುಗಳಿಗೆಃ ಇದು (ಅಜ್ಞಾತ) ಆಪ್ಟಿಮಲ್ ಪರಿಹಾರಕ್ಕೂ ಸಹ ಅನ್ವಯಿಸುತ್ತದೆ. ಅಂದರೆ,. ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ನಂತರದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ-th ಪುನರಾವರ್ತನೆಯ ನಿರ್ದೇಶನ-ಹುಡುಕುವ ಉಪ-ಸಮಸ್ಯೆಯ ಪರಿಹಾರವನ್ನು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯ ಸಮಯದಲ್ಲಿ ಸೆಟ್ಟಿಂಗ್ ಮಾಡುವ ಮೂಲಕ ಹೆಚ್ಚುತ್ತಿರುವ ಕಡಿಮೆ ಮಿತಿಗಳನ್ನು ನಿರ್ಧರಿಸಲು ಬಳಸಬಹುದು ಮತ್ತು ಅಜ್ಞಾತ ಆಪ್ಟಿಮಲ್ ಮೌಲ್ಯದ ಮೇಲಿನ ಅಂತಹ ಕಡಿಮೆ ಮಿತಿಗಳು ಆಚರಣೆಯಲ್ಲಿ ಮುಖ್ಯವಾಗಿವೆ ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ನಿಲ್ಲಿಸುವ ಮಾನದಂಡವಾಗಿ ಬಳಸಬಹುದು ಮತ್ತು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಅಂದಾಜು ಗುಣಮಟ್ಟದ ದಕ್ಷ ಪ್ರಮಾಣಪತ್ರವನ್ನು ನೀಡಬಹುದು. ಈ ಅನುಗುಣವಾದ ದ್ವಂದ್ವತೆಯ ಅಂತರವು, ಅಂದರೆ ಮತ್ತು ಕೆಳಗಿನ ಮಿತಿಯ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು, ಅದೇ ಒಮ್ಮುಖದ ದರದೊಂದಿಗೆ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ, ಅಂದರೆ. ಟಿಪ್ಪಣಿಗಳ ಗ್ರಂಥಸೂಚಿ (ಅವಲೋಕನ ಕಾಗದ) ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಅಲ್ಗಾರಿದಮ್ ವಿವರಣೆ. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು https://conditional-gradients.org: ಫ್ರಾಂಕ್-ವೋಲ್ಫ್ ಕ್ರಮಾವಳಿಗಳ ಒಂದು ಸಮೀಕ್ಷೆ. ಮಾರ್ಗರೇಟ್ ಫ್ರಾಂಕ್ ಅಲ್ಗಾರಿದಮ್ನ ಇತಿಹಾಸದ ಬಗ್ಗೆ ವೈಯಕ್ತಿಕ ವಿವರಣೆಯನ್ನು ನೀಡುತ್ತಾ ಪ್ರಾಕ್ಸಿಮಲ್ ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ಗಳು ಮತ್ತು ವಿಧಾನಗಳನ್ನು ನೋಡಿ.