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
12
votes
0answers
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 ...
9
votes
0answers
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 ...
8
votes
0answers
160 views

Accelerated convergence for Sparse NMF

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}_{+}^{...
8
votes
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}(...
7
votes
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 ...
6
votes
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 ...
6
votes
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}^...
6
votes
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 ...
6
votes
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]\...
6
votes
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\...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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 $$...
5
votes
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 ...
5
votes
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, ...
5
votes
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*, ...
5
votes
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)$: $$ \...
5
votes
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 ...
5
votes
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 ...
5
votes
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 ...
5
votes
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$$ ...
5
votes
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 ...
5
votes
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 ...
5
votes
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$, ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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 ...
4
votes
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, ...
4
votes
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 ...
3
votes
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....
3
votes
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 ...
3
votes
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_{\...
3
votes
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 ...
3
votes
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$$ ...
3
votes
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]$. ...
3
votes
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 ...
3
votes
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) $...
3
votes
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,...
3
votes
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 ...
3
votes
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 ...
3
votes
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 (...
3
votes
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 ...
3
votes
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,...
3
votes
0answers
125 views

Stochastic gradient descent for large deterministic optimization problems

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 ...
3
votes
0answers
66 views

Relaxing a variable in MIP

I have this MIP optimization problem, with couple of binary variables; however when I relax one of the binary variables the optimal solution of the objective does not change. But the solving time ...

1
2 3 4 5