Subgradient method
ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ಕನ್ವೆಕ್ಸ್ ಮಿನಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಪುನರಾವರ್ತಿತ ವಿಧಾನಗಳಾಗಿವೆ. ಮೂಲತಃ 1960 ಮತ್ತು 1970 ರ ದಶಕಗಳಲ್ಲಿ ನೌಮ್ ಝಡ್. ಶೋರ್ ಮತ್ತು ಇತರರು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದ, ಭೇದಿಸಲಾಗದ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಕ್ಕೂ ಸಹ ಅನ್ವಯಿಸಿದಾಗ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ಒಮ್ಮುಖವಾಗಿರುತ್ತವೆ. ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯವು ಭೇದಾತ್ಮಕವಾಗಿದ್ದಾಗ, ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗಳಿಗೆ ಉಪ-ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ಕಡಿದಾದ ಇಳಿಯುವಿಕೆಯ ವಿಧಾನದಂತೆಯೇ ಅದೇ ಹುಡುಕಾಟ ದಿಕ್ಕನ್ನು ಬಳಸುತ್ತವೆ. ಎರಡು ಬಾರಿ ನಿರಂತರವಾಗಿ ಭೇದಿಸಬಹುದಾದ ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯಗಳನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಅನ್ವಯಿಸಿದಾಗ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ನ್ಯೂಟನ್ನ ವಿಧಾನಕ್ಕಿಂತ ನಿಧಾನವಾಗಿರುತ್ತವೆ. ಆದಾಗ್ಯೂ, ನ್ಯೂಟನ್ನ ವಿಧಾನವು ಭೇದಿಸಲಾಗದ ಕಿನ್ಕ್ಗಳನ್ನು ಹೊಂದಿರುವ ಸಮಸ್ಯೆಗಳ ಮೇಲೆ ಒಮ್ಮುಖವಾಗಲು ವಿಫಲವಾಗಿದೆ. ಇತ್ತೀಚಿನ ವರ್ಷಗಳಲ್ಲಿ, ಕನ್ವೆಕ್ಸ್ ಮಿನಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಕೆಲವು ಆಂತರಿಕ-ಬಿಂದು ವಿಧಾನಗಳನ್ನು ಸೂಚಿಸಲಾಗಿದೆ, ಆದರೆ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಪ್ರೊಜೆಕ್ಷನ್ ವಿಧಾನಗಳು ಮತ್ತು ಸಂಬಂಧಿತ ಬಂಡಲ್ ವಿಧಾನಗಳು ಸ್ಪರ್ಧಾತ್ಮಕವಾಗಿ ಉಳಿದಿವೆ. ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಆಯಾಮಗಳನ್ನು ಹೊಂದಿರುವ ಕನ್ವೆಕ್ಸ್ ಕನಿಷ್ಠೀಕರಣ ಸಮಸ್ಯೆಗಳಿಗೆ, ಸಬ್ಗ್ರೇಡಿಯಂಟ್-ಪ್ರೊಜೆಕ್ಷನ್ ವಿಧಾನಗಳು ಸೂಕ್ತವಾಗಿವೆ, ಏಕೆಂದರೆ ಅವುಗಳಿಗೆ ಕಡಿಮೆ ಶೇಖರಣೆಯ ಅಗತ್ಯವಿರುತ್ತದೆ. ವಿಭಜನೆ ತಂತ್ರಗಳೊಂದಿಗೆ ದೊಡ್ಡ ಪ್ರಮಾಣದ ಸಮಸ್ಯೆಗಳಿಗೆ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಪ್ರೊಜೆಕ್ಷನ್ ವಿಧಾನಗಳನ್ನು ಹೆಚ್ಚಾಗಿ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ. ಅಂತಹ ವಿಭಜನೆಯ ವಿಧಾನಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಒಂದು ಸಮಸ್ಯೆಗೆ ಸರಳವಾದ ವಿತರಣಾ ವಿಧಾನವನ್ನು ಅನುಮತಿಸುತ್ತವೆ. ಕ್ಲಾಸಿಕಲ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ನಿಯಮಗಳು ಡೊಮೇನ್ನೊಂದಿಗೆ ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯವಾಗಿರಲಿ. ಒಂದು ಶಾಸ್ತ್ರೀಯ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನವು ಪುನರಾವರ್ತನೆಯಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಅದು ಅಟ್ನ ಯಾವುದೇ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು ಅದರ ಪುನರಾವರ್ತನೆಯಾಗಿದೆ. ಡಿಫರೆನ್ಷಿಯೇಬಲ್ ಆಗಿದ್ದರೆ, ಅದರ ಏಕೈಕ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಗ್ರೇಡಿಯಂಟ್ ವೆಕ್ಟರ್ ಆಗಿದೆ. ಇದು ಏಟ್ಗೆ ಇಳಿಯುವ ದಿಕ್ಕಲ್ಲ ಎಂದು ಸಂಭವಿಸಬಹುದು. ಆದ್ದರಿಂದ ನಾವು ಇಲ್ಲಿಯವರೆಗೆ ಕಂಡುಬಂದ ಅತ್ಯಂತ ಕಡಿಮೆ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯ ಮೌಲ್ಯವನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡುವ ಪಟ್ಟಿಯನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ, ಅಂದರೆ. ಹಂತ-ಗಾತ್ರದ ನಿಯಮಗಳು ಉಪವಿಭಾಗದ ವಿಧಾನಗಳಿಂದ ವಿವಿಧ ರೀತಿಯ ಹಂತ-ಗಾತ್ರದ ನಿಯಮಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಲೇಖನವು ಐದು ಶಾಸ್ತ್ರೀಯ ಹಂತ-ಗಾತ್ರದ ನಿಯಮಗಳನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತದೆ, ಇದಕ್ಕಾಗಿ ಒಮ್ಮುಖದ ಪುರಾವೆಗಳು ತಿಳಿದಿವೆಃ ಸ್ಥಿರ ಹಂತದ ಗಾತ್ರ, ಸ್ಥಿರ ಹಂತದ ಉದ್ದ, ಇದು ಚೌಕಾಕಾರದ ಸಾರಾಂಶವನ್ನು ನೀಡುತ್ತದೆ ಆದರೆ ಸಾರಾಂಶವಲ್ಲದ ಹಂತದ ಗಾತ್ರವನ್ನು ನೀಡುತ್ತದೆ, ಅಂದರೆ. ಯಾವುದೇ ಹಂತದ ಗಾತ್ರಗಳು ಅಪೂರ್ಣವಾಗಿ ಕಡಿಮೆಯಾಗುವುದನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತವೆ, ಅಂದರೆ. ಯಾವುದೇ ಹಂತದ ಗಾತ್ರಗಳು ಅಪೂರ್ಣವಾಗಿ ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಹಂತದ ಉದ್ದಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತವೆ, ಅಂದರೆ. ಎಲ್ಲಾ ಐದು ನಿಯಮಗಳಿಗೆ, ವಿಧಾನವನ್ನು ಪುನರಾವರ್ತಿಸುವ ಮೊದಲು ಹಂತ-ಗಾತ್ರಗಳನ್ನು "ಆಫ್-ಲೈನ್" ಎಂದು ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ; ಹಂತ-ಗಾತ್ರಗಳು ಹಿಂದಿನ ಪುನರಾವರ್ತನೆಗಳನ್ನು ಅವಲಂಬಿಸುವುದಿಲ್ಲ. ಉಪವಿಭಾಗ ವಿಧಾನಗಳ ಈ "ಆಫ್-ಲೈನ್" ಗುಣಲಕ್ಷಣವು ಭೇದಾತ್ಮಕ ಕಾರ್ಯಗಳಿಗಾಗಿ ಅವರೋಹಣ ವಿಧಾನಗಳಿಗೆ ಬಳಸುವ "ಆನ್-ಲೈನ್" ಹಂತ-ಗಾತ್ರದ ನಿಯಮಗಳಿಗಿಂತ ಭಿನ್ನವಾಗಿದೆಃ ಭೇದಾತ್ಮಕ ಕಾರ್ಯಗಳನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಅನೇಕ ವಿಧಾನಗಳು ಒಮ್ಮುಖಕ್ಕೆ ವೋಲ್ಫ್ನ ಸಾಕಷ್ಟು ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸುತ್ತವೆ, ಅಲ್ಲಿ ಹಂತ-ಗಾತ್ರಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಪ್ರಸ್ತುತ ಬಿಂದು ಮತ್ತು ಪ್ರಸ್ತುತ ಹುಡುಕಾಟ-ದಿಕ್ಕನ್ನು ಅವಲಂಬಿಸಿರುತ್ತವೆ. ಬರ್ಟ್ಸೆಕಾಸ್ ಮತ್ತು ಬರ್ಟ್ಸೆಕಾಸ್, ನೆಡಿಕ್ ಮತ್ತು ಓಝ್ಡಾಗ್ಲರ್ ಅವರ ಪುಸ್ತಕಗಳಲ್ಲಿ ಹೆಚ್ಚುತ್ತಿರುವ ಆವೃತ್ತಿಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳ ಹಂತದ ನಿಯಮಗಳ ಬಗ್ಗೆ ವ್ಯಾಪಕವಾದ ಚರ್ಚೆಯನ್ನು ನೀಡಲಾಗಿದೆ. ಯುಕ್ಲಿಡಿಯನ್ ಮಾನದಂಡವು ಒಂದಕ್ಕೆ ಸಮನಾಗಿರುವ ಸ್ಥಿರ ಹಂತ-ಉದ್ದ ಮತ್ತು ಸ್ಕೇಲ್ಡ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ಗಳಿಗೆ, ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನವು ಕನಿಷ್ಠ ಮೌಲ್ಯಕ್ಕೆ ಅನಿಯಂತ್ರಿತವಾಗಿ ಹತ್ತಿರದ ಅಂದಾಜುಗೆ ಒಮ್ಮುಖವಾಗುತ್ತದೆ, ಅಂದರೆ ಶೋರ್ನ ಪರಿಣಾಮವಾಗಿ. ಈ ಶಾಸ್ತ್ರೀಯ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನಗಳು ಕಳಪೆ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಹೊಂದಿವೆ ಮತ್ತು ಸಾಮಾನ್ಯ ಬಳಕೆಗೆ ಇನ್ನು ಮುಂದೆ ಶಿಫಾರಸು ಮಾಡಲಾಗುವುದಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಅವುಗಳನ್ನು ಇನ್ನೂ ವಿಶೇಷ ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಅವು ಸರಳವಾಗಿರುತ್ತವೆ ಮತ್ತು ಕೈಯಲ್ಲಿರುವ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ರಚನೆಯ ಲಾಭವನ್ನು ಪಡೆಯಲು ಅವುಗಳನ್ನು ಸುಲಭವಾಗಿ ಅಳವಡಿಸಿಕೊಳ್ಳಬಹುದು. ಸಬ್ಗ್ರೇಡಿಯಂಟ್-ಪ್ರೊಜೆಕ್ಷನ್ ಮತ್ತು ಬಂಡಲ್ ವಿಧಾನಗಳು 1970ರ ದಶಕದಲ್ಲಿ, ಕ್ಲೌಡ್ ಲೆಮೆರೆಚಲ್ ಮತ್ತು ಫಿಲ್ ವೋಲ್ಫ್ ಅವರು ಕನ್ವೆಕ್ಸ್ ಕನಿಷ್ಠೀಕರಣದ ಸಮಸ್ಯೆಗಳಿಗೆ ಅವರೋಹಣದ "ಬಂಡಲ್ ವಿಧಾನಗಳನ್ನು" ಪ್ರಸ್ತಾಪಿಸಿದರು. "ಬಂಡಲ್ ವಿಧಾನಗಳು" ಎಂಬ ಪದದ ಅರ್ಥವು ಆ ಸಮಯದಿಂದ ಗಮನಾರ್ಹವಾಗಿ ಬದಲಾಗಿದೆ. ಆಧುನಿಕ ಆವೃತ್ತಿಗಳು ಮತ್ತು ಸಂಪೂರ್ಣ ಒಮ್ಮುಖದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಕಿವೀಲ್ ಒದಗಿಸಿದ್ದಾರೆ. ಸಮಕಾಲೀನ ಬಂಡಲ್-ವಿಧಾನಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಹಂತ-ಗಾತ್ರಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡಲು "ಮಟ್ಟದ ನಿಯಂತ್ರಣ" ನಿಯಮಗಳನ್ನು ಬಳಸುತ್ತವೆ, ಬೋರಿಸ್ ಟಿ. ಪೊಲ್ಯಾಕ್ (1969) ಅವರ "ಸಬ್ಗ್ರೇಡಿಯಂಟ್-ಪ್ರೊಜೆಕ್ಷನ್" ವಿಧಾನದಿಂದ ತಂತ್ರಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಸಬ್ಗ್ರೇಡಿಯಂಟ್-ಪ್ರೊಜೆಕ್ಷನ್ ವಿಧಾನಗಳಿಗಿಂತ ಬಂಡಲ್ ವಿಧಾನಗಳು ಕಡಿಮೆ ಪ್ರಯೋಜನವನ್ನು ನೀಡುವ ಸಮಸ್ಯೆಗಳಿವೆ. ನಿರ್ಬಂಧಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಪ್ರೊಜೆಕ್ಟೆಡ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನದ ಒಂದು ವಿಸ್ತರಣೆಯು ಪ್ರೊಜೆಕ್ಟೆಡ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನವಾಗಿದೆ, ಇದು ಕನ್ವೆಕ್ಸ್ ಸೆಟ್ ಇರುವ ಸ್ಥಳಕ್ಕೆ ಒಳಪಟ್ಟು ನಿರ್ಬಂಧಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ. ಪ್ರೊಜೆಕ್ಟೆಡ್ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ವಿಧಾನವು ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸುತ್ತದೆ, ಅಲ್ಲಿ ಪ್ರೊಜೆಕ್ಷನ್ ಆನ್ ಆಗಿದೆ ಮತ್ತು ಸಾಮಾನ್ಯ ನಿರ್ಬಂಧಗಳಲ್ಲಿ ಯಾವುದೇ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಆಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಹಂತದ ಗಾತ್ರವಿರುವ ಅನಿಯಂತ್ರಿತ ಪ್ರಕರಣದಂತೆಯೇ ಅದೇ ರೂಪವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಇದು ವಸ್ತುನಿಷ್ಠತೆಯ ಉಪವಿಭಾಗವಾಗಿದೆ ಅಥವಾ ಟೇಕ್ ನಲ್ಲಿ ನಿರ್ಬಂಧದ ಕಾರ್ಯಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಪ್ರಸ್ತುತ ಬಿಂದುವು ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ ವಸ್ತುನಿಷ್ಠ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಅನ್ನು ಬಳಸುತ್ತದೆ; ಪ್ರಸ್ತುತ ಬಿಂದುವು ಅಸಾಧ್ಯವಾಗಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ ಯಾವುದೇ ಉಲ್ಲಂಘಿಸಿದ ನಿರ್ಬಂಧದ ಸಬ್ಗ್ರೇಡಿಯಂಟ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಸ್ಟ್ಯಾನ್ಫೋರ್ಡ್ನ ಕನ್ವೆಕ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕೋರ್ಸ್ ಅನುಕ್ರಮವಾದ ಬಾಹ್ಯ ಕೊಂಡಿಗಳಾದ EE364A ಮತ್ತು EE364B ಅನ್ನು ಮತ್ತಷ್ಟು ಓದುವ ಉಲ್ಲೇಖಗಳು. ಆಪ್ಟಿಮೈಸೇಶನ್ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ವಿಧಾನಗಳು ಕನ್ವೆಕ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್