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

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

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


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

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

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

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

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

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

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

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

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


4

If possible, you want to choose a well-scaled objective for your problem, which would mean de-correlating your parameters as much as possible. For a quadratic approximation to an objective function, correlated parameters correspond to objective function isosurfaces that are ellipsoidal in shape; the ideal shape for isosurfaces would be roughly spherical. In ...


4

Replace $A$ by a factored form from which the determinant can be computed stably and cheaply. E.g., add new triangular variables $L$ and $R$ and the constraint $A=PLR$ for some fixed permutation matrix $P$; often the identity permutation $P=I$ is enough. This means that you treat the nontrivial entries of $L$ and $R$ as additional variables. Then ...


4

If the $R_k$ are your only optimization variables, then the constraint $$ \exp \left[ - (2^{{R}_k } -1) \left(\frac{\tilde{Z} g_{k} p_{\max} + \sigma^2}{g_{pu} p_{pu}} \right) \right] \leq q $$ is equivalent to $$ - (2^{{R}_k } -1) \left(\frac{\tilde{Z} g_{k} p_{\max} + \sigma^2}{g_{pu} p_{pu}} \right) \leq \ln q $$ which is equivalent to $$ (2^{{R}_k }...


4

Not a direct answer to your title question, but I think you are better off attacking this problem from the semidefinite domain instead. Trivial approach is to linearize the objective at some initial guess, solve the linearized problem, perform a line-search along the computed direction, and repeat until the objective doesn't improve. The code below does this ...


4

Adding another answer, as I just realized that the problem is easily solved as a linear SDP. Let $Q=S^TS$ and you have the objective $\mathrm{trace}~Q + \mathrm{trace}~Q^{-2}$. Introduce an upper bound $X\succeq Q^{-1}$ and minimize $\mathrm{trace}~Q + \mathrm{trace}~X^{2}$. At optimality you will have $X= Q^{-1}$. The constraints $X\succeq Q^{-1}$ and $Q\...


4

Based on your current optimization strategy, it is likely you cannot get away with just the gradient of $f(\cdot)$ evaluated at $\frac{\boldsymbol{x}}{\left| \boldsymbol{x}\right|}$ since normalization isn't linear wrt. $\boldsymbol{x}$. However, you could try using chain rule by first assuming that $f(\boldsymbol{u}(\boldsymbol{x}))$ where $\boldsymbol{u}(\...


4

@Stellos already gave the correct answer, but let me try to back it up with a bit of intuition: Think of your function $f(x)$ as a function that would actually make sense for any real-valued argument $x$. Then, if that function happened to be of the form $f(x)=\sin(1000x)$, you would have lots of maxima and minima between each integer point and, in essence, ...


4

It turns out that the problem has quite an elegant solution. Let the hypercuboid be defined by $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ instead of using the more cumbersome $\mathbf{x_{0}}$ and $\epsilon_{i}$ For a hypercuboid to lie within a polyhedron, each of its vertices must lie inside, that is, satisfy the inequality $\mathbf{Ax} \leq \mathbf{b}$....


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