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


15

To add to Lutz Lehmann's answer, you can look up the latency for the CPU instructions in this comprehensive table by Anger Fog. For example, on the Intel Ivy Bridge processors: FADD / FSUB (floating point add and subtract) both take 3 cycles FMUL (multiply) takes 5 cycles FDIV (divide) takes 10-24 cycles FYL2X ($y \cdot \log_2(x)$) takes 90-106 cycles F2XM1 ...


14

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

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


11

$\exp$, $\sin$, $\tan$ and their inverse and otherwise related functions are transcendental, defined by an infinite power series. Meaning it takes some effort to evaluate uniformly good approximations. This is done via argument simplification using the properties of these functions, and polynomial approximations, or using quotients of polynomials à la Padé ...


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

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

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

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

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

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

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

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


4

Check out Matrix Market. It has a nice collection of matrices from different areas (fluid dynamics, elasticity, acoustics etc.) So you do not need to assemble systems yourself in order to provide decent test cases. Matrices are provided in ASCII–format (Matrix Market and Harwell–Boeing). I do not know what language your team uses, but you can easily find I/...


4

No, this is not possible. There is a standard way of showing this: The feasible region of your constraints is not convex. For example, $x_{1,1}=1$, $x_{1,2}=0$ is feasible, $x_{1,1}=0$, $x_{1,2}=1$ is feasible, but the midpoint $x_{1,1}=1/2$, $x_{1,2}=1/2$ is not feasible. The feasible set of a system of linear equality and inequality constraints is ...


4

$$\big\| \mathrm A \begin{bmatrix} \mathrm X & \mathrm X^2\end{bmatrix} - \begin{bmatrix} \mathrm B_1 & \mathrm B_2\end{bmatrix} \big\|_{\text{F}}^2 = \underbrace{\| \mathrm A \mathrm X - \mathrm B_1 \|_{\text{F}}^2}_{=: f_1 (\mathrm X)} + \underbrace{\| \mathrm A \mathrm X^2 - \mathrm B_2 \|_{\text{F}}^2}_{=: f_2 (\mathrm X)}$$ Everybody knows that ...


4

If they don't have a variable that is constrained to a discrete set you can formulate it like so: b1 = m.Var(lb=0,ub=1,integer=True) #Binary variable b2 = m.Var(lb=0,ub=1,integer=True) #Binary variable b3 = m.Var(lb=0,ub=1,integer=True) #Binary variable b4 = m.Var(lb=0,ub=1,integer=True) #Binary variable a = m.Var() #Variable ...


4

Below is an example of using Gekko (v0.2.4+) to define a SOS1 variable with an objective function to find the minimum in that sequence of values. from gekko import GEKKO m = GEKKO() y = m.sos1([19.05, 25.0, 29.3, 30.2]) m.Obj(y) # select the minimum value m.solve() print(y.value) Additional information on model building functions is available in the Gekko ...


3

You could try using an optimization formulation to exclude undesirable roots via constraints. However, global optimization is a notoriously difficult problem and solving such a problem deterministically could be challenging. If you can exclude all suboptimal local minima in some way, that would make it easier. For deterministic approaches, you're essentially ...


3

The best reference I've seen on establishing relationships between constraint qualifications is Constraint Qualification for Nonlinear Programming. Since the function $g$ is nonlinear, your problem is likely nonconvex, so the Slater condition will be inapplicable to your problem, but any other constraint qualification should work, as long as you can show it ...


3

If you're optimizing with respect to the $k_{i,j}$, $k_{i,j}$ isn't an argument to the Heaviside function (for each $i, j$), and the $x_{i}$ and $T$ are known parameters, your problem is continuous and (twice continuously) differentiable with respect to $k$. Your problem still looks to be nonconvex at first glance, so deterministic global optimization would ...


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