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
24 votes
8 answers
4k views

Software package for constrained optimization?

I am looking to solve a constrained optimization problem where I know the bounds on some of the variables (specifically a boxed constraint). $$ \arg \min_u f(u,x) $$ subject to $$ c(u,x) = 0 $$ $$ ...
  • 1,370
15 votes
4 answers
2k views

Testing numerical optimization methods: Rosenbrock vs. real test functions

There seem to be two main kinds of test function for no-derivative optimizers: one-liners like the Rosenbrock function ff., with start points sets of real data points, with an interpolator Is it ...
  • 892
12 votes
2 answers
3k views

Newton-based methods in optimization vs. solving systems of nonlinear equations

I asked for clarification about a recent question about minpack, and got the following comment: Any system of equations is equivalent to an optimization problem, which is why Newton-based methods ...
11 votes
1 answer
7k views

Are there any heuristics for optimizing the successive over-relaxation (SOR) method?

As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
  • 11.8k
10 votes
2 answers
569 views

Eigenvectors of a small norm adjustment

I have a dataset that is slowly changing, and I need to keep track of eigenvectors/eigenvalues of its covariance matrix. I've been using scipy.linalg.eigh, but it'...
4 votes
2 answers
10k views

Tikhonov regularization in the non-negative least square - NNLS (python:scipy)

I am working on a project that I need to add a regularization into the NNLS algorithm. Is there a way to add the Tikhonov regularization into the NNLS implementation of scipy [1]? [2] talks about it, ...
13 votes
5 answers
2k views

Global maximization of expensive objective function

I am interested in globally maximizing a function of many ($\approx 30$) real parameters (a result of a complex simulation). However, the function in question is relatively expensive to evaluate, ...
  • 306
12 votes
2 answers
3k 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 ...
  • 11.8k
12 votes
2 answers
2k views

How do I find the minimum-area ellipse that encloses a set of points?

I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
11 votes
1 answer
2k views

Sensitivity of BFGS to initial Hessian approximations

I'm trying to implement the Broyden-Fletcher-Goldfarb-Shanno method to find the minimum of a function. I need two initial guesses $x_{-1}$ & $x_0$ and an initial Hessian Matrix approximation $B_0$...
  • 11.8k
9 votes
5 answers
1k views

How can I automate the process of optimizing the design of a physical object?

I'm trying to optimize a flow distributor in a tank such that the velocity and temperature distribution across any cross-section is relatively uniform. There are many parameters I can adjust to the ...
  • 11.8k
8 votes
1 answer
22k views

scipy.optimize.fmin_bfgs: "Desired error not necessarily achieved due to precision loss"

I am getting the warning in the post subject when attempting to optimize a function in Python with the scipy.optimize.fmin_bfgs function. The complete output: Warning: Desired error not necessarily ...
  • 183
5 votes
2 answers
351 views

Approximating and visualizing basins of attraction

I am working on estimating the position and orientation (pose) of a model (rigid object) from its silhouette in an image. For this, I have constructed an error measure between the model in its pose ...
  • 207
4 votes
4 answers
309 views

Minimize distance between curves

I have a dataset with values of multiple curves. An example plot is shown below. I want to shift the curves (up/down) so that all curves overlap. This would mean the data points in each curve is ...
  • 459
3 votes
1 answer
222 views

Finding zeroes of an infinitely differentiable function of ~100 to ~1000 variables

I have a function that is not only infinitely differentiable, but it is also very cheap to calculate any of those derivatives. It looks like: $f(\boldsymbol{C}, \boldsymbol{x})=\sum_{i} C_{i} \prod_{...
2 votes
1 answer
1k views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
  • 656
1 vote
1 answer
556 views

How to formulate variance minimization as a mixed integer quadratic program

I have a mixed integer quadratic problem and my objective function is as follows $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$ $d$ are ...
1 vote
0 answers
207 views

Oscillating convergence in my Resilient BackPropagation (RPROP) implementation

I have implemented in matlab a neural network that uses rprop's algorithm to update its weights. Strangely the error on the training set does not converge to a local minimum, but oscillates. Here is ...
  • 11
28 votes
3 answers
23k views

BFGS vs. Conjugate Gradient Method

What considerations should I be making when choosing between BFGS and conjugate gradient for optimization? The function I am trying to fit with these variables are exponential functions; however, the ...
  • 2,109
24 votes
5 answers
9k views

Why should non-convexity be a problem in optimization?

I was very surprised when I started to read something about non-convex optimization in general and I saw statements like this: Many practical problems of importance are non-convex, and most non-...
19 votes
3 answers
1k 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} \...
18 votes
1 answer
2k views

Intuitive motivation for BFGS update

I am teaching a numerical analysis survey class and am seeking motivation for the BFGS method for students with limited background/intuition in optimization! While I don't have time to prove ...
18 votes
4 answers
5k views

Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
  • 383
17 votes
5 answers
5k 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 ...
  • 417
17 votes
5 answers
2k views

Finding a global minimum of a smooth, bounded, non-convex 2D function that is costly to evaluate

I have a bounded non-convex 2-D function which I'd like to find the minimum of. The function is quite smooth. Evaluating it is costly. An acceptable error is about 3% of the function's domain in each ...
15 votes
2 answers
18k views

Confusion about Armijo rule

I have this confusion about Armijo rule used in line search. I was reading back tracking line search but didn't get what this Armijo rule is all about. Can anyone elaborate what Armijo rule is? The ...
  • 453
