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

learn more… | top users | synonyms

0
votes
0answers
19 views

Maximize sum of Rayleigh quotients

I want to maximize the sum of Rayleigh quotients: $$\max_x\sum_{i=1}^n\frac{x^\top A_i x}{x^\top B_i x}$$ where $A_i$ and $B_i$ is positive definite. I've found a similar question here: minimization ...
0
votes
0answers
23 views

State of the art in pseudo-boolean optimization

Pseudo-boolean optimization is known to be NP-hard. What is the current state of the art (how many variables, interaction parameters) in solvers for pseudo-boolean optimization problems? What is the ...
0
votes
0answers
10 views

Max weighted subset (max sum diversification)

Given a set of elements $V$, with known cost $\pi_S$ for each subset $S \subset V$ and a monotone increasing function on the subsets $f(S)$ . I'm wondering if there is a pseudo-polynomial algorithm ...
2
votes
1answer
24 views

Combinatorial optimization problem: choose a set of corrective factors to make a set of points most closely resemble a plane

Apologies in advance if this has already been asked before (I suspect it has, but I'm not experienced to know what to call it, or how to classify this problem). Given a set of $m$ points in space, ...
2
votes
2answers
105 views

How many generations does it typically take for a differential evolution method to reach a global optimum?

For differential evolution methods in optimization, how many generations does it typically take to reach a global optimum? How do we know if the values are never going to converge?
3
votes
2answers
162 views

Parallel optimization algorithms for a problem with very expensive objective function

I am optimizing a function of 10-20 variables. The bad news is that each function evaluation is expensive, approx 30 min of serial computation. The good news is that I have a cluster with a few dozen ...
1
vote
1answer
79 views

How does the number of iteration until optimization begins depends on the dimension of the problem?

I am optimizing a function of 10-20 variables by running algorithm such as BOBYQA and a few other derivative-free algorithms. The bad news is that each function evaluation is very expensive, approx 30 ...
1
vote
3answers
80 views

Minimize quadratic form with equality constraints

I want to minimize function: $f(x) = x^T \cdot A \cdot x + b \cdot x$ given constraints: $B \cdot x = 0$. Here: $x$ is a vector ($x \in \mathbb{R}^n$), $A$ is a matrix of size $n \times n$, $b$ ...
1
vote
2answers
61 views

Solving a minimization problem with “scaled” equality constraint

Given a symmetric positive semi-definite matrix $Q\in\mathbb{R}^{n\times n}$, a vector $v\in\mathbb{R}^n$, a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in \mathbb{R}^m$ I'd like to solve the ...
4
votes
1answer
89 views

Finding a global minimum of non-convex quasi-smooth function that is costly to evaluate

I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my ...
0
votes
0answers
28 views

Sequence optimization for multithreading

Given a list of object I must compute an expensive operation on any couple of object of the list. So I need to create a sequence of tasks. I want to find the sequence of tasks such that there is the ...
4
votes
1answer
44 views

Does the amount of correlation of model parameters matter for nonlinear optimizers?

I am using nonlinear optimizers such as BOBYQA to train a model with 10-20 parameters. It so happens that some of the parameters have high correlation. Roughly speaking, imagine that you are fitting ...
8
votes
1answer
65 views

Method to quantify geometric difference of two dissimilar meshes

I am looking for a method or algorithm to produce a value that describes how different two meshes are geometrically but that have different topologies. An example would be some CAD data that has had ...
2
votes
2answers
87 views

fastest and most efficent way to count all combinations in many sets and sum them together

I am a Java programmer who has reached the limits of brute computer power. My relational database (and non relational databases) is not producing results quick enough and I have hit a bottleneck in ...
3
votes
1answer
81 views

How to solve this optimization problem with abs object function?

Helo, every one. May I ask for help about how to solve this problem. $\begin{align} & \text{max}_{x_i} \quad |\sum_{i=1}^{4} a_i x_i | \\ & s.t. \quad \sum_{i=1}^4 x_i^2=1 \end{align} $ ...
4
votes
0answers
125 views

Are there improved method of computing the following expression?

given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following ...
2
votes
1answer
84 views

Is there a relatively simple way to extract the Jacobian from a Runge-Kutta 4/5 integrator?

I have a RKF45 numerical integrator that simulates polymerization of proteins using CUDA. It does so by tracking the populations of discrete length polymers, e.g. monomers, dimers, trimers, etc. all ...
1
vote
1answer
45 views

optimising changing the range of integers from random number generation

I'm looking to find the most efficient way to change integers from a random number generator to a different inclusive number range. I know of 2 ways so far: Change the number into a decimal in the ...
1
vote
2answers
96 views

Solving a system of polynomial equations with multiple variables

I have a system of equations of the form: $$ l_i^T l_j \cdot m_i^T m_j - m_i^T R l_j \cdot l_i R^T m_j = 0$$ where $R \in \mathbb{R}^{3\times3}$ is an unknown rotation matrix. $l_i, l_j, m_i, m_j \in ...
0
votes
1answer
42 views

How to find max and min bounds of a uncertain function

First I would like to say that I have searched the for uncertain fitting, robust fitting, linear optimization, convex optimization, etc. But I'm lacking the knowledge to solve this problem, and I need ...
4
votes
6answers
422 views

Minimisation problem in thousands of dimensions

I need to find the minimum of a function (a log-likelihood from a Potts model) in tens of thousands of dimensions. The function evaluation is quite fast, takes about $10^{-3} s$, and there is a ...
1
vote
2answers
79 views

Maximum function evaluation with NLOPT in Python

I am having an issue with the implementation of NLOPT in Python. My objective is to minimize a somewhat complicated Maximum Likelihood function. My function is called mle and there are 6 parameters ...
0
votes
1answer
46 views

Gradient descent on the PDF of the multivariate normal distribution

I want to perform gradient descent optimization of the probability of a sample under a multivariate normal probability density function. For your convenience I state the PDF here: ...
2
votes
1answer
131 views

How to test convergence of an algorithm for constrained optimization

I am applying an iterative method (projected newton) to an optimization problem. Theoretically, the method should converge linearly. I would greatly appreciate it if you could share how should I test ...
4
votes
1answer
138 views

Pre calculate mathematical expressions in Fortran 90

Is there some flag to let the Fortran compiler pre calculate a math expression before compiling it?. I have to write expressions that contain many small 4x4 matrix multiplications. The thing is, most ...
6
votes
2answers
219 views

Understanding the cost of adjoint method for pde-constrained optimization

I'm trying to understand how the adjoint-based optimization method works for a PDE constrained optimization. Particularly, I'm trying to understand why the adjoint method is more efficient for ...
2
votes
1answer
106 views

Levenberg-marquardt: How to calculate the jacobian with fixed parameters

So I'm working on a fitting algorithm using the levenberg-marquardt algorithm and I'm a bit stumped as to how to handle fixed parameters. Looking around at other code, like the minpack version of the ...
9
votes
2answers
175 views

Is it well known that some optimization problems are equivalent to time-stepping?

Given a desired state $y_0$ and a regularization parameter $\beta \in \mathbb R$, consider the problem of finding a state $y$ and a control $u$ to minimize a functional \begin{equation} \frac{1}{2} ...
1
vote
0answers
47 views

Question about ellipsoid method

I have some technical question concerning the ellipsoid method Referring to the paper : http://paswkshop.comm.utoronto.ca/~weiyu/01658226.pdf It is mentioned in p.1317 at the last line in the left ...
3
votes
1answer
65 views

State-of-the-art for active set optimization algorithms?

Given a problem like this: $$ \text{min } ||Ex-f|| \text{ s.t.}$$ $$ Gx \ge 0$$ $$ Cx = d $$ And assuming that the matrices are medium sized (dimensions in the low thousands) and dense, what's the ...
0
votes
1answer
69 views

enhancing a MIP formulation of Ising model

I want to construct a MIP formulation for Ising model. For simplicity, I will only include terms involving nearest-neighbor pairs and triangular terms. I propose one formulation and ask whether there ...
1
vote
1answer
77 views

How can a quadratic positive definite minimization be unbounded [closed]

I am minimising a diagonal quadratic matrix using CPLEX. All off diagonal elements are zero. It has 500 variables and 20 linear constraints plus each variable is constrained to be within 0 and 1 All ...
1
vote
2answers
63 views

Unconstrained optimization learning and programming resources

I have a working knowledge of calculus and have been able to understand the application of Newton-Raphson technique for unconstrained optimization. Please point me to some of the easy to understand ...
4
votes
1answer
153 views

Python: Multistart optimization using parallel programming

[I previously asked my question on StackOverflow but this site may be more appropriate] In Matlab, I am currently using the MultiStart as an optimization algo in a parallel setup for a computer ...
0
votes
0answers
57 views

Algorithm for Octree for nearest neighbor seach

Problem Statement: To find the nearest GRID ID of each of the particles using Octree. I have a system of particles(~6k, movable, Fig 1) for which I need to check which grid point (rigid; in ...
3
votes
2answers
84 views

A separable nonnegative quadratic program

I have spent quite some time trying to solve the following quadratic program: $$\min \sum_{i=1}^n (\frac{1}{2}x_i^TQx_i+c_i^Tx_i), \quad \mathrm{s.t. } \quad x_i\ge 0 \quad \forall i,$$ where $n$ is ...
4
votes
1answer
54 views

Iteratively refine bounds on exp for Metropolis criterion

In Monte Carlo simulations, using the Metropolis criterion, one often has to compare a random number $a$, $0 \leq a < 1$, to the Boltzmann distribution $exp(-\beta\Delta E)$, where $\Delta E$ is ...
0
votes
0answers
24 views

Particle Collision to Static paticles

I have a system of particles with equal distance with each other and another at random positions which is moving with time. I want to know: a) The method by which I can reduce the number of particles ...
0
votes
0answers
23 views

Discrete Matrix Completion Problems

I am looking for matrix completion problems where the values of the matrix are discrete, say from a categorical distribution. I have found a few reference, such as this, but this too recent. I am ...
0
votes
3answers
156 views

Looking for ways to speed up the numeric evaluation of a symbolic expression in Matlab

{Summary: I have a symbolic expression DCritnF expressed in terms of two variables x1 and x2. I need to find it's numeric value and I used combination of double and subs as given below. ...
4
votes
1answer
130 views

Maximum Likelihood Estimation for State Space Models using BFGS

I have written some code that can do Kalman filtering (using a number of different Kalman-type filters [Information Filter et al.]) for Linear Gaussian State Space Analysis for an n-dimensional state ...
1
vote
0answers
81 views

Estimating the parameters of the DACE stochastic model (EGO optimization algorithm)

Good day. I am trying to implement the EGO optimization algorithm. The algorithm itself is rather long to describe here in full. It is presented here, with another example of usage here. But before ...
2
votes
0answers
118 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. ...
2
votes
1answer
102 views

How do I simultaneously minimize two different functions who have the same inputs?

I want to minimize two different functions simultaneously who have the same inputs. The functions are both linear and non-exponential. $$F_1(X_1, X_2) = a_1X_1 + a_2X_2$$ $$F_2(X_1, X_2) = b_1X_1 + ...
2
votes
1answer
141 views

Optimal numerical method for optimization of “Rosenbrock Banana”-like function

Which numerical methods would be optimal to find an extremum of a function with an almost flat "valley" (but a single minimum in the middle of the valley)? In this context optimal means the least ...
6
votes
1answer
153 views

Help deciding between cubic and quadratic interpolation in line search

I'm performing a line search as part of a quasi-Newton BFGS algorithm. In one step of the line search I use a cubic interpolation to move closer to the local minimizer. Let $f : R \rightarrow R, f ...
0
votes
2answers
109 views

Matlab fmincon with zero user-supplied hessian

I have to solve the problem $$\min_x 1^Tx+\frac{\lambda}{2}\|\Omega\mu-x\|_2^2+\frac{\beta}{2}\|x-\bar{\gamma}\|_2^2\quad\text{w.r.t.}\quad Px-c=0,\ \ x\geq0$$ and in order to do that with Matlab I ...
4
votes
1answer
98 views

Fast way to repeatedly solve a small nonlinear equation system

A small nonlinear equation system (sizes around 12 ✕ 12) needs to be solved repeatedly (millions of times); each time with some variation in parameters/coefficients (although the equation set is ...
4
votes
1answer
135 views

Solving a system of nonlinear PDEs by minimization

I have two coupled nonlinear partial differential equations of the form: $ \begin{align} \dot{u} -f(u,u',u'',v,v',v'')=0 \\ \dot{v} -g(u,u',u'',v,v',v'')=0 \end{align} $ The boundary conditions are ...
2
votes
2answers
130 views

TVL1 algorithm for optical flow

This is a bit of a long shot, but I was hoping somebody might have some insight (not sure of a better forum than here but open to suggestions). I have implemented the optical flow algorithm from the ...