0
$\begingroup$

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}]

enter image description here

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}]

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$
( * 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]]]}]

enter image description here

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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