Maximization of convex quadratic function for diagonal matrices over Euclidean ball

Question

Let's say $\epsilon \in \mathbb{R}^d$. I am trying to solve the following optimization problems:

\begin{equation} \underset{\|\epsilon\| _{\infty} \le \rho}{\operatorname{arg max}} \ \epsilon^T b + \epsilon^T D \epsilon \tag{1} \end{equation}

and

\begin{equation} \underset{\|\epsilon\| _{2} \le \rho}{\operatorname{arg max}} \ \epsilon^T b + \epsilon^T D \epsilon \tag{2} \end{equation}

where $D$ is a diagonal positive semidefinite $d \times d$ matrix.

I know for the minimization case when $D$ is not diagonal this problem is known as the trust-region subproblem and does not have a closed-form solution. I wondered if there is a closed-form solution for at least one of the above problems.

Answer 1

I do not think that problem (2) admits a closed form solution.

As I note in my comment, we know that the only critical point to the problem that is potentially in the interior of the region is a local minimum, so we can guarantee that any maximum must occur on the region's boundary. Denote $f(\epsilon) = \epsilon^Tb + \epsilon^TD\epsilon$, $g(\epsilon) = \|\epsilon\|_2^2 = \epsilon^T\epsilon$.

With Lagrange multipliers, the optimum occurs where $\nabla f = \lambda \nabla g$. We compute $$ \nabla f = b + 2D\epsilon, \quad \nabla g = 2\epsilon. $$ From there, $$ b + 2D\epsilon = 2\lambda \epsilon \implies\\ 2(\lambda I - D)\epsilon = b \implies\\ \epsilon = \frac 12 (\lambda I - D)^{-1}b. $$ Applying the constraint $g(\epsilon) = \rho^2$, we have $$ \frac 14 b^T(\lambda I - D)^{-2}b = \rho^2 \implies \sum_{i=1}^d \frac{b_i^2}{(\lambda - d_i)^2} = 4 \rho^2, $$ but I'm not sure where to proceed from here. At the very least, we have reduced the problem to one of finding the roots of a polynomial.

Answer 2

The first optimization problem has a closed-form solution.

The problem can be written as $$ {\max \sum_{i=1}^n d_{ii}\epsilon_i^2+b_i\epsilon_i \\ \text{s. t.} \\|\epsilon_i|\le \rho\quad,\quad 1\le i\le n. } $$ The state of the problem allows us to optimize each of the $\epsilon_i$s, regardless of the others, i.e., an equivalent form of the problem is solving $$ {\max d_{ii}\epsilon_i^2+b_i\epsilon_i \\ \text{s. t.} \\-\rho\le \epsilon_i\le \rho } $$ for each $i$ and gather the results altogether. The optimal point for the latter problem is $$ \epsilon_i^*=\text{sign}(b_i)\cdot\rho, $$ where $\text{sign}$ denotes the sign function and we assumed $\text{sign}(0)=1$. Therefore, the optimal argument to the original problem is $$ \epsilon^*=\rho\cdot \begin{bmatrix}\text{sign}(b_1)&\text{sign}(b_2)&\cdots&\text{sign}(b_n)\end{bmatrix}. $$