Un problema de optimización convexa en el que interviene la norma euclídea

Question

¿Alguna idea sobre cómo plantear el siguiente problema de optimización?

$$\begin{array}{ll} \text{maximize} & \|Ax\|_2^2+\|Bx\|_2^2+\|Cx\|_2^2 \\ \text{subject to} & \|x\|_2 = 1\end{array}$$

Answer 1

Estás calculando la matriz $2$ -norma de la matriz $\begin{bmatrix} A \\ B \\ C \end{bmatrix}$ . Así pues, basta con utilizar cualquier método apropiado del álgebra lineal numérica para calcular la norma de una matriz.

En Matlab puedes utilizar la función normest o norm.

Answer 2

La función objetivo es

$$\begin{array}{rl} \|\mathrm A \mathrm x\|_2^2 + \|\mathrm B \mathrm x\|_2^2 + \|\mathrm C \mathrm x\|_2^2 &= \mathrm x^T \mathrm A^T \mathrm A \mathrm x + \mathrm x^T \mathrm B^T \mathrm B \mathrm x + \mathrm x^T \mathrm C^T \mathrm C \mathrm x\\\\ &= \mathrm x^T (\mathrm A^T \mathrm A + \mathrm B^T \mathrm B + \mathrm C^T \mathrm C) \mathrm x\\\\ &\leq \lambda_{\max} (\mathrm A^T \mathrm A + \mathrm B^T \mathrm B + \mathrm C^T \mathrm C) \|\mathrm x\|_2^2\end{array}$$

Si $\|\mathrm x\|_2 = 1$ entonces

$$\|\mathrm A \mathrm x\|_2^2 + \|\mathrm B \mathrm x\|_2^2 + \|\mathrm C \mathrm x\|_2^2 \leq \lambda_{\max} (\mathrm A^T \mathrm A + \mathrm B^T \mathrm B + \mathrm C^T \mathrm C)$$

Answer 3

Como estás multiplicando $x$ por todas estas matrices tienen el mismo número de columnas. Así que está bien para apilarlos a una sola matriz $D$ . Entonces $\|Dx\|_2^2=\|Ax\|_2^2+\|Bx\|_2^2+\|Cx\|_2^2$ . Supongamos que tenemos una descomposición de valor singular (SVD) de $D$ $$USV^t=D.$$ Entonces, si $v$ es la primera columna de $V$ tiene la propiedad de maximizar su problema bajo la restricción dada $\|v\|_2=1$ .

Aquí tienes un programa matlab que compara esto con la respuesta de Rodrigo de Azevedo:

clc

N = 30;
n1 = randperm(N); n1 = n1(1);
n2 = randperm(N); n2 = n2(1);
n3 = randperm(N); n3 = n3(1);
m1 = randperm(N); m1 = m1(1);

A = rand(n1,m1);
B = rand(n2,m1);
C = rand(n3,m1);

D = [A;B;C];

[U,S,V] = svd(D);
v = V(:,1);

[norm(D*v)^2, max(eig(A'*A+B'*B+C'*C))]