Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
4
votes
3answers
3k views

Robust optimization using fmincon in Matlab?

I am trying to implement the following optimization (from this paper) in Matlab using fmincon: $\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$ where $\Sigma$ is a positive definite ...
4
votes
2answers
837 views

nonlinear conjugate gradient for multivariable functions

For the optimization problem $\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$, we can use the following standard nonlinear conjugate gradient method to find the solution: $...
4
votes
2answers
6k views

LBFGS or other optimization algorithms - implementations MATLAB

Do you know some good free Matlab LBFGS implementations? The only one I know (and use for the moment) is Liam Stewart's (it can be found at the following link: http://www.cs.toronto.edu/~liam/...
4
votes
3answers
281 views

Best software to do big number calculations quickly

I am trying to do some work on some math conjecture. I am testing the conjecture numbers using very large math numbers (100+ digits ). I am currently using python to test these numbers. In the ...
4
votes
2answers
143 views

Maximization variant of semidefinite programming (SDP)

Consider the following program: $$\max_{\pmb a} \sum_i z_i\\ u.c. \pmb a \pmb P_i\pmb a^\top\geq z_i$$ where $\pmb a \in\mathbb{R}^p$ and the $\pmb P_i$ are all symmetric positive semidefinite ...
4
votes
2answers
569 views

Derivative-free optimization of function with a flat region

I'm attempting derivative-free minimization of, essentially, a black-box function in one dimension. Up to now I've been using BOBYQA as implemented in NLopt. The shape of the function looks like this: ...
4
votes
1answer
584 views

What is a vector programming problem?

In a note: semi-definite programming is equivalent to vector programming. ... A Vector Program is a Linear Program over dot products. In Boyd's Convex Optimization, a vector optimization ...
4
votes
1answer
326 views

Conway's FRACTRAN

I've implemented fractran and playing with sequences iteratively in C. http://mathworld.wolfram.com/FRACTRAN.html Sloan: http://oeis.org/A007542 I can generate correct results, but I would like to ...
4
votes
3answers
296 views

How to fill a 2D set over a cartesian lattice with as few rectangles as possible?

Suppose I have a black and white image (composed of binary pixel values in a 2D cartesian array) that contains an irregular, nonconvex shape. Let's further suppose that the shape is one connected ...
4
votes
1answer
181 views

Piecewise linear optimization with resource allocation constraints

I have this problem: \begin{align} \min_{\mathbf{w}} & \sum_{i=1}^N c_i P_i(w_i)\\ s.t & \notag\\ & \sum_{i =1 }^N w_i = w \\ & 0 \leq w_i \leq w_{max},~~\forall i \in 1, ..., N \...
4
votes
2answers
414 views

Are these two formulations of semidefinite programming problems equivalent?

From Wikipedia Denote by $\mathbb{S}^n$ the space of all $n \times n$ real symmetric matrices. The space is equipped with the inner product (where ${\rm tr}$ denotes the trace) $$\langle A,B\...
4
votes
1answer
98 views

Arbitrary Precision Optimization Libraries?

