Is there any closed form solution for the optimal value of the folowing optimization problem?

$$\begin{array}{ll} \text{minimize} & (\mathbf{x} - \mathbf{y})^{\mathrm{T}}\mathbf{B}(\mathbf{x} - \mathbf{y}) + \mathbf{1}^{\mathrm{T}} \mathbf{y} \\ \text{subject to} & \mathbf{x}, \mathbf{y} \geq \mathbf 0\end{array}$$

where $\mathbf{1}$ is an all-one vector and $\mathbf{B}$ is a symmetric indefinite matrix.

  • $\begingroup$ B is indifinite. $\endgroup$
    – Math_Y
    Dec 21 '19 at 20:43
  • $\begingroup$ Suppose $\mathbf{B}$ is a negative semidefinite matrix, the objective value must be $-\infty$. $\endgroup$
    – fengbiqian
    Dec 26 '19 at 7:33

Is the problem well-defined in case $B$ has a negative eigenvalue?

Consider an unit eigenvector $v$ corresponding to a negative eigenvalue $\lambda$ of $B$. Since any vector $v$ can be written as the difference of two vectors each having non-negative elements, we have $v=x_v-y_v$ where $x_v\geq 0, ~y_v\geq 0$. The cost function will then evaluate at $\{x_v, y_v\}$ to: $\lambda + 1^\top y_v$. Scaling $v$ by $K>0$ would then yield: $K^2\lambda + K\left(1^\top y_v\right)$, which is clearly not bounded below.

Compactifying the search space (inside a ball, or alike) would lead to well-posedness, although I still cannot think of a clear way towards a closed form solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.