# Minimizing linear function subject to quadratic constraints?

What's the most efficient way to solve the following quadratically constrained linear objective in Mathematica?

\begin{align} \text{minimize}_{\alpha,t}\ & t \\ \text{subject to } & a_i(1-\alpha h_i)^2 < t \ \forall i \end{align}

There's QuadraticOptimization function, but it does the converse -- linearly constrained quadratic objective.

Here's an example where you can see the minimum is between 1 and 1.5

d = 2;
avals = Table[1/i, {i, 1, d}];
hvals = Table[1/i, {i, 1, d}];
Plot[Max[(1 - alpha hvals)^2 avals], {alpha, 0, 2}]


Motivation

This is equivalent to this problem in the case of simultaneously diagonalizable $$A,H$$

d = 2;
A = DiagonalMatrix[Table[1/i, {i, 1, d}]];
H = DiagonalMatrix[Table[1/i, {i, 1, d}]];
Plot[Norm[MatrixPower[IdentityMatrix[d] - alpha H, 2] . A], {alpha, 0, 2}]


## 1 Answer

( * Minimize or NMinimize *)
sol = Minimize[{Max[(1 - alpha hvals)^2 avals],
0 <= alpha <= 2}, {alpha}]
Plot[Max[(1 - alpha hvals)^2 avals], {alpha, 0, 2},
Epilog -> {PointSize[Large], Red,
Point[{alpha, Max[(1 - alpha hvals)^2 avals]} /. sol[[2]]]}]


• Ok looks like this scales to thousands of dimensions, Minimize is pretty smart at removing redundant constraints Aug 19, 2022 at 5:15