# Tag Info

### 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

### 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
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
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

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

### 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

### 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
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

### 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

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, ... 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