Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf

технических средств измерения признаков [8]. Квадрат расстояния между парой классов определяется по фор­ муле

знака для г-н пары классов. Теперь нашу задачу можно

записать в следующем виде:

(3.17)

N

V 3 С ■ < Г

/= 1

где

Я—-(Я„ ..., Я^); Рг—- (рдч ..., рг ),

Е = {Я; Я., = 0,1; (Я-С)<С0).

Таким образом, сформулированная задача является сложной и нетрадиционной. Она состоит в нахождении максмина с ограничением дискретной функции. В про­ стейших случаях, когда N-n сравнительно невелико, за­

дача может быть решена простым перебором. В против­ ном случае для ее решения может быть применен метод штрафных функций, позволяющий приближенно свести задачу определения максмина с ограничением функции к безусловному экстремуму непрерывной функции.

55

Идея метода штрафных функций состоит в замене задачи отыскания относительного максимума функции F (X) при условиях фФ(Х) = 0 , і = 1, . . т, задачей отыс­

кания абсолютного максимума функции

Функции Лфр^Х)]2 называются штрафными функциями.

Если условия связи выполнены, то Е ( Х )= ф ( Х) . Если нет, то второе слагаемое в правой части (3.18) характе­ ризует меру отклонения точки от поверхности фФ(Х)=0. Если теперь для отыскания максимума функции Ф(Х) применить градиентный метод, т. е. использовать рекур­ рентное соотношение

ТП

чтобы компенсировать дефект в выполнении условий свя­ зи. Чем больше будут числа Аі, тем больше будет штраф' за нарушение условий связи.

Рассмотрим задачу отыскания максимума функции F(X), определенной и ограниченной сверху на некотором, компактном множестве Е, при условии, что X удовлетво­ ряет условию ф(X) = 0 . Множество точек X ^ R , удов­ летворяющих этому условию, обозначим через М. Будемполагать, что множество М замкнутое. Построим функ­

цию ф(Х)

рых функция /(X, X) достигает своего максимального значения на R при данном X. Обозначим через N множе­ ство точек Х х, когда X изменяется от 0 до оо. Так как

множество Е компактно, то можно выделить сходя­

щиеся подпоследовательности точек {Хх}, обладаю­

5G

зовавшись теоремой три, доказанной в [10], можно ут­ верждать, что точки Хоо принадлежат множеству М и в этих точках функция F(X) достигает на М своего мак­

симального значения, причем

F (X ) = Ііш max / (X, Я).

Х->оо X^zzE

Возвращаясь к нашей задаче, введем в рассмотрение функцию

Функция Ф(Х) = 0 тогда и только тогда, когда Х е£ , т. е. совокупность ограничений на к заменена одним ограни­

функция аргумента X, то к ней применима сформулиро­ ванная выше теорема о штрафных функциях.

Таким образом,

Так как слагаемое КФ (Я) не зависит от г, то его можно

ввести под знак min, т. е.

57

Таким образом, искомый максмин с ограничением све­ ден к повторному пределу простого максимума некото­ рой функции. Однако пользоваться формулой (3.24) трудно в связи с необходимостью осуществлять предель­ ные переходы в определенной последовательности. Это затруднение удается преодолеть, если иметь в виду, что повторный предел в (3.24) равен двойному пределу вида

58