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


8

Yes: See Higham's book "Accuracy And Stability of Numerical Algorithms", second edition, chapter 25: Nonlinear Systems and Newton's Method. In particular, see the section on the "limiting residual" in terms of a condition number for the Jacobian. It may well be that since your system is ill-conditioned, that you quickly hit the limiting residual and your ...


8

One commonly used approach is the "Response Surface Method" in which you sample the feasible region, running the full simulation at the sample points, then use regression techniques to fit a surrogate model to these points. You'll be assuming that the response in between your sample points is relatively smooth. Once you've fit that surrogate model, you ...


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}{...


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

Despite your claim that these functions have "special properties", the properties you've supplied still leave f and g extremely general. This means the answers you're going to get must be correspondingly general. If, for instance, you know that g is always positive or f is quadratic, or g is some kind of positive semi-definite matrix, and so on, then you ...


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

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

I would call the constraint "upper- and lower-bounds on the maximum element." Note that you are actually dealing with two separate constraints. Define the max element function as follows $$ \max:\mathbb{R}^{n}\to\mathbb{R}\qquad\max(x)\equiv\max_{i\in\{1,\ldots,n\}}x_{n}. $$ Your first constraint is "take the max element and ensure that it is less than $c$": ...


4

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


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

Geometrically, you are trying to find a point that is (i) as close as possible to the point $\mathbf c_{ref}$ and (ii) as close as possible to the sphere of radius 2. Your objective function is the sum of these two distances. The solution is that point $\mathbf c$ that is half-way between $\mathbf c_{ref}$ and the (closest point on the) sphere of radius 2, i....


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 goal is to compute an $x\in\mathbb{R}^{n}$ to satisfy the strict inequalities $$ f(z_{i})^{T}x>0\qquad\forall z_{i}\in\{1,\ldots,m\}.\tag{1} $$ If we write $\epsilon>0$ as the smallest margin of feasibility, that is $$ \epsilon=\min_{i}\{f(z_{i})^{T}x\}, $$ then (1) is equivalent to $$ f(z_{i})^{T}x\ge\epsilon>0\qquad\forall z_{i}\in\{1,\ldots,...


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

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

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

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

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

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

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

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

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


2

I agree with all of the answers provided here but I wanted to supplement with a Python implementation. We developed the Python GEKKO package for solving similar problems. We're also working on machine learning functions that may be able to combine a convolutional neural network with this constrained mixed-integer problem as a single optimization. Here is a ...


2

Good question! Here is my view of it. There is a hierarchy as follows: integer programming $\subset$ discrete optimization $\subset$ combinatorial optimization. So combinatorial is the broadest field. Any problem that involves making decisions out of a discrete set of alternatives I would classify as a combinatorial problem. The problem definition here ...


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