Преобразуйте квадратичные ограничения в конические ограничения второго порядка

В этом примере показано, как преобразовать квадратичное ограничение в коническую ограничительную форму второго порядка. Квадратичное ограничение имеет форму

xTQx+2qTx+c0.

Коническое программирование второго порядка имеет ограничения формы

Asc(i)x-bsc(i)dsc(i)x-γ(i).

Матрица Q должно быть симметричным и положительный полуопределенный для вас, чтобы преобразовать квадратичные ограничения. Пусть S будьте квадратным корнем из Q, значение Q=S*S=ST*S. Можно вычислить S использование sqrtm. Предположим, что существует решение b к уравнению STb=q, который всегда верен когда Q положителен определенный. Вычислить b использование b = -S\q.

xTQx+2qTx+c=xTSTSx-2(STb)Tx+c=(Sx-b)T(Sx-b)-bTb+c=Sx-b2+c-bTb.

Поэтому, если bTb>c, затем квадратичное ограничение эквивалентно коническому ограничению второго порядка с

  • Asc=S

  • bsc=b

  • dsc=0

  • γ=-bTb-c

Числовой пример

Задайте векторный f с пятью элементами представление целевой функции fTx.

f = [1;-2;3;-4;5];

Установите квадратичную матрицу ограничений Q как случайная положительная определенная матрица 5 на 5. Установите q как случайный вектор с 5 элементами, и берут аддитивную постоянную c=-1.

rng default % For reproducibility
Q = randn(5) + 3*eye(5);
Q = (Q + Q')/2; % Make Q symmetric
q = randn(5,1);
c = -1;

Создать входные параметры для coneprog, создайте матричный S как квадратный корень из Q.

S = sqrtm(Q);

Создайте остающиеся входные параметры для конического ограничения второго порядка, как задано в первой части этого примера.

b = -S\q;
d = zeros(size(b));
gamma = -sqrt(b'*b-c);
sc = secondordercone(S,b,d,gamma);

Вызовите coneprog решать задачу.

[x,fval] = coneprog(f,sc)
Optimal solution found.
x = 5×1

   -0.7194
    0.2669
   -0.6309
    0.2543
   -0.0904

fval = -4.6148

Сравните этот результат с результатом, возвращенным путем решения этой той же задачи с помощью fmincon. Запишите квадратичное ограничение как описано в Анонимных Нелинейных Ограничительных Функциях.

x0 = randn(5,1); % Initial point for fmincon
nlc = @(x)x'*Q*x + 2*q'*x + c;
nlcon = @(x)deal(nlc(x),[]);
[xfmc,fvalfmc] = fmincon(@(x)f'*x,x0,[],[],[],[],[],[],nlcon)
Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
xfmc = 5×1

   -0.7196
    0.2672
   -0.6312
    0.2541
   -0.0902

fvalfmc = -4.6148

Эти два решения почти идентичны.

Смотрите также

| |

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте