Оптимизация целевой функции с помощью шаговых функций - PullRequest
Новая
       11

Оптимизация целевой функции с помощью шаговых функций

3 голосов
/ 10 января 2011

Я задал этот вопрос в Math SE, но ответ не очень удовлетворительный.Поэтому я снова спросил здесь:

У меня есть проблема оптимизации с линейным неравенством и ограничением равенств: 

A*x<=b 
Aeq*x=beq

Проблема в том, что целевая функция состоит из суммирования ряда Хевисайдапошаговые функции,

Вот псевдокод для целевой функции: 

function f(k, c, x)
  ffunction =0;
  for i=0;i<k.row.length;i++
     smallF=0
     for j=0; j<k.column.length; j++
      smallF+= k.row[i]*k.column[j]*x[j]+c[j]
     end 
     ffunction += u(smallF)
  end
 f=ffunction 
end


function u(x)
  if(x>0)
   return 1
  else
   return 0
  end
end

Я получил предложение приблизить пошаговую функцию как гладкую функцию и использовать для этой цели нелинейную оптимизацию.Но есть ли в наборе инструментов MATLAB что-нибудь, что позволило бы мне решить эту проблему без плавного преобразования функций?

Ответы [ 3 ]

2 голосов
/ 10 января 2011

Эта проблема может быть решена точно с помощью решателя смешанных целых чисел.Я объясню подробности в моем ответе на ваш пост по Math SE;Подводя итог, вам нужно ввести двоичную переменную и линейное неравенство для каждого члена в целевой функции, включающей в себя ступенчатую функцию Хевисайда.

1 голос
/ 10 января 2011

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

С линейными и нелинейными ограничениями вы можете использовать FMINCON для решения вашей проблемы.

Я не совсем уверен, что понимаю, что вы хотите оптимизировать (извините, это немного рано), но для примера позвольте мне предположить, что у вас есть вектор со значениями x xdata и вектор с y-значениями ydata, к которым вы хотите добавить «лестничную функцию». Вы знаете, сколько шагов, но не знаете, где они находятся. Кроме того, вы знаете, что сумма местоположений шагов должна быть 5 (ограничение линейного равенства).

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

function out = objFun(loc,xdata,ydata)
%#OBJFUN calculates the squared sum of residuals for a stair-step approximation to ydata
%# The stair-step locations are defined in the vector loc

%# create the stairs. Make sure xdata is n-by-1, and loc is 1-by-k
%# bsxfun creates an n-by-k array with 1's in column k wherever x>loc(k)
%# sum sums up the rows
yhat = sum(bsxfun(@gt,xdata(:),loc(:)'),2); %'# SO formatting

%# sum of squares of the residuals
out = sum((ydata(:)-yhat).^2);

Сохраните эту функцию как objFun.m в вашем пути Matlab. Затем вы определяете xdata и ydata (или загружаете его из файла), делаете начальное предположение для loc (массив k-на-1) и массив Aeq для ограничения линейного равенства, так что Aeq*loc==beq (Aeq равно [1 1 1] в случае, если у вас есть 3 шага), и напишите 

locEst = fmincon(@(u)objFun(u,xdata,ydata),locInitialGuess,[],[],Aeq,5);

Это позволит оценить расположение ступеней. Вместо двух пустых скобок вы можете добавить ограничения неравенства, а 5 - потому что я предположил, что ограничение равенства равно 5.

0 голосов
/ 10 января 2011

Абсолютная минимизация по любому одному измерению X - простая задача, которую можно найти за время O (i).

1) выберите Xj для модификации (все остальные исправлены)

2) создайте список длины i, содержащий местоположение переключения для каждого уравнения вдоль Xj, сопоставленное либо с 1, либо с -1, в зависимости от того, уменьшается ли оно или увеличивается при приближении к + inf.

3) Сортировка по месту переключения ... начните с 0 в минимальном месте переключения и добавьте или вычтите отображенное значение.

4) Отслеживайте минимальную сумму при переходе по этому списку, сохраняя место переключения как оптимальное, сопоставленное с результатом.

5) в конце списка ваше лучшее местоположение переключения становится вашим новым значением для Xj.

Отсюда вы можете делать сопряженные минимизации вдоль каждого измерения X, повторяя, пока не прекратите улучшать результат. Это, по крайней мере, найти локальный минимум.

В качестве альтернативы вы можете использовать стандартный локальный код оптимизации, который не требует градиентов ... например, метод скоростной спуск *1017* Nelder Mead. Для этой задачи доступны библиотеки Matlab .

Оба эти подхода дадут вам локальные оптимумы. Если вам действительно нужно более глобальное решение, вы можете обратиться к решениям Имитация отжига или Генетическому алгоритму, которые, вероятно, будут очень хорошо работать с этим типом проблемы.

Наконец, если у вас есть куча денег (не уверен, что это бесплатно), я бы зашел в набор инструментов Matlab Global Optimization .

...