Questions tagged [optimization]

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

189 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
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 ...
8
votes
0answers
440 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
150 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}_{+}^{...
7
votes
0answers
154 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}(...
6
votes
0answers
233 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
99 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
96 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
96 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
95 views

How to solve a 4th order nonnegative LASSO problem?

I need to solve the following 4th order nonnegative LASSO problem: $$ \min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1 $$ where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
5
votes
0answers
226 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
84 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
158 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
332 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
487 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
42 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 $$...
4
votes
1answer
129 views

An optimization method for bounding the eigenvalues of a unknown non symmetric matrix

Given a positive objective function $f$ that acts on a real-valued matrix $A$, I am interested in the following problem $$\underset{A \in \mathbb{R}^{n \times n}}{\text{minimize}} \quad f(A) \quad \...
4
votes
0answers
67 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
34 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, ...
4
votes
0answers
83 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
375 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 ...
4
votes
0answers
77 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
158 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
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
86 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 ...
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
174 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
407 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
51 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
106 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
48 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
79 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
63 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
165 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
49 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
142 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
86 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
102 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
89 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
115 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
93 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
200 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
74 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
119 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
62 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 ...
3
votes
0answers
2k 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 ...
3
votes
0answers
102 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
175 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
153 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
164 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
90 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(\...