Кіріспе
Іші нүктелік әдістер (оларды кедергілік әдістер немесе IPM деп те атайды) – сызықтық және сызықтық емес дөңес оптимизация мәселелерін шешуге арналған алгоритмдер. IPM бұрынғы алгоритмдердің екі артықшылығын біріктіреді:
Interior point methods (also referred to as barrier methods or IPMs) are algorithms for solving linear and non linear convex optimization problems. IPMs combine two advantages of previously known algorithms:
Theoretically, their run time is polynomial—in contrast to the simplex method, which has exponential run time in the worst case. Practically, they run as fast as the simplex method—in contrast to the ellipsoid method, which has polynomial run time in theory but is very slow in practice. In contrast to the simplex method which traverses the boundary of the feasible region, and the ellipsoid method which bounds the feasible region from outside, an IPM reaches a best solution by traversing the interior of the feasible region—hence the name.
Теориялық тұрғыдан алғанда, олардың орындалу уақыты полиномиалды болып келеді – нашар жағдайда экспоненциалды уақытқа ие симплекс әдісінен өзгеше. Іс жүзінде олар симплекс әдісімен шамалас жылдамдықпен жұмыс істейді – теорияда полиномиалды уақытқа ие, бірақ практикада өте баяу болатын эллипсоид әдісінен өзгеше. Симплекс әдісі мүмкін болатын аймақтың шекарасымен жүретін, ал эллипсоид әдісі мүмкін болатын аймақты сырттан шектейтін әдістерден айырмашылығы, IPM мүмкін болатын аймақтың ішінде қозғалып, ең жақсы шешімге жетеді – сондықтан осылай аталады.
Interior point methods (also referred to as barrier methods or IPMs) are algorithms for solving linear and non linear convex optimization problems. IPMs combine two advantages of previously known algorithms:
Theoretically, their run time is polynomial—in contrast to the simplex method, which has exponential run time in the worst case. Practically, they run as fast as the simplex method—in contrast to the ellipsoid method, which has polynomial run time in theory but is very slow in practice. In contrast to the simplex method which traverses the boundary of the feasible region, and the ellipsoid method which bounds the feasible region from outside, an IPM reaches a best solution by traversing the interior of the feasible region—hence the name.
Тарих
Ішкі нүкте әдісін 1967 жылы кеңестік математик И. И. Дикин ашқан. Бұл әдіс АҚШ-та 1980 жылдардың ортасында қайта жаңартылды. 1984 жылы Нарендра Кармаркар сызықтық бағдарламалау үшін Кармаркар алгоритмі деп аталатын әдіс әзірледі, ол дәлелденген полиномиалдық уақытта жұмыс істейді (L биттік сандардағы операциялар, мұнда n – айнымалылар мен тұрақтылардың саны) және практикада да өте тиімді. Кармаркардың жұмысы ішкі нүкте әдістеріне қызығушылықты күшейтті. Екі жылдан кейін Джеймс Ренегар ішкі нүкте әдісінің алғашқы жолмен жүретін нұсқасын ойлап тапты, бұл әдіс кейіннен сызықтықтан конвекстік оптимизация мәселелеріне дейін кеңейтілді, конвекстік жиынтықты кодтау үшін қолданылатын өзіндік конкордантты кедергі функциясының негізінде. Кез келген конвекстік оптимизация мәселесін эпиграф формасына түрлендіру арқылы конвекстік жиынтықтағы сызықтық функцияны азайтуға (немесе арттыруға) келтіруге болады. Мүмкін болатын жиынтықты кедергі арқылы кодтау және кедергі әдістерін жобалау идеясын 1960 жылдардың басында Энтони В. Фиакко, Гарт П. Маккормик және басқалар зерттеді. Бұл идеялар негізінен жалпы сызықтық емес бағдарламалау үшін жасалды, бірақ олар кейіннен осы мәселелер класы үшін бәсекеге қабілетті әдістердің пайда болуына байланысты қолданудан шығарылды (мысалы, тізбектік квадраттық бағдарламалау). Юрий Нестеров пен Аркадий Немировский кез келген конвекстік жиынтықты кодтауға болатын осындай кедергілердің ерекше класын ұсынды. Олар алгоритмнің итерациялар санының шешімнің өлшемі мен дәлдігіне байланысты полиноммен шектелгенін кепілдейді.
Анықтамалар
Бізге f — конвекстік функция және G — конвекстік жиын түріндегі конвекстік бағдарлама берілген. Жалпылықты жоғалтпай, f мақсатын сызықтық функция деп қарастыруға болады. Әдетте, G конвекстік жиыны конвекстік теңсіздіктер мен сызықтық теңдіктер жиынтығымен өрнектеледі; сызықтық теңдіктерді сызықтық алгебра қолдану арқылы жоюға болады, сондықтан қарапайымдық үшін тек конвекстік теңсіздіктер бар деп есептейміз және бағдарламаны былай сипаттауға болады, мұнда gi — конвекстік функциялар: Шектеу функциялары белгілі бір отбасыға жатады деп есептейміз (мысалы, квадраттық функциялар), сондықтан бағдарламаны коэффициенттердің шектік векторымен көрсетуге болады (мысалы, квадраттық функциялардың коэффициенттері). Бұл коэффициент векторының өлшемі бағдарламаның мөлшері деп аталады. Берілген бағдарламалар отбасы үшін сандық шешуші — коэффициент векторы берілгенде, t = 1, 2, … үшін шекті сандық амалдарды қолдана отырып, жуықтап xₜ шешімдер тізбегін құратын алгоритм. Сандық шешуші конвергентті деп аталады, егер отбасының кез келген бағдарламасы және кез келген оң ε > 0 үшін, қандай да бір T (бағдарламаға және ε-ға тәуелді болуы мүмкін) табылатын болса, кез келген t > T үшін жуықтап xₜ шешімі ε-ға жуық, яғни: f(xₜ) − f* ≤ ε, gi(xₜ) ≤ ε, i = 1, …, m, x ∈ G, мұнда f* — оптималды шешім. Егер алғашқы T қадамындағы арифметикалық амалдардың жалпы саны ең көп болса poly(бағдарлама мөлшері) * log(V/ε), онда V — деректерге тәуелді тұрақты, мысалы, мүмкін болатын жиынның ең үлкен және ең кіші мәндерінің айырмашылығы. Басқаша айтқанда, V/ε — бұл шешімнің «қатысты дәлдігі» — ең үлкен коэффициентке қатысты дәлдік. log(V/ε) — «дәлдік таңбаларының» саны. Сондықтан, егер әрбір қосымша дәлдік таңбасы бағдарлама мөлшеріне қатысты полиномиалды сандық амалдарды қажет етсе, онда шешуші «полиномиалды» болып табылады.
gi(x t) ≤ ε for i in 1, ,m,
x in G,where f* is the optimal solution. A solver is called polynomial if the total number of arithmetic operations in the first T steps is at mostpoly(problem size) * log(V/ε),where V is some data dependent constant, e. g., the difference between the largest and smallest value in the feasible set. In other words, V/ε is the "relative accuracy" of the solution the accuracy w. r. t. the largest coefficient. log(V/ε) represents the number of "accuracy digits". Therefore, a solver is 'polynomial' if each additional digit of accuracy requires a number of operations that is polynomial in the problem size.
Ішкі нүктелік әдістер арқылы шешілетін құрғақ бағдарламалардың түрлері
Мұнда ішкі нүктелік әдістермен тиімді шешілетін дөңес бағдарламалардың кейбір ерекше жағдайлары келтірілген.
Жартылай нақты бағдарлама
Ішкі нүктелік әдістер жартылай белгісіз бағдарламаларды шешуге қолданылуы мүмкін.