How can I check for the accuracy of numerical result to optimization problem?

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

Newton’s method

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

Finding optimal hyperplane

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

Software tools for medium-scale systems of polynomial equations

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

Maximizing “log det + log sum exp” function

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

references: L-BFGS rate of convergence

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

How to create an example with exponential running time for a given implementation of the simplex algorithm?

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

how to find the the maximum of an implicit function

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

Numerical “helper solver” to solve polynomial matrix equation system?

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

Efficient algorithm for lower-bound least squares.

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