Optimization problem for non-symmetric normal cone inclusion or antiderivative of Ax+b

84 Views Asked by At

I have the following equation:

$$ -(\mathbf{A}\mathbf{x} + \mathbf{c}) \in \mathcal{N}_{C}(\mathbf{x}) \qquad (1) $$ where $\mathbf{A} \in \mathbb{R}^{n\times n}$ is symmetric and positive definite, and $\mathbf{x} \in \mathcal{C} \subseteq \mathbb{R}^n$ and $$\mathcal{N}_{C} := \{\mathbf{x} \mid \mathbf{x}^\top(\mathbf{x}^*-\mathbf{x}) \leq 0 \quad \forall \mathbf{x}^* \in \mathcal{C}\}$$ is the normal cone to the convex set $\mathcal{C}$. Normally the inclusion above is the optimality condition of the optimization problem: $$ \min \frac{1}{2} \mathbf{x}^\top \mathbf{A}\mathbf{x} + \mathbf{x}^\top \mathbf{c} + I_{\mathcal{C}}(\mathbf{x})$$ where $I_{\mathcal{C}}(\mathbf{x})$ is the indicator function to the convex set $$I_{\mathcal{C}}(\mathbf{x}) := \begin{cases} 0 & if \quad \mathbf{x} \in \mathcal{C} \\ \infty & if \quad \mathbf{x} \notin \mathcal{C} \end{cases}$$

My interest is, how can we see that starting from (1) and assuming that $\mathbf{A}$ in (1) is not symmetric but invertible then there exists no optimization (convex?) problem? If this is true? How can we see this?

In other words: what is the antiderivative of $\mathbf{A}\mathbf{x} + \mathbf{c}$ in the case $\mathbf{A}$ is not symmetric but invertible?

1

There are 1 best solutions below

2
On BEST ANSWER

If $A$ is non-symmetric, there is no $f : \mathbb{R}^n \to \mathbb{R}^n$, such that $f'(x) = A \, x + c$. Indeed, this would imply that the Hessian $f''(x) = A$ is non-symmetric.

(However, there are other methods to deal with problem (1).)