5
votes
Discrete-time Algebraic Riccati Equation (DARE) solver in C++
If you want a ten-line solution that is decently fast and stable, you can implement yourself the structured doubling algorithm: set up the coupled iteration
$A_0 = A, G_0 = G = BR^{-1}B^T, H_0 = Q$
...
- 11.9k
5
votes
Constrained simulated annealing
Simulated annealing comes from computations in statistical mechanics. When I think of simulated annealing, I very much think in terms of physics: I want to minimize some potential energy function that ...
- 603
4
votes
Accepted
What is this discrete optimization problem called?
This can be represented as an integer quadratic program, particularly with binary variables. Your problem (with slight tweaking of notation) is:
\begin{align}
&\min_{k_i \in \lbrace 1, \cdots, m\...
- 4,308
3
votes
Accepted
scipy.optimize.root not converging and RuntimeWarning
The only stationary point is the saddle point at $(y,y')=(0,0)$. Linearization around that point gives that approximately at infinity $y''=y$. The stable solution satisfies $y'=-y$, which would also ...
- 6,139
3
votes
Complementary quadratic knapsack problem
Applying the transformation you suggested, we get:
$$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$
$$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where $n$ is the dimension where $x$ ...
- 131
2
votes
Accepted
Optimization Problem with Array Index as decision variable
I found a simple answer based on the Type1 SOS idea suggested by Richard.
The problem is that I have an integer decision variable $\alpha[t]$, for example, at some solution, the values of $\alpha[t]$:
...
- 131
2
votes
Optimization Problem with Array Index as decision variable
Can you do the following?
xc = x0*xb1 + x1*xb1 + ...
SOS1(xb)
That is, associate each value of your x array with a binary ...
- 4,021
2
votes
Hypergraph matching -> adjacency matrix?
Edges are represented as sets of vertices. With classical graphs, an edge can be represented by the set containing its 2 endpoints. With hypergraphs, they are represented by a set containing more than ...
- 121
2
votes
Accepted
A 95% minimal rectangle problem
Your problem reads
Given $N$ points in, say, two dimensions, find an axes-parallel rectangle
of minimal area that encloses at least 95% of the points.
This is essentially equivalent to the ...
- 2,226
2
votes
Find index for submatrix with maximum sum
This is a binary knapsack problem which is known to be NP-hard. No efficient algo exists yet, but there are algos that can solve problem up to size of 400 variables (according to a paper published in ...
- 482
1
vote
Linearize problem with absolute value
I don’t have any to mind, but you can use a family of functions which are parameterized and smooth with absolute value as their limit. Then you can solve for multiple, usually shrinking, values of the ...
- 10.9k
1
vote
Avalability of SNOPT optimization solver
It appears that SNOPT requires a paid license, even for single-use by an academic. According to the linked-to website, SNOPT would cost you a single payment of $416.
Have you considered using free, ...
- 171
1
vote
Accepted
Knapsack problem with fixed number of elements?
I don't know if this exactly works for you, but will give the relaxed version a shot:
Preliminaries:
Correlation matrix can be seen as the covariance matrix of the standardized random variables $X_{...
- 2,249
Only top scored, non community-wiki answers of a minimum length are eligible