# Tag Info

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$ While $\frac{\|H_{k+1}-H_k\|}{\|H_{k+1}\|} \geq \varepsilon$: $\quad \quad A_{k+1} = A_k(I+G_kH_k)^{-1}A_k$ \quad \quad G_{k+1} = G_k + A_k(I+G_kH_k)^{-1}G_kA_k^... 3 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 depends on the configuration, and whose global minimum corresponds to an optimal solution of your problem. At high temperature, there is enough kinetic energy ... 3 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\rbrace} &&\sum_{i=1}^n \left(\hat{e}_{k_i}^T a^{(i)}\right) + \sum_{i=1}^n \sum_{j=i+1}^n \left(\hat{e}_{k_i}^T b^{(ij)} \hat{e}_{k_j}\right) \end{align}... 3 Your problem reads GivenN$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 following problem (the smallest$k$-point enclosing rectangle), for which efficient deterministic algorithms are known: Given$N$points in two dimensions and an ... 3 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$lives and$\mathbf{1}$is a vector of$n\$ ones. Working with the objective function, \begin{align*} (\mathbf{1}-y)^T P(\mathbf{1}-y) & = \mathbf{1}^T P\... 2 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 1999). 2 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 2 nodes e.g. e_i = \lbrace v_1, v_2, ... , v_n \rbrace. Incidence matrices are straightforward, just look at the wikipedia page. About incidence matrices you ... 1 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, open-source software? For example, you could try using IPOPT. 1 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_{i}/\sigma (X_{i}). And, any correlation matrix can be converted to a covariance matrix as:Q={\text{corr}}({X} )=\left({\text{diag}}(\Sigma )\right)^{-{\...