9

Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then: $\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why? $$f_k(A) = \inf \left\{ {\bf tr}(V^T A V) | V \in {\bf R}^{n \times k}, V^T V = I \right\}$$ This follows from the Poincare separation theorem (see e.g. Horn ...


7

For a bounds-constrained problem to minimize $f(x)$ subject to $h(x)\ge 0$, there is no reason for $\nabla f(x^\ast)$ to be small at the optimum $x^\ast$. All the theory guarantees is that $\nabla f(x^\ast) + \lambda^\ast \nabla h(x^\ast)=0$ if the optimum is at a place where the bound is active. In your case, you are imposing the bound via a penalty ...


6

The question is missing some important context about the form of the objective function and constraints. I believe that the OP is referring to minimizing a function $ f(x)=f_{1}(x_{1})+\cdots + f_{N}(x_{N}) $ subject to constraints $Ax=b$. Here the vector $x$ is decomposed into $N$ blocks (that can be vectors of various sizes) $x=\left[ \begin{array}{...


6

First off, let me make a subtle distinction in the implementation of level set methods in topology optimization. In the literature, you will see this method implemented using shape derivatives as in here or using material derivatives (through the use of a Heaviside function) as in here. In my experience, using shape derivatives works better, but material ...


6

Optim.jl from Julia will work with the number types that you give it, so if you make it use BigFloats then it'll do that. Local derivative based, derivative-free, global, and integrates with automatic differentiation. From Julia, it's just: using Optim rosenbrock(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2 result = optimize(rosenbrock, big.(zeros(2)), ...


5

A related task to this is to find a subset of column vectors that are maximally linearly independent. Linear independence isn't exactly the same thing as asking for a large determinant, but if we can use one as a proxy for the other then this heuristic may help you. Rank revealing QR factorization (RRQR) is a good way to achieve this related task. One of ...


5

A general name for this approach is "Block Coordinate Descent." It's important to understand that convergence isn't guaranteed without additional hypotheses. ADMM is not simply block coordinate descent- it's a more complicated method that is optimizing with respect to primal variables $x$ and $z$ in each iteration and then adjusting the Lagrange ...


5

This is no doubt an Optimal Transportation problem. Optimal Transportation aka. Transportation theory mainly talks about how to allocate resources within minimal cost. You can search for related books, blogs or simply start from the wiki page. Also, the problem is a Linear Programming problem, or more specifically Integer Programming problem since the ...


5

In the specific problem you ask about (unlike Richard's more general answer), it turns out that you can relax the $=$ constraint into a $\leq$ without changing the optimal value, and that the resulting convex problem can be solved with the CVX software Richard mentioned. Details: Intuitively the relaxation is possible since if the function had arc length ...


4

It's NP-hard, but there are some heuristic algorithms. See https://arxiv.org/abs/1502.07838 which treats this problem.


4

The way you want to reorder the matrix $U$ is a special case of the assignment problem, and it is solved by standard algorithms like the Hungarian algorithm implemented in standard libraries (e.g., scipy). Note that its time complexity is $O(n^3)$, so it won't work on large matrices. In the assignment problem you are given a cost matrix $C$, and asked to ...


4

This topic has been discussed at some length on Cross Validated (aka stats.stackexchange) and Reddit: Why is Newton's method not widely used in machine learning? (see in particular Nick Alger's answer) Why use gradient descent with neural networks? L-BFGS and neural nets Why second order SGD convergence methods are unpopular for deep learning? How does the ...


4

If your objective function is noisy, then it makes sense to use stochastic algorithms. I would take a look at James Spall's SPSA algorithm and variations. There are also algorithms that update (an approximation of) the Hessian. All of these algorithms take into account that whatever gradient you compute may be noisy, and consequently don't just blindly ...


3

This is probably too late to help you, but here is a compact code that will do points, weights and first derivatives for Gauss, Lobatto or either Radau. function [x,w,A] = OCnonsymGLReig(n,meth) % code for nonsymmetric orthogonal collocation applications on 0 < x < 1 % n - interior points % meth = 1,2,3,4 for Gauss, Lobatto, Radau (right), ...


3

You may want to give SCAT Maple package a try. It is certainly not tailored to geometric programming but is worth trying. C. Hamilton "Symbolic Convex Analysis" thesis from 2005 describes the approach taken, and might reference (or be referenced) by something of your interest. Unfortunately, I never came across symbolic geometric programming research. I ...


3

Neither of these approaches is recommended. Although pivoted Cholesky factorization can help with badly conditioned matrices, it ultimately won't help with a singular matrix. The modified Cholesky factorization could be used, but it's quite expensive computationally in comparison with an efficient implementation of the Cholesky factorization and isn't ...


3

If they don't have a variable that is constrained to a discrete set you can formulate it like so: b1 = m.Var(lb=0,ub=1,integer=True) #Binary variable b2 = m.Var(lb=0,ub=1,integer=True) #Binary variable b3 = m.Var(lb=0,ub=1,integer=True) #Binary variable b4 = m.Var(lb=0,ub=1,integer=True) #Binary variable a = m.Var() #Variable ...


3

I think your best bet is some magic with your objective function. If I understand you correctly, you want to ensure that the optimizer will decrease the total objective function, but also each simulation's objective: so redefine your objective to heavily punish an increase in either objective. Maybe you could formulate it as: $$ J = J_\text{old} + \alpha\...


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

Lower level optimization problems being solved within a top or higher level algorithm are called subproblems. So the algorithm or routine to solve subproblems could be called a "subproblem solver". Googling "subproblem solver" shows that this term is not that uncommon. If there is a specific type of subproblem being solved, that can be incorporated, such as ...


3

I think you should stick with yyour current formulation. If you want to use a penalty, I would augment your function. Calculate your function itself, and then add a penalty of the form $$dJ = -(y - y_{max})^3$$. This will heavily punish any values of $y > y_{max}$. But this will tell your optimizer to seek low values of y. The best choice is if your ...


3

It depends on the selected level of abstraction and chosen classification. The question would be in the usability of this abstraction and the chosen classification of problems. If you are allowed to assume that an objective function can mean a boolean function that is true if and only if the found solution satisfies the given constraints (rules of the ...


3

Yes, any minimization method can be used to find a maximum by applying it to $$ -\min_{x} -f(x) = \max_{x} f(x) $$ (with the usual caveats that such a maximum must exist and $-f$ needs to have the required properties for the minimization method to work).


3

This is a minimum cost network flow problem. Construct the network as follows. You haven't specified the ranges for $i$ and $j$, but I'll assume that we $i=1, 2, \ldots, m$ and $j=1, 2, \ldots, n$. A source node $s$ sourcing $n$ units of flow. $m$ nodes $u_{i}$, $i=1, 2, \ldots, m$. Arcs from $s$ to $u_{i}$ with capacity $c_{i}$ for $i=1, 2, \ldots m$. $...


3

The paper you linked to describes an algorithm similar to the Kabsch algorithm from what I see. It's used to find the least squares rotation between two sets of points. For your case you need something else entirely. Suppose sensor 1 has matrix $M_1$ at time t and sensor 2 has matrix $M_2$ at time t. That means that a vector, whose coordinates in the local ...


3

Following up on my comment on the original question, I have finally managed to construct a counter example that shows that the statement is not in fact correct. Define the positive part of a function, $$ [x]^+ = \begin{cases}x & \text{if $x\ge 0$} \\ 0 & \text{otherwise.}\end{cases} $$ The let $$ \sigma_1(y) = 1+ \left[\tfrac 14 - |y-1|\right]^+ $...


3

The determinant is the product of all eigenvalues $\lambda_i(A)$, so its logarithm is the sum of the logarithms of the eigenvalues. As a consequence, you can write the objective function as follows: $$ \min_A \quad-\sum_i \log\lambda_i(A). $$ Now, assume you had an eigenvalue that tried to go to zero, then its logarithm would go to negative infinity and so ...


3

Despite my comment, I think you can find $\tilde{D}$ that contains the noise term as well. You have this equation: $$-M^{T} \tilde{D} M \phi(t) = -M^{T} D M \phi(t) + W(t)$$ Where $W(t)$ is the noise term vector. So: $$-M^{T} (\tilde{D}-D) M \phi(t) = W(t)$$ Take $\mathcal{D} = \tilde{D} - D$. Let's expand this equation: $$(M \phi(t))_{i} = \sum_{j=1}^{...


2

I would place a wild guess here as an answer. The derivations in the omitted reference used determinants for some theoretical derivations. While determinants are a very useful tool to prove certain things, they are a very lousy tool from the computational science perspective. Now, the theory of transitions was developed (which I am not familiar with) to ...


2

I believe that there is a good alternative that benefits from the geometry of the parameter space and completely eliminates the need for constrained optimization. If you explicitly wanted to make use of Lagrangians, I will definitely not be answering the question, but I thought it might be worthwhile to consider the perspective I will describe. In particular,...


Only top voted, non community-wiki answers of a minimum length are eligible