Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

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

8
votes
0answers
2k views

Best 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 ...
8
votes
0answers
427 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 ...
7
votes
0answers
133 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}_{+}^{...
6
votes
0answers
104 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 ...
6
votes
0answers
279 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$$ ...
6
votes
0answers
203 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
96 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]\...
5
votes
0answers
86 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
77 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
92 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
148 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}(...
4
votes
0answers
76 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*, ...
4
votes
0answers
72 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,...
4
votes
0answers
105 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 ...
4
votes
0answers
58 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 ...
4
votes
0answers
1k views

Understanding MATLAB's `fmincg` optimization function

I'm researching numerical optimization. Recently I've come across a variant of a conjugate gradient method named fmincg. The function is written in MATLAB and is ...
4
votes
0answers
299 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}^...
4
votes
0answers
73 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
70 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
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 ...
4
votes
0answers
173 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 ...
4
votes
0answers
382 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$, ...
3
votes
0answers
56 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 ...
3
votes
0answers
58 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 ...
3
votes
0answers
47 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
97 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
31 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, ...
3
votes
0answers
73 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
97 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
240 views

Using C/C++ for Markov chain Monte Carlo (MCMC) methods

I'm working on optimizing the parameters of a mathematical model to fit experimental data, using an existing formula for the likelihood of observing the data given a set of parameter values. At the ...
3
votes
0answers
84 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
97 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
84 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
192 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
251 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 ...
3
votes
0answers
93 views

Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
3
votes
0answers
90 views

A least square problem with a fixed mean constraint and a subspace constraint

Let $V_1,\ldots,V_n$ be $n$ vector subspaces of a Hilbert space, $y_i\in V_i$ for each $i$ and $\overline{x}$ be a fixed vector. I want to solve the optimization problem: \begin{equation*} \begin{...
3
votes
0answers
87 views

Finite difference method for coupled PDEs: optimizing performance (time step, iterations per step)

I'm solving coupled PDEs using finite difference method: Incompressible Navier-Stokes and the divergence-free induction equation (Maxwell's equations) with non-uniform electrical conductivity. The ...
3
votes
0answers
63 views

“Solution path” for quadratic program as regularizer changes

I am solving a quadratic program with regularization parameter $\alpha\geq0$ to get the solution to a problem of the form $$ p(\alpha):= \arg\min_{p\in\mathbb{R}^n}\ [\alpha(v^\top p)+f(p)], $$ where $...
3
votes
0answers
157 views

Solving a nonlinear poisson equation via variational minimization

I am kind of new in finite elements and I am solving simple "Poisson nonlinear" problem. $- \nabla ((1 + u^2) \nabla u) = f$ $u = 0 \ \text{on} \ \Omega $ I am using Newton solver, where I have ...
3
votes
0answers
147 views

Reference Request: Variational Problem

I want to solve approximately the following variational problem: Given a function $c:[-1,1]^2\rightarrow [0,1]$, constants $p_1...p_n\in \mathbb{R}^+$, $\alpha_1...\alpha_n\in \mathbb{R}$, and $\...
3
votes
0answers
135 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 ...
3
votes
0answers
134 views

Find constrained vectors maximizing angles between them - methods?

This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
3
votes
0answers
87 views

How to implement conjugate gradient method to minimize this nonlinear action?

Given a 2D stochastic differential equation: \begin{align} \dot{x}_{i}=f_{i}(\textbf{x})+g_{ij}\xi_{j}(t), \end{align} where $i=2$, $g_{ij}g_{jk}=2\epsilon\delta_{ik}$ and $f(\textbf{x})=-\nabla\phi(\...
3
votes
0answers
88 views

Maximizing slow multi-parameter function

What's the best method to maximize the value of slow multivariate function? Here is what I know about the function: Number of parameters is ~ 10. It takes considerable amount of time to compute the ...
3
votes
0answers
68 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 ...
3
votes
0answers
895 views

Polynomial Fitting with Least Squares using Numpy and Scipy

I am trying to fit data to a polynomial using Python - Numpy. The points, with lines sketched above them are as in the picture. I am trying to fit those points to a polynomial of 4. or 5. degree. ...
3
votes
0answers
72 views

Why not use this simpler variant of Stepwise Regression?

In stepwise regression, you step predictor by predictor, each time selecting the one with the greatest correlation with the measurement, subtracting greedily to leave a residual with no correlation to ...
3
votes
0answers
55 views

Partitioning Data for Multiple Regression Lines

We're all familiar with traditional least-squares method for constructing a straight line through a set of data points. The question is: suppose I show you a scatter plot which clearly is suggestive ...
3
votes
0answers
277 views

How much better a bounded BFGS is compared to augmented Lagrangian method with BFGS?

I mean, in handling boxed constraints? In terms of stability, and more importantly, the numerical performance? I have already written some well-optimized and well-tested C/CUDA/C++ codes for ...