1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .