23

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: A particular choice of the decision variable $x^\star$ and its corresponding objective value $f(x^\star)$, AND A proof of optimality: A mathematical proof that ...


19

Once you obtain a descent direction $p$ for your objective function $f(x)$, you need to pick a "good" step length. You don't want to take a step that is too large such that the function at your new point is larger than your current point. At the same time, you don't want to make your step too small such that it takes forever to get to converge. Armijo's ...


19

This is most easily seen by considering the stationary Stokes equations $$ -\mu \Delta u + \nabla p = f \\ \nabla \cdot u = 0 $$ which is equivalent to the problem $$ \min_u \frac\mu 2 \|\nabla u\|^2 - (f,u) \\ \text{so that} \; \nabla\cdot u = 0. $$ If you write down the Lagrangian and then the optimality conditions of this optimization problems, ...


19

If what you want is to solve $\min \| Ax - b \|_{2}^{2} + \lambda^{2} \| x \|_{2}^{2}$ subject to $x \geq 0$, then this is easily implemented. Construct a matrix $C=\left[ \begin{array}{c} A \\ \lambda I \end{array} \right]$ and a vector $d=\left[ \begin{array}{c} b \\ 0 \end{array} \right]$. Then use your nonnegative least squares solver on $...


18

Brian is spot on. But I think it is helpful to add some compressed sensing context. First, note that the so-called 0 norm $\|x\|_0$—the cardinality function, or the number of nonzero values in $x$—is not a norm. It is probably best to write it as something like $\mathop{\textbf{card}}(x)$ in anything but the most casual contexts. Don't get me wrong, you're ...


17

