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

learn more… | top users | synonyms

4
votes
6answers
346 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
1answer
41 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
38 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: ...
-1
votes
0answers
31 views

Expert advice problem - The multiplicative weights update method

Are there any implementations of Expert advice problem - The multiplicative weights update method available in matlab or any other languages. Please, see links for detailed explanations 1 2. Brief ...
2
votes
1answer
115 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
129 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
187 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
85 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
168 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
44 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
60 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
51 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
74 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
57 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
109 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
50 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
82 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
53 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
145 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
119 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
57 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
94 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
99 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
131 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
115 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
84 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
92 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 ...
3
votes
1answer
97 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
107 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 ...
3
votes
1answer
146 views

solving a linearly-constrained sparse linear least-squares problem

[ question reposted from http://math.stackexchange.com/questions/786612/solving-a-linearly-constrained-sparse-linear-least-squares-problem ] Given the system of equations $Ax=b$, subject to $Cx\le ...
0
votes
1answer
39 views

Marginal values for non linear optimisation using SNOPT

I am currently solving a Non Linear modell in GAMS and I am interested in a sensitivity analysis of the results. When working with a linear program I am able to look at the marginal values for the ...
4
votes
4answers
283 views

Mathematical optimization software free/openSource

I want to write mathematical optimization software. At university, they taught me how to use AMPL+CPLEX/SCIP/MINOS/Couenne etc.. and that was good enough. But I cannot afford the cost of AMPL for my ...
1
vote
0answers
70 views

Solving “virus”, a flash game, in the least amount of attempts

We am currently working on a project related to computational optimization, in which I have tasked myself with calculating the most efficient solution to one of the game's levels. Link to the flash ...
2
votes
1answer
61 views

Algorithm to equalize the area of random tessellation of various polygons

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
3
votes
1answer
169 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix A (10000*10000), if Aij is 1, then ith and jth variables can take 1 simultaneously, if it's 0, then it's ...
1
vote
1answer
48 views

Optimization of a sum of an absolute vector

$$ Mimimize\ \sum\limits_{i=1}^{10} L_{i}x_{i} \\ subject \ to \\ Af=p\ \\ x \geq|f| \\ L, p \ and\ A\ are\ known,\ f\ and\ x\ unknown.\ Af=p\ is\ underdetermined $$ x is minimized when abs(f) is ...
1
vote
2answers
62 views

Optimization with order constraints on parameters

Are there optimizers where it is possible to specify ordinal ranking of parameters? Assume that I have a function of three parameters $f(\theta_1, \theta_2, \theta_3)$. Are there optimizers such that ...
2
votes
0answers
73 views

Inverse problem with a rank-1 update

I hope you can help me out with this. I have to find the solution x to an inverse system $$ x=A^{-1}b $$ This inverse problem is basically a least square problem with a rank-1 update. $$ ...
2
votes
1answer
83 views

I have to solve a large binary programming task. Should I avoid branch and bound?

I have to minimize a linear function with respect to variables u which take values [0,1] The number of variables can exceed 10,000 There are thousands of linear inequality constraints I need a ...
0
votes
1answer
49 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
2
votes
2answers
234 views

Interpolation by Solving a Minimization Problem (Optimization)

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - M by N Matrix). Someone marks some pixels as anchors. Now, you need to ...
3
votes
1answer
138 views

Recommendations on FEM software for implementing Nitsche's method on interfaces between matching meshes?

Suppose: I have two domains, $\Omega_{1} = [0, 1/2] \times [0, 1]$ and $\Omega_{2} = [1/2, 1] \times [0, 1]$. The domains share an interface $\Gamma = \{1/2\} \times [0, 1] = \partial\Omega_{1} \cap ...
4
votes
3answers
97 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
106 views

Effect of Initial guess B (approximate Hessian) on BFGS algorithm

I am trying to implement BFGS. The purpose is to approximate Hessian matrix only (not using the quasi-newton optimization steps), so i am using steepest ascent for optimization. What I observe is that ...
0
votes
1answer
54 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...
2
votes
1answer
167 views

Weighted Gauss-Seidel Algorithm

In Jacobi method's Wikipedia article there's a section that describes Weighted Jacobi method: http://en.wikipedia.org/wiki/Jacobi_method#Weighted_Jacobi_method. I need to implement the Weighted ...
3
votes
0answers
57 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 ...
2
votes
1answer
59 views

Why do QM programs use redundant internal coordinates for geometry optimization?

Brief explanation of QM geometry optimization Quantum mechanics packages are often tasked with optimizing a chemical structure. The problem is essentially this: Given a set of points in 3D space and ...