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

Question

Я спросил this question в 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, что позволяет мне решить эту проблему без преобразования гладкой функции?

Answer 1

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

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

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

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

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

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

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

---

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

---

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

---

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

Answer 2

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

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

Я не совсем уверен, что понимаю, что вы хотите оптимизировать (извините, это немного рано), но, ради примера, позвольте мне предположить, что у вас есть вектор с x-значениями xdata и vectory с 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 (к-на-1 массив), и массив Aeq для линейного contstraint равенства таким образом, что Aeq*loc==beq (Aeq в случае [1 1 1] у вас есть 3 шаги) и напишите

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

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

Answer 3

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