As Jed Brown mentioned, the connection between gradient descent in nonlinear optimization and time stepping of dynamical systems is rediscovered with some frequency (understandably, since it's a very satisfying connection to the mathematical mind since it links two seemingly different fields). However, it rarely turns out to be a useful connection, ...


17

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 the derivatives exactly then it is normally best to use that code rather than to use finite difference approximations. Although some optimization libraries ...


16

As Paul states, without more information, it is hard to give advice without assumptions. With 10-20 variables and expensive function evaluations, the tendency is to recommend derivative-free optimization algorithms. I am going to disagree strongly with Paul's advice: you generally need a machine-precision gradient unless you're using some sort of special ...


16

Quasi-Newton methods construct an approximate Hessian for an arbitrary smooth objective function $f(x)$ using values of $\nabla f$ evaluated at the current and previous points. At each iteration of the method the quasi-Newton approximate Hessian is updated using the gradient evaluated at the latest iterate, $x^{(k)}$. These approximate Hessians aren't ...


16

Why do people use the classical least squares approach so often? Primarily, squaring makes the problem twice-differentiable, thus many different solution methods apply (quasi-Newton methods, Levenberg-Marquardt, Gauss-Newton), and there is still some flexibility with respect to what is being squared (e.g., I can replace $x$ with $f(x)$ for a wide class of ...


15

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 in the search direction, but not for how long. To decide how far to go along the search direction, you need extra information (gradient descent with constant ...


14

There are two issues here: Your optimization problem has two competing objectives: maximizing $k=f_1(p_1,p_2)$ and maximizing $t = f_2(p_1,p_2)$. This is known as multi-objective (or multi-criteria) optimization, and such problems have an infinite number of solutions, each based on a specific choice of the relative weight of the objectives (i.e., is it more ...


14

The methods you are looking for -- i.e., that only use function evaluations but not derivatives -- are called derivative free optimization methods. There is a large body of literature on them, and you can find a chapter on such methods in most books on optimization. Typical approaches include Approximating the gradient by finite differences if one can ...


14

Inge Söderkvist (2009) has a nice write-up of solving the Rigid Body Movement Problem by singular value decomposition (SVD). Suppose we are given 3D points $\{x_1,\ldots,x_n\}$ that after perturbation take positions $\{y_1,\ldots,y_n\}$ respectively. We seek a rigid "motion", i.e. a rotation $R$ and translation $d$ combined, applied to points $x_i$ that ...


14

Gradiant descent and the conjugate gradient method are both algorithms for minimizing nonlinear functions, that is, functions like the Rosenbrock function $ f(x_1,x_2) = (1-x_1)^2 + 100(x_2 - x_1^2)^2 $ or a multivariate quadratic function (in this case with a symmetric quadratic term) $ f(x) = \frac{1}{2} x^T A^T A x - b^T A x. $ Both algorithms are ...


14

If you want something open-source, you probably want to try COIN's CBC code (they also have a couple other MILP solvers, like a branch-and-price framework, or SYMPHONY). Gurobi and CPLEX will be considerably faster, and as of the 2011 or 2012 INFORMS meeting, Gurobi was faster than CPLEX (though the performance metrics are of course problem dependent). On ...


14

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 some people want to motivate an optimization algorithm by mentioning a linear solver is a question only they can answer, but I would just ignore that and focus on ...


13

The derivation of the BFGS is more intuitive when one considers (strictly) convex cost functionals: However, some background information is necessary: Assume, one wants to minimize a convex functional $$ f(x) \to \min_{x\in \mathbb R^n}. $$ Say there is an approximate solution $x_k$. Then, one approximates the minimum of $f$ by the minimum of the ...


13

While I haven't seen the exact formulation that you have written down here, I keep seeing talks in which people "rediscover" a connection to integrating some transient system, and proceed to write down an algorithm that is algebraically-equilavent to one form or another of an existing gradient descent or Newton-like method, and fail to cite anyone else. I ...


12

The curvature condition essentially says this: We know that $\nabla f(x)\cdot p < 0$ (because $p$ is a descent direction). So in direction $p$, it goes downhill. Now, we're looking for a minimum, i.e. a point where $\nabla f=0$. That means that we don't want to accept step lengths $x+\alpha p$ where the gradient in direction $p$, i.e., $\nabla f(x+\alpha ...


12

We would love to be able to solve $\min \| x \|_{0}$ s.t. $Ax=b$ but this problem is an NP-Hard combinatorial optimization problem that is impractical to solve in practice when $A$, $x$, and $b$ are of sizes typical in compressive sensing. It is possible to efficiently solve $\min \| x \|_{1}$ s.t. $Ax=b$ both in theory (it can be done in ...


12

The conjugate gradient method is good for finding the minimum of a strictly convex functional. This is typical when you reformulate a nonlinear elliptic PDE as an optimization problem. If you want to learn about it, I recommend you read about the CG method for linear systems first, for which An Introduction to the Conjugate Gradient Method Without the ...


12

Overview You might want to try a variant of the Alternating Directions Method of Multipliers (ADMM), which has been found to converge surprisingly quickly for $l_1$ lasso type problems. The strategy is to formulate the problem with an augmented Lagrangian and then do gradient ascent on the dual problem. It is especially nice for this particular $l^1$ ...


12

Athough Geoff Oxberry's answer addresses computational reasons why it's easier to minimize the sum of squared residuals than the sum of absolute values, it doesn't discuss statistical reasons for preferring the least squares solution. For problems in which measurement errors are independent and normally distributed, the (appropriately weighted) least ...


12

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 problems are of the type "if you do it blindly, you'll only get a couple of digits" (unless you resorted to multi-precision arithmetic with in some cases a huge ...


12

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 system of equations $J(x^{(k)})^{T}J(x^{(k)}) p = - J(x^{(k)})^{T} F(x^{(k)})$ where $J(x)$ is the matrix of partial derivatives of components of $F(x)$ with ...


11

There are a few other ways to do this, with advantages and drawbacks: MPI_WTIME: This is a high resolution wall-clock. It is probably the most `trusted' option; it just works. The downside is that if your program doesn't already use MPI, you'll have to wrap MPI around it (which isn't hard). Use a fortran intrinsic (as you have): This is probably the ...


11

Interior point methods work by following the central path to an optimal solution. When you change the objective function, the optimal solution from the previous version of the problem is far from the central path for the new problem, so it takes several iterations to get back to the central path and furthermore has to return to a fairly well centered ...


11

Genetic algorithms are a very poor choice when the objective function is extremely expensive to evaluate- these methods require a lot of function evaluations in each generation (which parallelism can help with) and a lot of generations (which are inherently sequential.) At two days per generation, this would be very slow. You haven't mentioned where this ...


11

Here is an approximate solution. Since N is so large and M is so small, how about the following: Compute the convex hull of N Select up to M points from the hull that satisfy your maximum distance criteria. If Step 2 leaves you with fewer than M points then select 1 point from the interior that maximizes its distance from the previously selected points. ...


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