Sum-of-squares optimization
ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಪ್ರೋಗ್ರಾಂ ಒಂದು ರೇಖೀಯ ವೆಚ್ಚದ ಕಾರ್ಯ ಮತ್ತು ನಿರ್ಧಾರದ ಅಸ್ಥಿರಗಳ ಮೇಲೆ ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ನಿರ್ಬಂಧವನ್ನು ಹೊಂದಿರುವ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಈ ನಿರ್ಬಂಧಗಳು ಕೆಲವು ಬಹುಪದಿಗಳಲ್ಲಿ ನಿರ್ಧಾರದ ಅಸ್ಥಿರಗಳನ್ನು ಗುಣಾಂಕಗಳಾಗಿ ಬಳಸಿದಾಗ, ಆ ಬಹುಪದಿಗಳು ಬಹುಪದ SOS ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿರಬೇಕು. ಒಳಗೊಂಡಿರುವ ಬಹುಪದಗಳ ಗರಿಷ್ಠ ಮಟ್ಟವನ್ನು ನಿಗದಿಪಡಿಸುವಾಗ, ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅನ್ನು ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ನಲ್ಲಿ ಸಡಿಲಿಕೆಗಳ ಲಾಸ್ಸೆರ್ ಶ್ರೇಣಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ನಿಯಂತ್ರಣ ಸಿದ್ಧಾಂತ (ನಿರ್ದಿಷ್ಟವಾಗಿ, ಬಹುಪದೀಯ ವಾಹಕ ಕ್ಷೇತ್ರಗಳಿಂದ ವಿವರಿಸಲಾದ ಕ್ರಿಯಾತ್ಮಕ ವ್ಯವಸ್ಥೆಗಳಿಗಾಗಿ ಬಹುಪದೀಯ ಲಿಯಾಪುನೋವ್ ಕಾರ್ಯಗಳನ್ನು ಹುಡುಕಲು), ಅಂಕಿಅಂಶಗಳು, ಹಣಕಾಸು ಮತ್ತು ಯಂತ್ರ ಕಲಿಕೆ ಸೇರಿದಂತೆ ವಿವಿಧ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ತಂತ್ರಗಳನ್ನು ಅನ್ವಯಿಸಲಾಗಿದೆ. "ಸ್ಕ್ವೇರ್ಸ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮೊತ್ತವನ್ನು ಬಳಸಿಕೊಂಡು ನಿಯಂತ್ರಣ ಲಿಯಾಪುನೋವ್ ಕಾರ್ಯಗಳಿಗಾಗಿ ಹುಡುಕಲಾಗುತ್ತಿದೆ". ರಲ್ಲಿಃ ಅಲೆರ್ಟನ್ ಕಾನ್ಫ್. ಕಾಮ್, ಕಂಟ್ರೋಲ್ ಮತ್ತು ಕಂಪ್ಯೂಟಿಂಗ್ನಲ್ಲಿ. ಪಿಪಿ. 210-219. </ರಿಫರ್> ಎ. ಚಕ್ರವರ್ತಿ, ಪಿ. ಸೀಲರ್, ಮತ್ತು ಜಿ. ಬಾಲಾಸ್, "ಫಾಲಿಂಗ್-ಲೀಫ್ ಮೋಡ್ಗೆ ಎಫ್/ಎ-18 ಫ್ಲೈಟ್ ಕಂಟ್ರೋಲರ್ಗಳ ಸೆಸೆಪ್ಟಿಬಿಲಿಟಿಃ ನಾನ್ ಲೀನಿಯರ್ ಅನಾಲಿಸಿಸ್", ಎಐಎಎ ಜರ್ನಲ್ ಆಫ್ ಗೈಡೆನ್ಸ್, ಕಂಟ್ರೋಲ್, ಅಂಡ್ ಡೈನಾಮಿಕ್ಸ್, ಸಂಪುಟ. 34ರಷ್ಟಿದೆ. 1 (2011), ಪು. 73-85. ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆ, ವೆಕ್ಟರ್ ಮತ್ತು ಬಹುಪದಿಗಳನ್ನು ನೀಡಿದರೆ, ಒಂದು ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಹೀಗೆ ಬರೆಯಲಾಗುತ್ತದೆಃ ಇಲ್ಲಿ "ಎಸ್. ಓ. ಎಸ್". ಎಂಬುದು ಸಮ್-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ (ಎಸ್. ಓ. ಎಸ್) ಬಹುಪದಿಗಳ ವರ್ಗವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಪ್ರಮಾಣಗಳು ನಿರ್ಧಾರದ ಅಸ್ಥಿರಗಳಾಗಿವೆ. ಎಸ್. ಓ. ಎಸ್. ಬಹುಪದ ಪ್ರೋಗ್ರಾಂನ ದ್ವಂದ್ವತೆ ಮತ್ತು ಧನಾತ್ಮಕ-ಸಮಾನ-ಸೀಮಿತ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ನಿರ್ಬಂಧಿತ ಬಹುಪದ ಆಪ್ಟಿಮೈಸೇಶನ್ಗಾಗಿ ಸಡಿಲಿಕೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಎಸ್. ಓ. ಎಸ್. ಪ್ರೋಗ್ರಾಂಗಳನ್ನು ಅರೆ-ಸೀಮಿತ ಪ್ರೋಗ್ರಾಂಗಳಾಗಿ (ಎಸ್. ಡಿ. ಪಿ. ಗಳು) ಪರಿವರ್ತಿಸಬಹುದು, ಈ ಕೆಳಗಿನ ವಿಭಾಗವನ್ನು ನೋಡಿ. ದ್ವಂದ್ವ ಸಮಸ್ಯೆಃ ನಿರ್ಬಂಧಿತ ಬಹುಪದ ಆಪ್ಟಿಮೈಸೇಶನ್ ನಾವು-ವೇರಿಯೇಟ್ ಬಹುಪದಿಯನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ, ಮತ್ತು ನಾವು ಈ ಬಹುಪದವನ್ನು ಉಪವಿಭಾಗದ ಮೇಲೆ ಕಡಿಮೆ ಮಾಡಲು ಬಯಸುತ್ತೇವೆ ಎಂದು ಭಾವಿಸೋಣ. ಇದಲ್ಲದೆ, ಉಪವಿಭಾಗದ ಮೇಲಿನ ನಿರ್ಬಂಧಗಳನ್ನು ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದ ಸಮಾನತೆಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಎನ್ಕೋಡ್ ಮಾಡಬಹುದು ಎಂದು ಭಾವಿಸೋಣ, ಪ್ರತಿ ರೂಪವು ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದಿಯಾಗಿದೆ. ಈ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗೆ ನೈಸರ್ಗಿಕ, ಸಾಮಾನ್ಯವಾಗಿ ಕನ್ವೆಕ್ಸ್ ಅಲ್ಲದ ಪ್ರೋಗ್ರಾಂ ಈ ಕೆಳಗಿನವುಗಳಿಗೆ ಒಳಪಟ್ಟಿರುತ್ತದೆಃ ಡಿಗ್ರಿಗಳ ಪ್ರತಿ ಮೊನೊಮಿಯಲ್ಗೆ ಒಂದು ನಮೂದನ್ನು ಹೊಂದಿರುವ-ಆಯಾಮದ ವೆಕ್ಟರ್ ಎಲ್ಲಿದೆ, ಆದ್ದರಿಂದ ಪ್ರತಿ ಮಲ್ಟಿಸೆಟ್ಗೆ, ನಾವು ಕಡಿಮೆ ಮಾಡಲು ಬಯಸುವ ಬಹುಪದದ ಗುಣಾಂಕಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ, ಮತ್ತು ಇದು ಬಹುಪದ ಎನ್ಕೋಡಿಂಗ್-th ನಿರ್ಬಂಧದ ಗುಣಾಂಕಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ. ಬಹುಪದಗಳನ್ನು ಬರೆಯುವ ಅನುಕೂಲಕ್ಕಾಗಿ ಮತ್ತು ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ ನಮ್ಮ ಹುಡುಕಾಟ ಜಾಗದಲ್ಲಿ ಹೆಚ್ಚುವರಿ, ಸ್ಥಿರ ಸ್ಥಿರ ಸೂಚ್ಯಂಕವನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಈ ಪ್ರೋಗ್ರಾಂ ಸಾಮಾನ್ಯವಾಗಿ ಕನ್ವೆಕ್ಸ್ ಅಲ್ಲ, ಏಕೆಂದರೆ ನಿರ್ಬಂಧಗಳು () ಕನ್ವೆಕ್ಸ್ ಆಗಿರುವುದಿಲ್ಲ. ಈ ಕನಿಷ್ಠೀಕರಣದ ಸಮಸ್ಯೆಗೆ ಒಂದು ಸಂಭವನೀಯ ಕನ್ವೆಕ್ಸ್ ಸಡಿಲಿಕೆಯು ಧನಾತ್ಮಕ-ಸೆಮಿಡಿಫೈನೈಟ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನೊಂದಿಗೆ ವೇರಿಯೇಬಲ್ಗಳ ರ್ಯಾಂಕ್-ಒನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಬದಲಿಸಲು ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಬಳಸುತ್ತದೆಃ ನಾವು ಗಾತ್ರದ ಪ್ರತಿಯೊಂದು ಮೊನೊಮಿಯಲ್ ಅನ್ನು ಹೆಚ್ಚಿನ ಸೂಚ್ಯಂಕಗಳ ಮಲ್ಟಿಸೆಟ್ನಿಂದ ಸೂಚ್ಯಂಕಗೊಳಿಸುತ್ತೇವೆ. ಅಂತಹ ಪ್ರತಿಯೊಂದು ಮೊನೊಮಿಯಲ್ಗೆ, ನಾವು ಪ್ರೋಗ್ರಾಂನಲ್ಲಿ ವೇರಿಯೇಬಲ್ ಅನ್ನು ರಚಿಸುತ್ತೇವೆ ಮತ್ತು ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ರೂಪಿಸಲು ನಾವು ವೇರಿಯೇಬಲ್ಗಳನ್ನು ಜೋಡಿಸುತ್ತೇವೆ, ಅಲ್ಲಿ ನಿಜವಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಸೆಟ್ ಆಗಿದ್ದು, ಅದರ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ಗರಿಷ್ಠ ಗಾತ್ರದ ಅಂಶಗಳ ಮಲ್ಟಿಸೆಟ್ಗಳೊಂದಿಗೆ ಗುರುತಿಸಲಾಗುತ್ತದೆ. ನಂತರ ನಾವು ಈ ಕೆಳಗಿನ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಅಸ್ಥಿರಗಳಲ್ಲಿ ಬರೆಯುತ್ತೇವೆಃ ಇದಕ್ಕೆ ಒಳಪಟ್ಟಿರುತ್ತದೆಃ ಇಲ್ಲಿ ನಾವು ಕಡಿಮೆ ಮಾಡಲು ಬಯಸುವ ಬಹುಪದದ ಗುಣಾಂಕಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ, ಮತ್ತು ಇದು ಬಹುಪದ ಎನ್ಕೋಡಿಂಗ್ನ ಗುಣಾಂಕಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ. ಮೂರನೆಯ ನಿರ್ಬಂಧವು ಮ್ಯಾಟ್ರಿಕ್ಸ್ನೊಳಗೆ ಹಲವಾರು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುವ ಮೊನೊಮಿಯಲ್ನ ಮೌಲ್ಯವು ಮ್ಯಾಟ್ರಿಕ್ಸ್ನಾದ್ಯಂತ ಸಮಾನವಾಗಿರುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ ಮತ್ತು ಕ್ವಾಡ್ರಾಟಿಕ್ ರೂಪದಲ್ಲಿ ಇರುವ ಸಮ್ಮಿತಿಗಳನ್ನು ಗೌರವಿಸಲು ಸೇರಿಸಲಾಗುತ್ತದೆ. ಡುಯಾಲಿಟಿ ಒಬ್ಬರು ಮೇಲಿನ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಂನ ಡ್ಯುಯಲ್ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು ಮತ್ತು ಈ ಕೆಳಗಿನ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಪಡೆಯಬಹುದುಃ ಇದಕ್ಕೆ ಒಳಪಟ್ಟುಃ ನಾವು ನಿರ್ಬಂಧಕ್ಕೆ ಅನುಗುಣವಾದ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ (ಅಲ್ಲಿ ಎಲ್ಲಾ ನಮೂದುಗಳನ್ನು ಹೊಂದಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಸೂಚಿಕೆ ಮಾಡಲಾದ ನಮೂದಿಗೆ ಶೂನ್ಯವನ್ನು ಉಳಿಸಿ), ಪ್ರತಿ ಬಹುಪದ ನಿರ್ಬಂಧಕ್ಕೆ ನಿಜವಾದ ವೇರಿಯೇಬಲ್ ಮತ್ತು ಮಲ್ಟಿಸೆಟ್ಗಳ ಪ್ರತಿಯೊಂದು ಗುಂಪಿಗೆ, ನಾವು ಸಮ್ಮಿತಿ ನಿರ್ಬಂಧಕ್ಕೆ ಡ್ಯುಯಲ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಧನಾತ್ಮಕ-ಸಮಪರಿಮಿತಿಯ ನಿರ್ಬಂಧವು ಬಹುಪದಗಳ ವರ್ಗಗಳ ಮೊತ್ತವನ್ನು ಖಾತ್ರಿಪಡಿಸುತ್ತದೆಃ ಧನಾತ್ಮಕ-ಸಮಪರಿಮಿತ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಗುಣಲಕ್ಷಣದಿಂದ, ಯಾವುದೇ ಧನಾತ್ಮಕ-ಸಮಪರಿಮಿತ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗೆ, ನಾವು ವಾಹಕಗಳಿಗೆ ಬರೆಯಬಹುದು. ಹೀಗಾಗಿ ಯಾವುದಕ್ಕೂ, ನಾವು ವಾಹಕಗಳನ್ನು ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಪಾಲಿನೋಮಿಯಲ್ನ ಗುಣಾಂಕಗಳೊಂದಿಗೆ ಗುರುತಿಸಿದ್ದೇವೆ. ಇದು ಮೌಲ್ಯವು ಮೀರಿದೆ ಎಂಬುದಕ್ಕೆ ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಪುರಾವೆಯನ್ನು ನೀಡುತ್ತದೆ. ಮೇಲಿನವುಗಳನ್ನು ಬಹುಪದೀಯ ಅಸಮಾನತೆಗಳಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಪ್ರದೇಶಗಳಿಗೂ ವಿಸ್ತರಿಸಬಹುದು. ಲಸ್ಸೆರೆ ಕ್ರಮಾನುಗತ ಎಂದೂ ಕರೆಯಲ್ಪಡುವ ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಕ್ರಮಾನುಗತವು (ಎಸ್ಓಎಸ್ ಕ್ರಮಾನುಗತ) ಹೆಚ್ಚುತ್ತಿರುವ ಶಕ್ತಿ ಮತ್ತು ಹೆಚ್ಚುತ್ತಿರುವ ಗಣನೆಯ ವೆಚ್ಚದ ಕನ್ವೆಕ್ಸ್ ಸಡಿಲಿಕೆಗಳ ಕ್ರಮಾನುಗತವಾಗಿದೆ. ಪ್ರತಿ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾದ ಕನ್ವೆಕ್ಸ್ ವಿಶ್ರಾಂತಿಯನ್ನು ಎಸ್ಓಎಸ್ ಕ್ರಮಾನುಗತದ th ಹಂತ ಅಥವಾ-th ಸುತ್ತು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮೊದಲ ಸುತ್ತು, ಯಾವಾಗ, ಮೂಲ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಂಗೆ ಅನುರೂಪವಾಗಿದೆ, ಅಥವಾ ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದಗಳ ಮೇಲೆ ಸಮ-ಆಫ್-ಸ್ಕ್ವೇರ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ಗೆ ಅನುರೂಪವಾಗಿದೆ. ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯ ಮೊದಲ ಹಂತದ ಮೂಲಭೂತ ಕನ್ವೆಕ್ಸ್ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು-th ಮಟ್ಟಕ್ಕೆ ಹೆಚ್ಚಿಸಲು, ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದಗಳನ್ನು ಪರಿಗಣಿಸಲು ಹೆಚ್ಚುವರಿ ಅಸ್ಥಿರಗಳು ಮತ್ತು ನಿರ್ಬಂಧಗಳನ್ನು ಪ್ರೋಗ್ರಾಂಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಎಸ್. ಓ. ಎಸ್ ಕ್ರಮಾನುಗತವು ತನ್ನ ಹೆಸರನ್ನು-th ಮಟ್ಟದಲ್ಲಿ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯದ ಮೌಲ್ಯವು ದ್ವಿಗುಣದ ಮೂಲಕ ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಒಟ್ಟು-ವರ್ಗಗಳ ಪುರಾವೆಯೊಂದಿಗೆ ಬಂಧಿಸಲ್ಪಟ್ಟಿದೆ ಎಂಬ ಅಂಶದಿಂದ ಪಡೆಯುತ್ತದೆ (ಮೇಲಿನ "ದ್ವಂದ್ವತೆ" ಯನ್ನು ನೋಡಿ). ಪರಿಣಾಮವಾಗಿ, ಗರಿಷ್ಠ ಮಟ್ಟದ ಬಹುಪದಗಳನ್ನು ಬಳಸುವ ಯಾವುದೇ ವರ್ಗಗಳ ಮೊತ್ತದ ಪುರಾವೆಯನ್ನು ವಸ್ತುನಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಬಂಧಿಸಲು ಬಳಸಬಹುದು, ಇದು ವಿಶ್ರಾಂತಿಯ ಬಿಗಿತದ ಬಗ್ಗೆ ಖಾತರಿಗಳನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಬರ್ಗ್ ಪ್ರಮೇಯದ ಜೊತೆಯಲ್ಲಿ, ಸಾಕಷ್ಟು ಅನೇಕ ಸುತ್ತುಗಳನ್ನು ನೀಡಿದರೆ, ಯಾವುದೇ ಸ್ಥಿರ ಮಧ್ಯಂತರದಲ್ಲಿ ವಿಶ್ರಾಂತಿ ಅನಿಯಂತ್ರಿತವಾಗಿ ಬಿಗಿಯಾಗಿರುತ್ತದೆ ಎಂದು ಇದು ಮತ್ತಷ್ಟು ಸೂಚಿಸುತ್ತದೆ. ಸೀಮಿತ ಅವಧಿಯೊಳಗಿನ ಪ್ರತಿ ಋಣಾತ್ಮಕವಲ್ಲದ ನೈಜ ಬಹುಪದಿಯನ್ನು ಆ ಮಧ್ಯಂತರದಲ್ಲಿ ನಿಖರತೆಯೊಳಗೆ ಸಾಕಷ್ಟು ಹೆಚ್ಚಿನ ಮಟ್ಟದ ನೈಜ ಬಹುಪದಗಳ ವರ್ಗಗಳ ಮೊತ್ತದೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು ಎಂದು ಬರ್ಗ್ ಅವರ ಫಲಿತಾಂಶವು ಹೇಳುತ್ತದೆ, ಮತ್ತು ಆದ್ದರಿಂದ ಬಹುಪದ ವಸ್ತುನಿಷ್ಠ ಮೌಲ್ಯವು ಬಿಂದುವಿನ ಕಾರ್ಯವಾಗಿದ್ದರೆ, ಅಸಮಾನತೆಯು ಆಸಕ್ತಿಯ ಪ್ರದೇಶದಲ್ಲಿ ಎಲ್ಲರಿಗೂ ಇದ್ದರೆ, ಈ ಸತ್ಯಕ್ಕೆ ಒಟ್ಟು-ವರ್ಗಗಳ ಪುರಾವೆ ಇರಬೇಕು. ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪ್ರದೇಶದ ಮೇಲೆ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯದ ಕನಿಷ್ಠ ಎಂದು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ನಾವು ಫಲಿತಾಂಶವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ವೆಚ್ಚ ವೇರಿಯೇಬಲ್ಗಳಲ್ಲಿ ಒಂದು ಕಾರ್ಯವನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸುವಾಗ, ಕ್ರಮಾನುಗತದ-th ಮಟ್ಟವನ್ನು ವೇರಿಯೇಬಲ್ಗಳ ಮೇಲೆ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಂ ಎಂದು ಬರೆಯಬಹುದು ಮತ್ತು ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಯಕ್ಕೆ ಪರಿಹರಿಸಬಹುದು. ಅಂತಹ ಬಹುಪದಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ಬಹುಪದವು ವರ್ಗಗಳ ಮೊತ್ತ (ಎಸ್. ಓ. ಎಸ್) ಆಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಇದು ವರ್ಗಗಳ ಮೊತ್ತವಾಗಿದೆ ಏಕೆಂದರೆ ಇದು ವರ್ಗಗಳ ಮೊತ್ತವಾಗಿದ್ದರೆ ಎಲ್ಲರಿಗೂ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಬಹುಪದ ಎಸ್ಓಎಸ್ನ ವಿವರವಾದ ವಿವರಣೆಗಳೆಂದರೆ available.Parrilo, ಪಿ. (2003) "ಅರೆ ಬೀಜಗಣಿತದ ಸಮಸ್ಯೆಗಳಿಗೆ ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಡಿಲಿಕೆಗಳು". ಮ್ಯಾಥಮೆಟಿಕಲ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸರ್. ಬಿ 96 (2), 293-320. ಸಮಮಿತಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎಲ್ಲಿದೆ ಎಂದು ಚತುರ್ಭುಜ ರೂಪಗಳನ್ನು ವ್ಯಕ್ತಪಡಿಸಬಹುದು. ಅಂತೆಯೇ, ಡಿಗ್ರಿ ≤ 2d "ನ ಬಹುಪದಿಗಳನ್ನು ವೆಕ್ಟರ್ ಎಲ್ಲಾ ಡಿಗ್ರಿ ಮೊನೊಮಿಯಲ್ಗಳನ್ನು ಹೊಂದಿರುವಂತೆ ವ್ಯಕ್ತಪಡಿಸಬಹುದು. ಇದನ್ನು ಗ್ರಾಮ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ರೂಪ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಒಂದು ಪ್ರಮುಖ ಸಂಗತಿಯೆಂದರೆ, ಅಂತಹ ಸಮ್ಮಿತೀಯ ಮತ್ತು ಧನಾತ್ಮಕ-ಸೆಮಿಡಿಫೈನೈಟ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಇದ್ದರೆ ಮಾತ್ರ ಅದು ಎಸ್. ಓ. ಎಸ್. ಆಗಿರುತ್ತದೆ. ಇದು ಎಸ್. ಓ. ಎಸ್. ಬಹುಪದಗಳು ಮತ್ತು ಧನಾತ್ಮಕ-ಅರೆ-ಪರಿಮಿತ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ನಡುವಿನ ಸಂಪರ್ಕವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಸಾಫ್ಟ್ವೇರ್ ಉಪಕರಣಗಳು, ಜಿ. ಎನ್. ಯು. ಜಿ. ಪಿ. ಎಲ್. ಅಡಿಯಲ್ಲಿ ಪರವಾನಗಿ ಪಡೆದಿವೆ. ಉಲ್ಲೇಖ ಮಾರ್ಗದರ್ಶಿ arXiv: 1310.4716 [math.OC] ನಲ್ಲಿ ಲಭ್ಯವಿದೆ, ಮತ್ತು ಅದರ ಆಂತರಿಕಗಳ ಬಗ್ಗೆ ಪ್ರಸ್ತುತಿಯು ಇಲ್ಲಿ ಲಭ್ಯವಿದೆ. ಸಿಡಿಸಿಎಸ್-ಎಸ್ಒಎಸ್, ಸಿಡಿಸಿಎಸ್ನ ಪ್ಯಾಕೇಜ್, ದೊಡ್ಡ ಪ್ರಮಾಣದ ಎಸ್ಒಎಸ್ ಪ್ರೋಗ್ರಾಂಗಳೊಂದಿಗೆ ವ್ಯವಹರಿಸಲು ವರ್ಧಿತ ಲಗ್ರಾಂಜಿಯನ್ ವಿಧಾನ ಪರಿಹಾರಕವಾಗಿದೆ. ಜೂಲಿಯಾಗಾಗಿ ಜುಎಂಪಿಯ ಸುಮೋಫ್ ಸ್ಕ್ವೇರ್ಸ್ ವಿಸ್ತರಣೆ. ಜೂಲಿಯಾಗಾಗಿ ಟಿಎಸ್ಎಸ್ಓಎಸ್, ಸ್ಪಾರ್ಸಿ ಅಳವಡಿಸಿದ ಕ್ಷಣ-ಎಸ್ಒಎಸ್ ಶ್ರೇಣಿಗಳನ್ನು ಆಧರಿಸಿದ ಬಹುಪದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಾಧನವಾಗಿದೆ. ನಿರ್ಬಂಧಿತ ಬಹುಪದ ಆಪ್ಟಿಮೈಸೇಶನ್ನ ಎರಡು ಸಮಸ್ಯೆಗಳಿಗೆ, ಮ್ಯಾಟ್ಲ್ಯಾಬ್/ಆಕ್ಟೇವ್ಗಾಗಿ ಗ್ಲೋಪ್ಟಿಪೋಲಿ, ಪೈಥಾನ್ಗಾಗಿ ಎನ್ಸಿಪೋಲ್2ಎಸ್ಡಿಪಿಎ ಮತ್ತು ಜೂಲಿಯಾಗೆ ಮೊಮೆಂಟ್ಆಪ್ಟ್. ಉಲ್ಲೇಖಗಳು ಗಣಿತದ ಆಪ್ಟಿಮೈಸೇಶನ್ ನೈಜ ಬೀಜಗಣಿತದ ರೇಖಾಗಣಿತ