15 votes
3 answers
8k views

Fortran: Best way to time sections of your code?

Sometimes while optimizing code it is required to time certain portions of the code, I have been using the following for years but was wondering if there is a simpler/better way to do it? ...
14 votes
1 answer
9k views

Understanding the Wolfe Conditions for an Inexact line search

According to Nocedal & Wright's Book Numerical Optimization (2006), the Wolfe's conditions for an inexact line search are, for a descent direction $p$, Sufficient Decrease: $f(x+\alpha p)\le f(x)+...
  • 11.8k
13 votes
3 answers
7k views

Optimize an unknown function which can be evaluated only?

Given an unknown function $f:\mathbb R^d \to \mathbb R$, we can evaluate its value at any point in its domain, but we don't have its expression. In other words, $f$ is like a black box to us. What is ...
  • 1,281
13 votes
2 answers
6k views

Strategies for Newton's Method when the Jacobian at the solution is singular

I'm trying to solve the following system of equations for the variables $P,x_1$ and $x_2$ (all else are constants): $$\frac{A(1-P)}{2}-k_1x_1=0 \\ \frac{AP}{2}-k_2x_2=0 \\ \frac{(1-P)(r_1+x_1)^4}{L_1}...
  • 11.8k
10 votes
2 answers
4k views

Calculating Lagrange coefficients for SVM in Python

I'm trying to write a full SVM implementation in Python and I have a few issues computing the Lagrange coefficients. First let me rephrase what I understand from the algorithm to make sure I'm on the ...
10 votes
2 answers
1k views

Safe application of iterative methods on diagonally dominant matrices

Suppose the following linear system is given $$Lx=c,\tag1$$ where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
  • 1,653
10 votes
4 answers
4k views

Nonlinear least squares with box constraints

What are recommended ways of doing nonlinear least squares, min $\sum err_i(p)^2$, with box constraints $lo_j <= p_j <= hi_j$ ? It seems to me (fools rush in) that one could make the box ...
  • 892
10 votes
2 answers
848 views

Trace An Isoline of an Expensive 2D Function

I have a problem similar in formulation to this post, with a few notable differences: What simple methods are there for adaptively sampling a 2D function? Like in that post: I have a $f(x,y)$ and ...
  • 1,898
9 votes
2 answers
9k views

Simultaneous maximization of two functions without available derivatives

I have two variables k and t as functions of two other variables p1 and ...
user avatar
8 votes
1 answer
7k views

What are the differences between the different gradient-based numerical optimization methods?

I am interested in the specific differences of the following methods: The conjugate gradient method (CGM) is an algorithm for the numerical solution of particular systems of linear equations. The ...
  • 265
8 votes
1 answer
821 views

Linear system solution with inequality constraints - methods?

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this? Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{...
  • 113
8 votes
3 answers
3k views

What is the most appropriate derivative free optimization algorithm

We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$. If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
7 votes
3 answers
2k views

Finding the first N roots of transcendental equation

I need to find the first $n$ roots of the transcendental equation \begin{equation} F(k) = J_m'(kr)Y_m'(k)-J'_m(k)Y'_m(kr) \end{equation} for integer values of $m$ and any $r \in [0,1)$ where $J'$ ...
  • 873
7 votes
3 answers
2k views

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

So I have a symmetric matrix $A$ and I would like to solve the optimization problem, $$\hspace{2.5mm}\text{Minimize}\;\; \|A-S\|_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0.$$ $A$ is given and $S$ ...
  • 443
7 votes
2 answers
647 views

Recommendations for a usable, fast GPL-compatible derivative-free numerical optimization library that can be interfaced to C++

I am dealing with optimization of functions for which I do not have derivatives available, and the optimization is not constrained. I am searching for a high quality GNU Public License-compatible ...
  • 1,916
6 votes
0 answers
769 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}^...
  • 443
6 votes
1 answer
977 views

The speed and memory requirement of minpack

I am considering minpack software package to solve my optimization problem ( this is the kind of question that I am facing), but I don't quite know what is the memory requirement and the speed of this ...
  • 468
6 votes
1 answer
180 views

zero terminal value of the adjoint based optimal control

I have been pondering about this issue for some time... Say, I want to minimize a costfunctional $$ \tilde J(u) = J(v(u),u) = \frac 12 \int_0^T (v-v_0)^2 + \alpha u^2 dt $$ subject to $$ \dot v = v^2 ...
  • 3,408
6 votes
4 answers
3k views

LP feasibility checking

I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?
  • 555
5 votes
0 answers
457 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$$ ...
  • 443
5 votes
2 answers
872 views

log(det(X)) in Semidefinite Programming

I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
5 votes
2 answers
1k views

minimization problem: sum of Rayleigh quotients

I would like to find $x$ which minimizes the following equation: $\frac{x^HAx}{x^HBx} + \frac{x^HCx}{x^HDx}$ where A, B, C, D are positive-definite. $x$ is not a very large vector (<1000 elements ...
  • 1,300
4 votes
2 answers
179 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 ...
  • 143
4 votes
1 answer
255 views

Going to try to move some of my scipy/numpy calculation to a new GPU, how to avoid disappointing results?

update: I've refactored the question based on helpful advice in the linked meta. I'm a heavy user of Python's NumPy and SciPy (and not much else) and for years I could run anything I need on my laptop....
  • 942