Метод решения задач нелинейного программирования с использованием базиса переменной размерности

Abstract

Розглядається метод апроксимуючого програмування з розмірністю базису, що поступово збільшується/зменшується. Якщо розв’язок знаходиться у вершині обмежуючого многогранника — на межі перетинання n обмежуючих гіперповерхонь ( n — розмірність простору шуканих змінних), то розмірність базису досягає n ; якщо розв’язок знаходиться на гранях чи ребрах обмежуючого многогранника, то розмірність базису знижується. Якщо розв’язок знаходиться усередині припустимої області, то розмірність базису дорівнює нулю і зміна X на останніх кроках відповідає алгоритму найшвидшого спуску (крутого сходження). Другою особливістю методу є використання квадратичної апроксимації варіації нев’язок ∆ϕᵢ( X ) уздовж припустимого придатного напряму — променя σ — лінійної комбінації ребер поточного базисного конуса. Квадратична апроксимація дозволяє збільшити довжину кроку в порівнянні з найпростішими методами апроксимуючого програмування.

Approximation programming method with gradual increasing/decreasing basis dimension is considered. If solution is found in the vertex of limiting polyhedron, i.e. on the boundary of intersection of n -limiting hyperplane ( n — dimension of space of searched variables), then the basis dimension reaches n ; if the solution is on the faces or edges of limiting polyhedron, then basis dimension is decreased. If the solution is found inside admissible domain, then basis dimension is zero and X -trace on the last steps corresponds to the fastest descent (ascent) algorithm. The other feature of the method is the application of quadratic approximation of discrepancy ∆ϕᵢ( X ) variation along admissible appropriate direction — ray σ — linear combination of edges of current basis cone. The quadratic approximation method enables us to increase the step length in comparison with the simplest methods of approximation programming.