How can I check for the accuracy of numerical result to optimization problem? Or when is this possible? Intuitively it could be possible at least to some extent, when one knows how to find analytic solutions or analytic approximations. However, what if one just starts with some numerical solution, but the problem is e.g. non-linear. … Read more
I’m trying to understand how the Newton’s method in optimization works. This is the algorithm: S0) Choose x0∈Rn,ρ>0, p>2, β∈(0,1),σ∈(0,12), ε≥0, set k=0 S1) If ‖∇f(xk)‖≤ε STOP S_2) determine d_{k} with D^{2}f(x_{k})d_{k}=-\nabla f(x_{k}) if d_{k} cannot be calculated or the condition \nabla f(x_{k})^{T}d_{k}\leq-p\Vert d_{k}\Vert^{p} is violated, set d_{k}=-\nabla f(x_{k}) S_3) determine t_{k}\in\{\beta^{j}:j=0,1,2,\ \ldots\} maximal with f(x_{k}+t_{k}d_{k})<f(x_{k})+t_{k}\sigma\nabla f(x_{k})^{T}d_{k} S_4) … Read more
I have a set of vectors {Vi} in n-dimensional space. There is a number corresponded to each vector αi=f(Vi) (αi can be negative). I want to find a hyperplane which would maximize the difference between sums of αi on the different sides of the space, divided by plane. What is the best way to do … Read more
I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real solutions. The equations were derived as the gradients of a sum-of-squares cost function, which I am attempting to … Read more
I’m trying to find a numerical solution to the following optimization problem maximize f(M)=12logdet where A, x_i, a_i are all given. Unfortunately, log-det is concave and log-sum-exp is convex. Edit: I think some background might help. The origin of the objective function is the following function f(V) = \sum_{i=1}^n w_i \, \mathcal{N}(x_i | \, 0, V) … Read more
I was trying to find results about the rate of convergence for the L-BFGS algorithm (in the nonlinear case). What I end up with so far is that the BFGS-Algorithm converges Q-superlinearly this 50 year old Paper characterizing superlinear convergence of quasi-newton methods Theorem 3.5. (and 3.6.) in Nocedal’s Numerical Optimization which do not give … Read more
Say I have a black box implementation of the simplex algorithm given. Even though the worst case complexity is exponential, the implementation is fast for all cases I have tried. Is there a good/systematic way to create an example of inputs which will require exponential execution time? I have tried to create examples similar to … Read more
I have an implicit function and I would like to find the value of $h$ that maximizes $R$, i.e, I want to find $h$ that satisfies $\frac{\partial R}{\partial h} = 0$. The function is, $C=\frac{A}{1+\alpha \times exp(-\beta[\frac{180}{\pi}\arctan(\frac{h}{R})-\alpha])}+10\times log(h^2+R^2)+B$, where $C,A,\alpha,\beta$ and $B$ are constants. What I have done is as following; Let $x=\frac{h}{R}$, we can … Read more
I have noticed that when solving the following matrix-polynomial: N∑k=0CkTk=0 s.t. Ck,T∈RM×M using a numerical technique I can expand on if you wish, this solution is sometimes rather difficult to come by. But say that I can solve the equation system where multiply Ck with scalars sk and then manage to find a solution to this system: … Read more
We have: A∈Rn×m with independent columns, y∈Rn. Moreover, n≫m. Consider the following problem, where the inequality is elementwise: x⋆:=argmin Is it possible to compute x^{\star} by an algorithm of time complexity polynomial in m and space complexity O(m^3) in the following sense: Read the matrix A row by row and the vector y element by … Read more
