37

I work in a lab that does global optimization of mixed-integer and non-convex problems. My experience with open source optimization solvers has been that the better ones are typically written in a compiled language, and they fare poorly compared to commercial optimization packages. If you can formulate your problem as an explicit system of equations and ...


32

fmincon(), as you mentioned, employs several strategies that are well-known in nonlinear optimization that attempt to find a local minimum without much regard for whether the global optimum has been found. If you're okay with this, then I think you have phrased the question correctly (nonlinear optimization). The best package I'm aware of for general ...


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


22

The associated cost of BFGS may be brought more in line with CG if you use the limited memory variants rather than the full-storage BFGS. This computes the BFGS update for the last $m$ updates efficiently by a series of rank-one updates without needing to store more than the last $m$ solutions and gradients. In my experience, BFGS with a lot of updates ...


22

Probably you ask for a proof that the median solves the problem? Well, this can be done like this: The objective is piecewise linear and hence differentiable except for the points $m=x_i$. What is the slope of the objective is some point $m\neq x_i$? Well, the slope is the sum of the slopes of the mappings $m\mapsto |m-x_j|$ and this is either $+1$ (for $m>...


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


18

I decided to radically edit my answer based on some of the comments. I haven't used TAO. From perusing the documentation, it seems like the only way that TAO can handle constrained optimization problems (excluding the special case of only box constraints) is to convert the problem into a variational inequality using the Karush-Kuhn-Tucker (KKT) conditions, ...


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


18

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


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

Update: see the new GEKKO package that we just released. APM Python is a free optimization toolbox that has interfaces to APOPT, BPOPT, IPOPT, and other solvers. It provides first (Jacobian) and second (Hessian) information to the solvers and provides an optional web-interface to view results. The APM Python client is installed with pip: pip install ...


16

A generalization of this problem to multiple dimensions is called the geometric median problem. As David points out, the median is the solution for the 1-D case; there, you could use median-finding selection algorithms, which are more efficient than sorting. Sorts are $O(n\log n)$ whereas selection algorithms are $O(n)$; sorts are only more efficient if ...


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

In low dimensions, a well implemented BFGS method is generally both faster and more robust than CG, especially if the function is not very far from a quadratic. Neither BFGS nor CG need any assumption about convexity; only the initial Hessian approximation (for BFGS) resp. the preconditioner (for CG) must be positive definite. But these can always be ...


15

Although mixed-integer linear programming (MILP) is indeed NP-complete, there are solvable (nontrivial) instances of mixed-integer linear programming. NP-complete means that mixed integer linear programming is: a) solvable in polynomial time with a nondeterministic Turing machine (the NP part) b) polynomial time reducible to 3-SAT (the complete part; for ...


15

You can circumvent the problem of choosing a small $\epsilon>0$ by being a bit more ambitious: Try to find $\mathbf{x}$ such that $\mathbf{Ax}\leq \mathbf{b}$ and that the smallest entry in $\mathbf{x}$ is largest possible. To that end, introduce a new variable $$\mathbf{y} = \begin{bmatrix} \mathbf{x}\\ \epsilon\end{bmatrix}\in\mathbb{R}^{n+1}$$ (if $\...


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

J.M. is right about storage. BFGS requires an approximate Hessian, but you can initialize it with the identity matrix and then just calculate the rank-two updates to the approximate Hessian as you go, as long as you have gradient information available, preferably analytically rather than through finite differences. BFGS is a quasi-Newton method, and will ...


14

Edit: Let's try this explanation again, this time when I'm more awake. There are three big issues with the formulation (in order of severity): There's no obvious reformulation of the problem that is obviously smooth, convex, or linear. It's nonsmooth. It's not necessarily convex. No obvious smooth/convex/linear reformulation First off, there's no ...


14

If a given nonlinear system is the first order optimality condition for an optimization problem, then we can often produce a more robust algorithm by using that information. For example, consider the equation $$ f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$$ This clearly has a unique minimum and we expect our optimization ...


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

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


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

Simple functions like Rosenbrock's are used to debug and pre-test newly written algorithms: They are fast to implement and to execute, and a method that cannot solve the standard problems well is unlikely to work well on real life problems. For a recent thorough comparison of derivative-free methods for expensive functions, see Derivative-free optimization:...


13

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


13

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


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