3
$\begingroup$

Given a quadratic program, $$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$ Suppose $A \succ 0$, so the program strongly convex. The question is, is the solution $x^*$ continuous with respect to the weights $A$ and $b$ ?

If we only have equality constraints, this is easy since we can simply write out the system of equations using the Lagrangian and the solution is determined by the system. However, with the inequality constraints, we need to deal with active / inactive constraints. It is not obvious to me how we can analyze the change in the solution when some inactive constraints become active or vice versa.

Some related reference:

  1. Perturbation Analysis of Optimization Problems, J. Frédéric Bonnans, Alexander Shapiro

Update: I found the following reference characterizes the problem. Basically, we need regularity of the linear system.

Continuity of the optimal value function in indefinite quadratic programming, Tam, N.N. Journal of Global Optimization 23, 43–61 (2002)

$\endgroup$
0

1 Answer 1

3
$\begingroup$

$\newcommand\R{\mathbb R}\newcommand\tz{\tilde z}\newcommand{\de}{\delta}$Yes, the minimizer $x_{A,b}$ of $\frac12 x^TAx + b^Tx$ subject to $Cx\le d$ is
continuous with respect to $A$ and $b$ -- provided that the set $X:=\{x\in\R^n\colon Cx\le d\}$ is nonempty (otherwise, such a minimizer does not exist).

Indeed, let $M^+$ denote the set of all (symmetric) positive definite $n\times n$ real matrices. In what follows, $A,A_k$ are in $M^+$, and $b,b_k$ are in $\R^n=\R^{n\times1}$, where $k$ is any natural number.

Using the substitution $x=f_{A,b}(z):=A^{-1/2}z-A^{-1}b$, we rewrite the problem as \begin{equation*} \text{minimize } z^T z \quad \text{over } z\in Z_{A,b}, \end{equation*} where \begin{equation*} Z_{A,b}:=\{z\in\R^n\colon Cf_{A,b}(z)\le d\}=f_{A,b}^{-1}(X). \end{equation*} So, $Z_{A,b}$ is a non-empty closed subset of $\R^n$ and hence there is a unique minimizer, say $z_{A,b}$, of $z^T z$ over $z\in Z_{A,b}$. So, $x_{A,b}:=f_{A,b}(z_{A,b})=A^{-1/2}z_{A,b}-A^{-1}b$ is the unique minimizer of $\frac12 x^TAx + b^Tx$ subject to $Cx\le d$.

So, it remains to show that $z_{A,b}$ is continuous in $A,b$.

To do this, suppose that $A_k\to A$ and $b_k\to b$ (as $k\to\infty$). Then \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*} and \begin{equation*} z_k\to z_{A,b}, \tag{0b}\label{0b} \end{equation*} so that \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*} and hence \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*} in particular, the sequence $(z_{A_k,b_k})$ is bounded. Therefore and because $A_k\to A$ and $b_k\to b$, we see that for $$\tz_k:=f_{A,b}^{-1}(f_{A_k,b_k}(z_{A_k,b_k}))$$ we have $\tz_k-z_{A_k,b_k}\to0$. Therefore and because $(z_{A_k,b_k})$ is bounded, we have $\tz_k^T \tz_k-z_{A_k,b_k}^T z_{A_k,b_k}\to0$. Also, $\tz_k\in Z_{A,b}$. So, \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*} By \eqref{1} and \eqref{2},
\begin{equation*} m_{A_k,b_k}\to m_{A,b}. \tag{3}\label{3} \end{equation*}

To obtain a contradiction, suppose now that $z_{A_k,b_k}\not\to z_{A,b}$. Then, passing to a subsequence, without loss of generality (wlog) assume that $|z_{A_k,b_k}-z_{A,b}|\ge2\de$ for some $\de>0$ and all $k$, where $|\cdot|$ is the Euclidean norm. So, by \eqref{0b}, wlog \begin{equation*} |z_{A_k,b_k}-z_k|\ge\de \tag{4}\label{4} \end{equation*} for all $k$. Because (i) the set $Z_{A_k,b_k}$ is convex and (ii) the minimizer $z_{A_k,b_k}$ of $z^T z$ over $z\in Z_{A_k,b_k}$ is in $Z_{A_k,b_k}$ and (iii) $z_k\in Z_{A_k,b_k}$ by \eqref{0a}, we see that $w_k:=\frac12\,(z_{A_k,b_k}+z_k)\in Z_{A_k,b_k}$. Using now (i) the parallelogram identity and (ii) the definitions of $z_{A_k,b_k}$ and $m_{A,b}$ and (iii) \eqref{0b} and \eqref{4}, we get \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*} so that for all large enough $k$ we have $w_k^T w_k=|w_k|^2<m_{A_k,b_k}$, which contradicts the condition $w_k\in Z_{A_k,b_k}$, in view of the definition of $m_{A_k,b_k}$.

Thus, $z_{A_k,b_k}\to z_{A,b}$, which proves that $z_{A,b}$ is continuous in $A,b$. $\quad\Box$

$\endgroup$
1
  • $\begingroup$ Looks good to me! I was thinking about using KKT conditions. The transformation $A^{-1} (\cdot - b)$ makes things much clearer. $\endgroup$
    – gcy
    Commented Feb 27, 2023 at 21:50

You must log in to answer this question.