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


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


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


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


12

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


12

tl;dr: My general impression from the literature is that speedups are modest (if they exist). The main kernel you'll see in these methods is a sparse-direct method (e.g., sparse LU, sparse LDLT), and memory accesses are irregular; these characteristics don't favor use of GPUs. Also, parallel IPMs are in their infancy. I still suspect people will work on GPU ...


8

If you introduce a variable $\mathbf z=(\mathbf x^T, \mathbf y^T)^T \in \mathbb{R}^{2n}$, then you can write $f(\mathbf x, \mathbf y)=f(\mathbf z)$ and it fits the exact format you wrote in your outline of the first method and it will all work as described. You just have to match things like $\nabla_z f(\mathbf z) = (\nabla_x f(\mathbf x,\mathbf y)^T, \...


7

Though this does not entirely answer your question, I author a Python package for nonlinear programming named NLPy. The most recent version may be retrieved from https://github.com/dpo/nlpy I must stress that NLPy is research-grade and the solvers included are by no means as robust as more seasoned codes like IPOPT. Moreover, they currently require that ...


7

pyomo is a full GAMS/AMPL-like modeling environment for optimization in python. It is extremely powerful, has interfaces to all solvers that are supported by AMPL, and generates Jacobians etc. automatically. However, due to it running in a 'virtual python environment', it might not be trivial to link it to existing code.


7

If sparsity is preserved, optimal preconditioners are available, and inequality constraints can be resolved by a multiscale method (or the number of active constraints is not too large), the overall algorithm can be $\mathcal O(n)$ time and space. Distributing across a parallel machine adds a logarithmic term to time. If enough sparsity is available, or if ...


7

If $P_i(w)$ is a piecewise linear, convex function, then it can be written as the maximum of a number of linear functions, $P_i(w)=\max \{L_{i1}(w),\ldots,L_{iJ_i}(w)\}$. Then, the optimization problem allows for the reformulation $$ \min_{\mathbf w,\mathbf x} \sum_{i=1}^N c_ix_i = \mathbf c^T \mathbf x, \\ \sum_{i=1}^N w_i = w \\ 0\le w_i \le w_{max}, ...


6

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 with using these solvers is that you normally need to provide at least first derivatives and optionally second derivatives. There are several nice modeling ...


6

Not by itself, no. The optimal solutions of multiobjective optimization problems are Pareto optimal solutions. Multiobjective optimization problems have their own specialized algorithms, as can be seen in the corresponding Wikipedia article. Some of these methods construct surrogate single objective optimization problems, which could be solved with L-BFGS; ...


6

If you have nonsmooth constraints, it is no help that you have a convex quadratic objective. You need a constrained nonsmooth solver. See my web page http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm for suitable software.


6

Popular, simple to implement line search strategies are doubling and backtracking, but they need often more function values than strictly needed. Interpolation schemes as you describe them need safeguards to be efficient, but all (or at least most) currently used schemes are based on some form of interpolation. The most used high quality line search (...


6

This is discussed in great detail in the excellent book by Nocedal and Wright on nonlinear optimization. I can't summarize the method better than they describe it.


6

It looks like you are optimizing over the surface of a ball. That constraint is non-convex, but I think with your objective the solution will always be on the surface, so you can relax it to be $ \leq 1 $ and now its convex - thats a good start. So lets make that change. Now if you ignore the absolute sign, you are maximizing a linear objective over a ball. ...


5

You say in the comment that you cannot get it to work as it is not quadratic enough. I don't see any reason for that. The problem is easily coded as a mixed-integer quadratic program. If I understand your problem definition, you want to constraint the sum of the varables larger than a threshold. Introduce a binary variable indicating if x is larger than a, ...


5

It could be that your optimization problem is very badly conditioned when using only the accelerometer data. In other words, the accelerometer data might not sufficiently constrain the parameters so that many different paths adequately fit the data. In terms of the minimization problem this means that you'd have a large "flat spot" at the minimum of ...


5

If the $s_{i}$ are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred Glover has a sequence of papers to that effect in the mid-to-late 1970s, and subsequent work has built upon it. For example: Fred Glover, "Improved Linear ...


5

If there's no mistake then it's much easier than I thought. We will show that the minimum is equal to the smallest component of $A$, denoted by $a_{i_0j_0}$ where $(i_0,j_0) = \arg\min_{(i,j)} a_{ij}$, and attained when $x_{i_0}=y_{j_0}=1$ and $x_i=y_i=0\quad\forall i\neq i_0,j\neq j_0.$ Indeed, we have \begin{align} x^TAy=\sum_{1\le i\le m}\sum_{1\le j\...


5

A good starting point for this is Boyd and Vandenberghe's textbook, Convex Optimization. I'd strongly encourage you to get a copy (the authors have posted a free .pdf online, so it won't cost you anything, and the hardcover edition from Cambridge University Press is quite reasonably priced.) Begin by Cholesky factoring your symmetric and positive ...


4

PyGMO contains several solvers, providing the same interface to them. IPOPT and scipy slsqp are included in case you compile the code and download/install the third party code independently. As a bonus, parallel use of the solver is made really easy (multistart) via the archipelago class!


4

What about scipy.fmin_slsqp ? http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_slsqp.html


4

We've tried TAO but found it to be not very useful for inequality constrained problems. It's also essentially only in maintenance mode since at least 2003, with no real new features apart from updates to track changes in PETSc upon which it is built.


4

You can't. Optimization and feasibility are equivalent problems, because optimization can be achieved by solving a sequence of feasibility problems.Consequently, both are in the same computational complexity class. In an answer to a similar question you posed I showed that your formulation is nonconvex. Determining feasibility such problems is generally an $\...


4

The difficulty in optimization is finding the location of the minimum, not the value at this point. This is why your scaling makes no difference: the location is exactly the same. Furthermore, every reasonable optimization algorithm should produce exactly the same sequence of intermediate points (iterates) whether you scale the objective function or not. ...


4

The isolated bilinear and trilinear terms make your problem nonconvex. (Occasionally, these terms can be gathered into sums or differences of squares, but that does not appear to be the case here.) If $f$ is a twice continuously differentiable function, and you're interested in deterministic global optimization, you probably want to use a branch-and-bound ...


4

For generic data the optimal value (in the limit) is zero, which is achieved by any vector with arbitrarily large elements. Just pick a random vector $x_0$ and use $x=\alpha x_0$ where $\alpha$ tends to $\infty$. Am I missing something? The eigenvalue discussion you have is not correct (there is no reason that you should be allowed to add the constraint $y^...


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