Are there any well-known optimization libraries (ideally with Python bindings or even in Python) supporting (unconstrained) minimization (of $f:\mathbb{R}^n \to \mathbb{R}$ for $n$ for $n\sim 10^1,10^...
4
votes
1answer
168 views

Does the limit of $\frac{\partial f}{\partial u}$ at $u=0$ exist?

For an optimization routine I needed to compute the derivative of the right-hand side $\: f_u(x_k, u_k)$ of a discrete-time system $x_{k+1} = f(x_k, u_k)$. Since $\: f_u(x_k, u_k)$ includes terms that ...
4
votes
3answers
1k views

Beale's function and newton iteration

I am trying to find the minimum of the so called Beale’s function given by $f(x_1,x_2) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2$ Using Newton iteration $x^{(k+1)} = x^{...
4
votes
1answer
3k views

Constrained optimization with max and absolute values in objective function

I would like to find the optimal set $ \{ x_i \} $ given $ L $ and $ \{ a_i \} $ that minimizes the problem below. My first thought was to use linear programming. Is there a transformation that ...
4
votes
3answers
12k views

How to choose a good step size for stochastic gradient descent?

For the purpose of model fitting in a large time series dataset, I am using stochastic gradient descent of the negative log likelihood. The model is nonlinear and non-convex. Is there a thumb rule for ...
4
votes
2answers
718 views

Quadratic programs with rank deficient positive semidefinite matrices

Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
4
votes
3answers
615 views

Minimization of non-linear function

Problem Summary I am trying to estimate the (x,y) coordinates of each node in a graph, where I know the distances between connected nodes. For example Given this ...
4
votes
1answer
1k views

Converting convex quadratic constraint to linear matrix inequality (LMI)

I have the quadratic programming problem in $x$ $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{25mm}\boldsymbol{1}^Tx=1$$ ...
4
votes
2answers
1k 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 ...
4
votes
1answer
164 views

Question about extending Tikhonov regularization

I know that the Tikhonov regularization of a linear system has an analytical solution given by: \begin{equation} \hat{\mathbf{x}} = \mathrm{arg\;min}\left( \left| \mathbf{Ax} - \mathbf{b} \right|^{2} ...
4
votes
1answer
6k views

Differences between “least square”, “mean square” and “least mean square”?

I was wondering what differences are between the terminology: "least square (LS)" "mean square (MS)" and "least mean square (LMS)"? I get confused when reading in Spall's Introduction to Stochastic ...
4
votes
2answers
338 views

best way to optimize a function with linear/non-linear parameters

I am trying to fit some raw data using a function of the form $f(r) = \sum_{i=1}^{K} d_kS_k(n_k,\alpha_k,r)$ where $S_k(n_k,\alpha_k,r) = \frac{\alpha_k ^{n_k+3}}{(n_k+2)!}r^{n_k}\exp(-\alpha_kr)$ ...
4
votes
1answer
137 views

How to define a dimensionless Objective function for determining how peaked a curve is?

I have attached 2 plots for FFT spectra. One is considered good and one is bad. The good one is classified on the basis of how closely spaced the frequencies and the bad is based on how multiple ...
4
votes
1answer
227 views

How to solve the following Frobenius norm-minimization problem?

Background We know how to solve the following minimization problem $$ \min_{X} \lVert AX - B \rVert_F^2 $$ But what about the extended version? $$ \min_{X} \lVert A \begin{bmatrix} X & X^2 \...
4
votes
1answer
126 views

Nonlinear least-squares solvers vs. generic minimization

A nonlinear least-squares problem with $F:\mathbb{R}^m\to\mathbb{R}^n$, $$ F(x) \to \min_x \quad (\text{in the least-squares sense}) $$ really means minimizing $$ \frac{1}{2} \|F(x)\|^2 \to \min_x. $$ ...
4
votes
3answers
331 views

How can I use Projected Gradient Descent for this optimization problem with constraint?

Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that $$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
4
votes
2answers
211 views

Literatures on numerical stability of optimisation algorithms

I am curious of whether optimisation algorithms (whatever simplex, active-set quadratic programming, interior point sequential etc.) can fail due to numerical errors and how to avoid them. But I ...
4
votes
2answers
482 views

Simple bound constrained optimization problem

My problem is $$\text{minimize}: \phantom{2} f(x) \\ \text{subject to }: \phantom{2} x_4 \ge 0$$ where $x=(x_1,x_2,x_3,x_4)$. I know that the fourth component $x_4$ of the desired local minimizer ...
4
votes
1answer
198 views

convergence of unconstrained convex optimization

I encounter an optimization problem. The simplified version is like following: Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. $...
4
votes
2answers
188 views

non-convex quadratic with only one quadratic constraint?

I have a non-convex optimization problem in the form: \begin{align} \min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr \text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq \frac{1}{n-...
4
votes
1answer
343 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 ...
4
votes
1answer
234 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ f\...
4
votes
2answers
64 views

gradient for ternary functions?

I've got a function of form $$f: (\mathbb{Z}_3)^n \rightarrow \mathbb{R}$$ to optimize, where $n$ is relatively large (the order of hundreds). Is it there a gradient-like notion for these type of ...
4
votes
3answers
7k views

How to avoid NaN in optim?

Suppose, I have a function and want to optimize it. But if I use optim() which gives warnings(). How can I avoid these warnings ...
4
votes
1answer
1k views

Second order directional derivative in image processing

it is all about valley detection in image processing. I would like to find, for a given pixel, direction for higher second order derivative. I am not quite sure what discrete mask/filter I can use to ...
4
votes
1answer
297 views

Nelder-Mead optimization Algorithm

I am reading the following file, that explain the Nelder-Mead optimization Algorithm.(Algorithm Below) Where $B$ is the best point, $G$ second best point, $W$ is the worst point, $R$ reflection point. ...
4
votes
1answer
293 views

Should I include integral constraints in a integer linear program with a totally unimodular constaint matrix?

I have formulated an integer linear program (ILP). The constraint matrix for the ILP is totally unimodular. Should I solve it as an LP without the integral constraints, or should I keep the integral ...
4
votes
1answer
121 views

Which optimization method can be used to do the following?

I've the following system of equations for studying information flow in the below graph, $$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$ Here, M is the incidence ...
4
votes
1answer
155 views

Can I solve a model in GEKKO with Black Box, Simulated Annealing or GA solvers?

I'm trying to use my current GEKKO model with different solvers methodologies. I don't know if I can also use global optimisation solvers as GA, Simulated Annealing o Differential Evolution. I need ...
4
votes
1answer
96 views

Examples of problems that cannot be formulated as optimization problems

An optimization problem has 3 main components: decision variables, constraints and an objective function. Such a problem can be mathematically modelled and solved using an optimization solver. For ...
4
votes
1answer
2k views

How does fmincon in MATLAB calculate gradients?

I am trying to solve numerically a constrained optimisation problem in MATLAB, and I am wondering how the fmincon function calculates gradients when one isn't ...
4
votes
1answer
75 views

Large-scale almost-linear optimization

I'm currently trying to minimize the following function: $$\min_{\mathbf x,\mathbf y,s} \|F\mathbf x-\mathbf a\|_2^2 + \|SF\mathbf y-\mathbf b\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ $$\...
4
votes
1answer
157 views

Optimization of non-smooth, non-convex, locally Lipschitz functions of type exp(-abs(x))

What would be the numerical method of choice to find minima in a non-smooth, non-convex, locally Lipschitz function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. The function $f$ is mostly smooth but ...
4
votes
1answer
133 views

Efficient way to generate a list of possible matrices (all integer components) with a determinant $V$

I have an interesting problem from my research that I have been struggling to solve. One part of the problem involves generating all possible matrices, where each set contains three integer vectors, ...
4
votes
1answer
364 views

Sum of Inverse of Variables in an Optimization Problem

I have the following optimization problem: $$ \begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array} $$ where ...
4
votes
1answer
61 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 ...
4
votes
3answers
168 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 ...
4
votes
2answers
175 views

Optimization algorithm selection for 3 variable integer

I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$ it is very expensive to evaluate $x,y,z \in \mathbb{Z}$ 0 < x < 10 0 < y < 30 0 < z < 100 I thought it was convex, not sure ...
4
votes
2answers
152 views

Algorithm to find singularities of a log function

I have a numerical problem in which I need to find the values $\lambda$ for which the determinant of a matrix $A_\lambda$ is zero. (The solutions $\lambda$ will give the eigenvalues of an operator...) ...

1
3 4
5
6 7
17