# Questions tagged [optimization]

This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.

218 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3k views

### Optimized open source BLAS / LAPACK package

I was wondering what is a more optimized open source BLAS/LAPACK package with respect to modern multi-core processors (Haswell and beyond). Is there any distribution that can attain performance close ...
443 views

### What's a good numerical/optimization software package for solving the 2-D optimal stopping problem?

I am looking for a numerical software package to help me solve the 2-dimensional "free boundary" PDEs that arise in optimal stopping problems. In one dimension a standard optimal stopping problem in ...
160 views

In the Non-Negative Matrix factorization (NMF), you basically compute an approximation of a given matrix $V \in \mathbb{R}_{+}^{n \times m}$ into matrices $W$ and $H$ such that $W \in \mathbb{R}_{+}^{... 0answers 159 views ### Fast algorithms to solve Markov Decision Processes In my master thesis I used an Algorithm called Approximative Dynamic Programming [1] to solve equations of the form $$\max_{\pi}\mathbb{E}^{\pi}\left\{\sum_{t=0}^{T}\gamma^tC_t^{\pi}(S_t,A_t^{\pi}(... 0answers 3k views ### Good C++ optimization library for BFGS To implement maximum likelihood estimators, I am looking for a good C++ optimization library that plays nicely with Eigen's matrix objects. Eigen has some capability of interfacing of its own but if ... 0answers 82 views ### continuous analogues of Newton's method Suppose we want to minimize some convex functional J(u) where u lives in some Banach space V. The classical Newton method$$\mathrm d^2J(u_n)(u_{n + 1} - u_n) = -\mathrm dJ(u_n)$$can be viewed ... 0answers 585 views ### Best way to add a positivity constraint to Newton's Method So given an objective function f({\bf x}), I would like to include a positivity constraint when I perform the fixed point iteration:$${\bf x}^{(t+1)}={\bf x}^{(t)} - \text{H}_f^{-1}\nabla f({\bf x}^... 0answers 252 views ### Linear vs Non Linear inverse problems: Does non-linearity help? This is not a typical question with a deterministic answer. If this is not the right place, feel free to close it. For the past one year I have been working on various kinds of inverse problem. Most ... 0answers 102 views ### Reference request for numerical variational method I have a variational problem where the unknown function is a periodic path$\gamma:[0,1)\to\mathbb{R}^2$, and the functional is $$\int_0^1\left( \tfrac12\|\dot\gamma(s)\|^2 + \mathcal{F}[\gamma]\... 0answers 98 views ### Benchmarks or generic configurations for optimal flow control I am about to test my algorithms for solving optimal control problems of type: Find an input u, such that for a time interval (0,T] the cost functional$$J(v,u) = \mathcal M(v(T)) + \int_0^T\... 0answers 87 views ### How to find a lot of (if not all) local minima / critical points of a function? Briefly stated, I would like to find "all" local minima / critical points of a function. This function comes from the discretization of a continuous problem with infinitely many degrees of ... 0answers 81 views ### Can automatic differentiation be used on the parameters of an optimization problem? If I wanted to perform an optimization using a Newton-based solver where the Hessian and gradient of a function are known analytically, and then use a package such as Adept to compute a Jacobian ... 0answers 134 views ### Inverse problem with uncertain forward operator Suppose I want to solve a linear inverse problem. In this example we take a convolution with the kernel: $$\frac{1}{(y^2+z^2)^{3/2}}$$ We only take a fixed$z$for the computation and convolve with ... 0answers 32 views ### Optimization for sampling multiple points of maximized minimum distance I'm trying to find a way to sample new points that have maximum minimum-distance (maximin distance). The current situation is where there are ns number of pre-existing sample points. I want N number ... 0answers 50 views ### Nonlinear least squares optimized Jacobian calculation I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes: $$\min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2$$... 0answers 105 views ### Minimum of quadratic assignment (QAP) with convex objective Suppose$A,B\succeq0$and$C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem: $$\min_{\textrm{permutation matrices }P} \mathrm{tr}(BP^\top AP+C^\top ... 0answers 35 views ### Stochastic conjugate directions to improve convergence in narrow valleys My question concerns a specific statement in this paper: N. N. Schraudolph and T. Graepel, "Conjugate Directions for Stochastic Gradient Descent," in Int. Conf. Artificial Neural Networks, Berlin, ... 0answers 87 views ### What Derivative-free optimization method should I use when my initial guess is very good? I am trying to minimize a function where my initial guess is quite close to the minimum. I'm trying to minimize$$f(q) = \text{angle}(qw_1q*, v_1) + \text{angle}(qw_2q*, v_2) + \text{angle}(qw_3q*, ... 0answers 314 views ### conjugate gradient for Newton's method with non positive definite Hessian matrix I want to minimize a non-linear function$f(x)$using Newton's method. At each optimization step, I compute a descent direction$d$to update$x$using a second-order approximation of$f(x)$: $$\... 0answers 87 views ### Minimize interesting objective function with knowledge of gradient nonlinearity? I plan on using a Quasi-Newton method (L-BFGS) to minimize a non-linear objective function.$$ f: \mathbb{R}^n \rightarrow \mathbb{R}$$The gradient is kind of interesting: as the values of the ... 0answers 424 views ### Optimisation of matrix exponential I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ... 0answers 171 views ### How to optimally choose points for multivariable Hermite interpolation? I have a multi-variate, continuous function f from R^n to R, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ... 0answers 411 views ### Optimization on the manifold of stochastic matrices So I have an optimization problem of the form$$\text{maximize}\hspace{3mm}f(A):{\bf R}^{K\times K}\rightarrow{\bf R}\text{subject to}\hspace{19mm}A^T{\bf 1}=\bf{1}\hspace{33mm}A\geq 0$$... 0answers 97 views ### Graph optimization for parallel processing Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color: The structure can be represented by a weighted undirected graph (images ... 0answers 1k views ### Using MINPACK for curve fitting: implementation? I need to implement a non-linear fitting algorithm in Fortran and chose to use MINPACK's flavor of the Levenberg-Marquardt algorithm as a basis for the least-squares stuff. However, I seem to ... 0answers 434 views ### Why is my lower convex hull extraction algorithm not working? Recently, I wrote an algorithm to obtain a delaunay triangulation of a random point set in I=[-10,10]x[-10,10] \subset R^2 by projecting these points onto the 3 dimensional paraboloid z=x^2+y^2, ... 0answers 64 views ### Optimize linear equation using inner products and subject to L1 norm I have a linear system of the form A x = b where A and b are known, A is "square", and \lvert b \rvert_1 = \lvert x \rvert_1 = 1. Unfortunately, I am working in a framework that ... 0answers 72 views ### Fast approximate solver for vehicle routing problem I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ... 0answers 66 views ### Given a list of intervals, find region that is contained by the largest number of those intervals Start with 1d case. Say I have lots of 1d intervals [s_i, e_i] and I want to find an interval [s^*, e^*] to maximise the count of interval i such that [s_i, e_i]\supseteq [s^*, e^*]. 1d case ... 0answers 262 views ### Nonlinear least squares and regularization Consider the nonlinear least-squares minimization of a vector of n residuals \mathbf{f} in p parameters \mathbf{x}:$$ \min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2 $$This can be done with ... 0answers 79 views ### Calculus of Variations with unknown cost function but some data I have a problem that I've framed out in a particular way, but I don't know if I'm re-inventing the wheel here. Is there an existing literature base in this problem? Does it have a corresponding term ... 0answers 163 views ### Eigenvalue-style optimization with quadratic constraints Suppose A\in\mathbb{R}^{n\times n} is symmetric and positive definite and that we have several symmetric matrices B_i\in\mathbb{R}^{n\times n} that are low-rank and indefinite. I need an ... 0answers 73 views ### Is there a term for Goodhart's Law in the context of optimization? Let's say I'm optimizing something. To pick an arbitrary example, let's say I'm choosing the shape of some part to maximize strength-to-weight ratio. So I get some FEM software, parametrize the shape, ... 0answers 175 views ### Find maximum distance between elements given constraints on some I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ... 0answers 54 views ### What is this QR-factorization-based preconditioning called? I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization.... 0answers 69 views ### Methods to approximate obective function gradients from point cloud Problem statement: Assume that I have an objective function f(x) which takes as input a D-dimensional vector x\in\mathbb{R}^D, and that f(x) is sufficiently smooth. Assume further that I ... 0answers 109 views ### A maximization problem, with motivation in machine learning Consider the minimization problem described this paper. Let f_{\lambda} be the minimizer. As a part of extending my work, I am able to show the following facts$$\lim_\limits{\lambda \to 0}\|f_{\... 0answers 49 views ### Constraint solver vs Bayesian optimizer for fast discontinuous processes I have a complex domain-specific process that accepts inputs: 10-500 inputs, where each input is of type: enum: choice between multiple string or numeric values int: integers float: floating point ... 0answers 94 views ### Solve ODE with non-negative and maximization constraints My task is to solve $$\eta_k\frac{d^2C_k}{dz}(z)=-e_k, k = 1,2,3$$ $$C_k\ge0$$ $$C_1(0)=0, C_2(0)=A, C_3(0)=0$$ $$C_1(L)=B, \frac{dC_2}{dz}(L)=0, \frac{dC_3}{dz}(L)=0$$ with $$e_1 = -\beta_1-\beta_3$$ ... 0answers 53 views ### Nonlinear functional optimization in radial coordinates I am currently implementing classical density functional theory for a radially symmetric system. In mathematical terms, I am searching for a function$f(r)$that minimizes a functional$\Omega[f]$. ... 0answers 242 views ### Difference between Dishonest Newton method and Very Dishonest Newton method What is the difference between the Dishonest Newton method and the Very Dishonest Newton method? Is there a difference or do they mean the same thing? I have tried searching for this on the internet ... 0answers 91 views ### Inconsistency in optimize.minimize I am trying to fit a time-dependent curve at each time step. I do so in minimizing along$x_c$the quadratic error between the curve and a reference solution$ 1/(1 + \exp\left(\sqrt{S}(x-x_c)\right) $... 0answers 104 views ### Are the No Free Lunch Theorems Useful for Anything? I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,... 0answers 94 views ### How to optimize for decay constant in exponential-like function? I've got a data set of points$M_O .. M_N$for time points$t_0 .. t_N$, where$N$is approximately 10-20, and the spacing of time is not uniform (i.e.,$t_{i+1}-t_i$is not constant for all i). It is ... 0answers 118 views ### Optimization Problem: Minimize the absolute value of a set of points I have the following optimization problem: Given is a set of$n$points$x_i, \ldots, x_n$with$x_i \in \mathbb{C}, \|x_i\| < \infty$. Note that$n$is usually not large, i.e.$n < 1000$. We ... 0answers 96 views ### Minimize number of rectangles that cover all the points I have a 2d distribution of moving points with known trajectories represented in a 640x480 image. Here is the initial state: I have to find the minimum number of rectangles with fixed dimensions (... 0answers 203 views ### Optimal Control using Dynamic Programming - Optimizing for Furthest Distance So I have been investigating a problem to get a glider with control of its elevator to fly as far as possible from any given initial state. To keep this simple, we will view this in 2D space with the ... 0answers 75 views ### linear relaxation of an optimization problem I'm reading an article lately, and there is one point which confuses me. So, we have the following constrained binary quadratic problem. min$x^{T}Qx$with the constraints that$Ax≤b$and$x\in {0,...
The Wikipedia page for SGD describes optimizing a function $f = \sum f_i(\theta;x_i)$ by successively approximating gradients from random subsets of the data, while most literature poses the problem ...