33
votes
stupid + stupid = brilliant in scientific computing
In W. Kahan, "Interval arithmetic options in the proposed IEEE floating point arithmetic standard". In: Karl L. E. Nickel (ed.), Interval Mathematics 1980, New York: Academic Press 1980, pp. ...
- 1,865
27
votes
Accepted
Why should non-convexity be a problem in optimization?
The misunderstanding lies in what constitutes "solving" an optimization problem, e.g. $\arg\min f(x)$. For mathematicians, the problem is only considered "solved" once we have:
A candidate solution: ...
- 2,485
26
votes
stupid + stupid = brilliant in scientific computing
Consider the constrained optimization problem
$$\min_x f(x) \quad\text{s.t. } g(x) = 0$$
where, to make things nice, we'll assume $f$ is convex and $g$ has convex level sets.
There are two bad ways to ...
23
votes
Accepted
How do I find the minimum-area ellipse that encloses a set of points?
Theory
The 1997 paper "Smallest Enclosing Ellipses -- Fast and Exact" by Gärtner and Schönherr addresses this question. The same authors provide a C++ implementation in their 1998 paper &...
- 3,961
17
votes
Is providing approximate gradients to a gradient based optimizer useless?
If your objective is smooth, then using finite difference approximations to the derivative is often more effective than using a derivative free optimization algorithm. If you have code that computes ...
- 18.7k
17
votes
Accepted
Why aren't Krylov subspace methods popular in the Machine Learning community compared to Gradient Descent?
On a basic level, I don't buy the argument that you have to "solve a linear system for many machine learning algorithms". Much more, you usually have to optimize a non-linear equation which ...
- 3,127
17
votes
stupid + stupid = brilliant in scientific computing
Disclaimer: stupid is in the eyes of the beholder.
For decades, it seemed like what would now be known as deep learning was combining stupid with stupid.
Stupid 1: over parameterization. A rule of ...
- 271
15
votes
Accepted
Adaptive gradient descent step size when you can't do a line search
I'll begin with a general remark: first-order information (i.e., using only gradients, which encode slope) can only give you directional information: It can tell you that the function value decreases ...
- 12.3k
15
votes
Accepted
What are the differences between the different gradient-based numerical optimization methods?
First, you should forget about solving linear equations for the moment -- that's a different context from optimization, and trying to consider both on equal footing will only lead to confusion. Why ...
- 12.3k
14
votes
Accepted
Beating typical BLAS libraries matrix multiplication performance
Consolidating the comments:
No, you are very unlikely to beat a typical BLAS library such as Intel's MKL, AMD's Math Core Library, or OpenBLAS.1
These not only use vectorization, but also (at least ...
13
votes
Accepted
How Jacobian matrix helps optimization faster?
You haven't told us exactly what optimization routine you're using, so it's difficult to provide a very specific answer to your question.
However, if you don't supply your own Jacobian function ...
- 18.7k
13
votes
Accepted
How to find the smallest ellipse covering a given fraction of a set of points?
You asked for the smallest ellipse. An ellipse so small that its smallestness needs to be italicized. Others have provided answers that identify smallish ellipses, but, as Miracle Max says, "...
- 3,961
12
votes
Accepted
Scientific Programming Contests
I don't know of any current contests, but you can definitely have a look at the SIAM 100-digit challenge. It's a set of 10 problems for which the contest required 10 correct digits per problem. All ...
- 6,179
12
votes
Accepted
When and when not to use automatic differentiation
Given code that computes a function $f(x)$, automatic differentiation tools produce a code that can compute $f(x)$ and its derivatives at the same time. Solving a differential equation is an entirely ...
- 18.7k
11
votes
Accepted
Is providing approximate gradients to a gradient based optimizer useless?
To complement Brian's excellent answer, let me give a bit of (editorial) background. Derivative-free optimization methods are defined as methods that only make use of function evaluations, and are ...
- 12.3k
11
votes
Finding the first N roots of transcendental equation
This is a root-finding problem for an analytic function over a single dimension. One standard technique is to approximate $F(k)$ as a polynomial $F(k) \approx c_0 + c_1 k + c_2 k^2 + \cdots$ using a ...
- 2,485
11
votes
What is required of the objective function in order to use Gauss Newton method?
Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem
$\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$
with the search direction $p$ computed as the solution to the linear ...
- 18.7k
11
votes
Accepted
Arbitrary Precision Optimization Libraries?
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 ...
- 12.3k
11
votes
Accepted
How does the number of function calls in BFGS scale with the dimensionality of space?
That very much depends on your objective function. If you know that your objective function is highly multi-modal and complex, then BFGS is only going to give you a local minimum. If that is enough ...
- 401
10
votes
Accepted
Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$
Since the optimization problem has a well-known closed-form solution, it is rarely used in itself and hence usually not given a name. The objective function $x^TAx$ (using $\|x\|=1$), however, is ...
- 12.3k
10
votes
How do I find the minimum-area ellipse that encloses a set of points?
With your formulation of the constraints, you can only produce ellipses where the semi-major and semi-minor axes are aligned with the coordinate axes, but it's clear from the figure that you attached ...
- 10.3k
10
votes
Accepted
Poor test functions for optimization
Your suspicion that many algorithms rely on specific position of the global optimum is well founded - even if it’s by symmetry only.
Most of the classical test functions found in the literature suffer ...
- 401
9
votes
Is there a high quality nonlinear programming solver for Python?
We recently released (2018) the GEKKO Python package for nonlinear programming with solvers such as IPOPT, APOPT, BPOPT, MINOS, and SNOPT with active set and interior point methods. One of the issues ...
- 506
9
votes
Accepted
Lack of quadratic convergence in Newton's method
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" ...
- 2,155
9
votes
Accepted
Convexity of Sum of $k$-smallest Eigenvalue
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?
$$...
- 2,206
9
votes
Accepted
When training a neural network, why choose Adam over L-BGFS for the optimizer?
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 ...
- 2,206
8
votes
What's the fastest software(open source) to solve mixed integer programming problem
If you want to try a bunch of different solvers, give Julia's JuMP modeling framework a try. It lets you write your model as a JuMP model, and then switch out the solvers with one line of code. For ...
- 12.3k
8
votes
Accepted
Subgradients of non-convex functions
The fact that $x^*$ is a (global!) minimizer of $f$ if and only if $0\in\partial f(x^*)$ is already fully explained in the notes you linked to -- it's really that simple, but here's the argument again ...
- 12.3k
8
votes
Why should non-convexity be a problem in optimization?
An example of a tricky low dimensional problem could be:
Given you hit a local minima, how can you be sure it's anything close to as good as the global minima? How do you know if your result is a ...
- 4,238
8
votes
Accepted
Can floating point error (in FFTW3) cause non-deterministic behavior?
Non-reproducible behaviors in computing amidst different runs can involve several mechanisms, sometimes mixed. They can be especially sensitive when one iterates calculations on large sets of data, ...
- 466
Only top scored, non community-wiki answers of a minimum length are eligible