3 votos

Sensibilidad de la solución de QP con respecto a los parámetros

Dado un programa cuadrático, $$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$ Supongamos que $A \succ 0$ por lo que el programa es fuertemente convexo. La cuestión es si la solución $x^*$ continua con respecto a los pesos $A$ y $b$ ?

Si sólo tenemos restricciones de igualdad, esto es fácil ya que podemos simplemente escribir el sistema de ecuaciones utilizando el Lagrangiano y la solución está determinada por el sistema. Sin embargo, con las restricciones de desigualdad, tenemos que lidiar con las restricciones activas / inactivas. No me resulta obvio cómo podemos analizar el cambio en la solución cuando algunas restricciones inactivas se convierten en activas o viceversa.

Algunas referencias relacionadas:

  1. Análisis perturbado de problemas de optimización, J. Frédéric Bonnans, Alexander Shapiro

3voto

Iosif Pinelis Puntos 24742

$\newcommand\R{\mathbb R}\newcommand\tz{\tilde z}\newcommand{\de}{\delta}$ Sí, el minimizador $x_{A,b}$ de $\frac12 x^TAx + b^Tx$ sujeto a $Cx\le d$ es
continua con respecto a $A$ y $b$ -- siempre que el conjunto $X:=\{x\in\R^n\colon Cx\le d\}$ no es vacío (en caso contrario, no existe tal minimizador).

En efecto, dejemos que $M^+$ denota el conjunto de todas las definidas positivas (simétricas) $n\times n$ matrices reales. En lo que sigue, $A,A_k$ están en $M^+$ y $b,b_k$ están en $\R^n=\R^{n\times1}$ donde $k$ es cualquier número natural.

Utilizando la sustitución $x=f_{A,b}(z):=A^{-1/2}z-A^{-1}b$ reescribimos el problema como \begin{equation*} \text{minimize } z^T z \quad \text{over } z\in Z_{A,b}, \end{equation*} donde \begin{equation*} Z_{A,b}:=\{z\in\R^n\colon Cf_{A,b}(z)\le d\}=f_{A,b}^{-1}(X). \end{equation*} Así que.., $Z_{A,b}$ es un subconjunto cerrado no vacío de $\R^n$ y por tanto existe un minimizador único, digamos $z_{A,b}$ de $z^T z$ en $z\in Z_{A,b}$ . Así que.., $x_{A,b}:=f_{A,b}(z_{A,b})=A^{-1/2}z_{A,b}-A^{-1}b$ es el único minimizador de $\frac12 x^TAx + b^Tx$ sujeto a $Cx\le d$ .

Por lo tanto, queda por demostrar que $z_{A,b}$ es continua en $A,b$ .

Para ello, supongamos que $A_k\to A$ y $b_k\to b$ (como $k\to\infty$ ). Entonces \begin{equation*} z_k:=f_{A_k,b_k}^{-1}(f_{A,b}(z_{A,b}))\in Z_{A_k,b_k} \tag{0a}\label{0a} \end{equation*} y \begin{equation*} z_k\to z_{A,b}, \tag{0b}\label{0b} \end{equation*} para que \begin{equation*} z_k^T z_k\to z_{A,b}^T z_{A,b}=m_{A,b}:=\min\{z^T z\colon z\in Z_{A,b}\} \end{equation*} y por lo tanto \begin{equation*} z_{A_k,b_k}^T z_{A_k,b_k}=m_{A_k,b_k}\le m_{A,b}+o(1); \tag{1}\label{1} \end{equation*} en particular, la secuencia $(z_{A_k,b_k})$ está limitada. Por lo tanto y porque $A_k\to A$ y $b_k\to b$ vemos que para $$\tz_k:=f_{A,b}^{-1}(f_{A_k,b_k}(z_{A_k,b_k}))$$ tenemos $\tz_k-z_{A_k,b_k}\to0$ . Por lo tanto y porque $(z_{A_k,b_k})$ está acotada, tenemos $\tz_k^T \tz_k-z_{A_k,b_k}^T z_{A_k,b_k}\to0$ . También, $\tz_k\in Z_{A,b}$ . Así que.., \begin{equation*} m_{A,b}\le \tz_k^T \tz_k=z_{A_k,b_k}^T z_{A_k,b_k}+o(1)=m_{A_k,b_k}+o(1). \tag{2}\label{2} \end{equation*} Por \eqref {1} y \eqref {2},
\begin{equation*} m_{A_k,b_k}\to m_{A,b}. \tag{3}\label{3} \end{equation*}

Para obtener una contradicción, supongamos ahora que $z_{A_k,b_k}\not\to z_{A,b}$ . Entonces, pasando a una subsecuencia, sin pérdida de generalidad (wlog) supongamos que $|z_{A_k,b_k}-z_{A,b}|\ge2\de$ para algunos $\de>0$ y todos $k$ donde $|\cdot|$ es la norma euclidiana. Así, por \eqref {0b}, wlog \begin{equation*} |z_{A_k,b_k}-z_k|\ge\de \tag{4}\label{4} \end{equation*} para todos $k$ . Porque (i) el conjunto $Z_{A_k,b_k}$ es convexo y (ii) el minimizador $z_{A_k,b_k}$ de $z^T z$ en $z\in Z_{A_k,b_k}$ está en $Z_{A_k,b_k}$ y iii) $z_k\in Z_{A_k,b_k}$ por \eqref {0a}, vemos que $w_k:=\frac12\,(z_{A_k,b_k}+z_k)\in Z_{A_k,b_k}$ . Utilizando ahora (i) la identidad del paralelogramo y (ii) las definiciones de $z_{A_k,b_k}$ y $m_{A,b}$ y iii) \eqref {0b} y \eqref {4}, obtenemos \begin{equation*} \begin{aligned} 4|w_k|^2&=2|z_{A_k,b_k}|^2+2|z_k|^2-|z_{A_k,b_k}-z_k|^2 \\ &\le 2m_{A_k,b_k}+2(m_{A,b}+o(1))-\de^2 \\ &\le 4m_{A_k,b_k}+o(1)-\de^2, \end{aligned} \end{equation*} de modo que para todo lo suficientemente grande $k$ tenemos $w_k^T w_k=|w_k|^2<m_{A_k,b_k}$ , lo que contradice la condición $w_k\in Z_{A_k,b_k}$ a la vista de la definición de $m_{A_k,b_k}$ .

Así, $z_{A_k,b_k}\to z_{A,b}$ lo que demuestra que $z_{A,b}$ es continua en $A,b$ . $\quad\Box$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X