Решение квадратичной оптимизации в MATLAB

У меня есть неограниченная задача квадратичной оптимизации. Мне нужно найти u, который минимизирует норму (u ^ H * A_k * u - d_k)), где A_k - матрица 4x4 (k = 1,2...180), а u - вектор 4x1. (H обозначает эрмитов).

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


matlab mathematical-optimization quadratic-programming
person zsha    schedule 23.11.2015    source источник
comment
Играет ли индекс k какую-либо роль в вашем решении? Или просто |u'Au-d| -› мин для например. данное к?   -  person Felix Darvas    schedule 23.11.2015
comment
нет k - это просто индекс, т.е. я должен мин |u'A_ku-d_k| для k=1,2...180.   -  person zsha    schedule 23.11.2015
comment
поскольку у вас, кажется, нет никаких ограничений, вы можете просто использовать «fminunc»   -  person Felix Darvas    schedule 23.11.2015
comment
Ваша запись не ясна. Является ли ваша матрица А симметричной? Какие размеры на А? Обозначает ли k размерность на A? Или вам нужно решить эту задачу 180 раз для k = от 1 до 180? В комментарии вы написали |u'A_ku - d_k| что обозначает абсолютное значение, но в вопросе есть скобки. Что это?   -  person Matthew Gunn    schedule 23.11.2015
comment
Да, матрица A симметрична 4x4 и положительно определена. u'A_ku является скаляром, а d_k также является скаляром для заданного k, и в конечном итоге OP находит вектор u, который минимизирует: суммирование (сигма) из k = 1,.. 180 норма (u'Au-d). (В латексе OP можно записать как \sum_{k=1}^{180}(u^H\textbf{A_k}u - d_k))$$, но я не знаю, почему здесь это не так!)   -  person zsha    schedule 23.11.2015
comment
Спасибо. Я могу читать латексный код, даже если он не отображается. :) Честно говоря, выглядит немного сложной проблемой. Сначала я подумал, что это задача прямого квадратичного программирования, но я думаю, что норма или абсолютное значение снаружи разрушает выпуклость задачи?   -  person Matthew Gunn    schedule 23.11.2015

Ответы (2)


arrow_upward
2
arrow_downward

Предварительные математические выкладки:

Если А симметрична, положительно определена, то матрица А определяет норму. Эта норма, называемая нормой A, записывается как ||x||_A = x'Ax. Ваша проблема minimize (over x) |x'*A*x - d| эквивалентна поиску вектора x, чья «норма A» равна d. Такой вектор легко найти, просто увеличивая или уменьшая любой ненулевой вектор, пока он не будет иметь соответствующую величину.

  1. Выберите произвольное y (не может быть все нулем). например. y = [1; zeros(n-1, 1)]; или y = rand(n, 1);
  2. Найдите некоторый скаляр c, такой что x = c*y и x'Ax=d. Подставляя получаем c^2 y'Ay=d отсюда:.

Тривиальная процедура поиска ответа:

y = [1; zeros(n-1)];   %Any arbitrary y will do as long as its not all zero
c = sqrt(d / (y'*A*y)) 
x = c * y`

x теперь решает вашу проблему. Не требуется ящик для инструментов!

person Matthew Gunn    schedule 23.11.2015
comment
Большое спасибо за ваши усилия. Да, я решил это с помощью вашего метода, а также с помощью fminsearch, но я хочу сделать это технически;) Поэтому я пытаюсь решить это с помощью метода Ньютона-Рэмпсона. Я надеюсь, что это дает хорошую оценку! - person zsha; 24.11.2015

arrow_upward
1
arrow_downward 

options = optimoptions('fminunc','GradObj','on','TolFun',1e-9,'TolX',1e-9);
x = fminunc(@(x)qfun(x,A,d),zeros(4,1),options);

с участием

function [y,g]=qfun(x,A,d)
y=(x'*A*x-d);
g=2*y*(A+A')*x;
y=y*y;

Кажется, работает.

person Felix Darvas    schedule 23.11.2015
comment
Я ценю ваше предложение, но я ищу метод, который не требует инструментов оптимизации MATLAB. - person zsha; 23.11.2015
comment
Поскольку у вас есть функция и градиент, вы можете просто реализовать собственную оптимизацию. Метод Ньютона (en.wikipedia.org/wiki/Newton%27s_method_in_optimization) должен работать. думать. - person Felix Darvas; 23.11.2015
comment
Да, даже я пытаюсь это реализовать по методу Ньютона-Рэмпсона. Есть ли встроенная функция Matlab для вычисления производных первого и второго порядка? - person zsha; 24.11.2015
comment
У вас тут же есть производная 1-го порядка, ее выход g из qfun. Вторая производная также легко вычисляется из этого. - person Felix Darvas; 24.11.2015
comment
Понимаю. Но разве не должно быть g= 2*y*(A)*x? (Я не получил часть +A') - person zsha; 24.11.2015
comment
внутренняя производная равна d/dx (x'Ax), поэтому применяется цепное правило, то есть d/dx(x')*Ax+x' d/dx( А*х) - person Felix Darvas; 24.11.2015
comment
Это более строгое рассмотрение производных, задействованных en.wikipedia.org/wiki/Matrix_calculus. - person Felix Darvas; 24.11.2015