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
7
votes
5answers
591 views

Recommended Route for Mastering Inverse PDE Problems

I would like to master Inverse PDE Problems particularly with the use of Finite Elements. My problem is I don't know where to start. Should I begin by reading a book on Inverse Problems or on PDE-...
3
votes
0answers
104 views

Efficient principal pivots

It was suggested I should try posting this question here from Mathematics Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal ...
8
votes
1answer
16k 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 ...
3
votes
2answers
5k views

Problems that can be reduced to the Traveling Salesman Problem

Which search/optimization problems can be reduced to the famous "Traveling Salesman Problem"? For instance, I have a collection of N particles, in 3D, and there is a function (Van der Waals energy) ...
6
votes
1answer
263 views

Adaptive h for gradient estimation

Can anyone point me to methods for varying $h$ in gradient estimation for noisy numerical optimization? Some programs have the user give a fixed $h$, which is used for forward-difference or central-...
2
votes
2answers
2k views

Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)

I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000. I already do it! but I do it with trial ...
1
vote
1answer
724 views

Gradient descent to stationary, or accumulation point

I recently came across the notion of an accumulation point as a result of a certain gradient descent variation. The following definition was found: An accumulation point $P$ is such that there are an ...
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}(...
10
votes
4answers
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 ...
1
vote
1answer
943 views

Multidimensional Minimization: GNU GSL C++ error code 27 for - iteration is not making progress towards solution

I am trying to find the minimum of the function using GNU scientific library, package Multidimensional Minimization. The method I am using is Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which is ...
7
votes
5answers
607 views

Adjoint method for optimization problem

I am interested in the adjoint method for shape optimization problems. However, I couldn't find a helpful introduction. So I come here and look forward to some enlightening advices. Could you direct ...
5
votes
3answers
2k views

IPOPT solver auto-converts my binary variables to continuous

I hope this is the right stackexchange for this question; if not, please direct me there! I'm on Linux. I've installed IPOPT and AMPL, and all the third-party stuff required: ASL, HSL, Lapack, Metis, ...
3
votes
1answer
70 views

2D Jacobi line maintenance?

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
10
votes
2answers
727 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 ...
14
votes
1answer
3k views

The Remez Algorithm

The Remez algorithm is a well-known iterative routine to approximate a function by a polynomial in the minimax norm. But, as Nick Trefethen [1] says about it: Most of these [implementations] go ...
4
votes
0answers
410 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$, ...
6
votes
2answers
2k views

Non-differentiable global optimization problem

I am trying to solve the following test problem which is well-known in the community in different variants: Place N = 15 points in the 3-dim. unit cube such that the minimal distance between them is ...
9
votes
2answers
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\...
6
votes
1answer
440 views

Reducing degeneracy in constrained (convex) optimization problem

DISCLAIMER: I've edited the question repeatedly for clarity and to target the most relevant answer. I have the following general problem $$ \min \|h_1\cdot h_2\|^2 $$ such that $$\|g_1\wedge g_2-h_1\...
7
votes
1answer
604 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
10
votes
2answers
2k views

How is geometric programming different from convex programming?

How is (generalized) geometric programming different from general convex programming? A geometric program can be transformed into a convex program, and is typically solved by an interior point method....
16
votes
6answers
20k views

Constraints involving $\max$ in a linear program?

Suppose $$\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}$$ where $U$ is a symmetric $n\times ...
11
votes
1answer
598 views

Computing standard errors for linear regression problems without calculating inverse

Is there a speedier way to calculate standard errors for linear regression problems, than by inverting $X'X$? Here I assume we have regression: $$y=X\beta+\varepsilon,$$ where $X$ is $n\times k$ ...
5
votes
1answer
126 views

Using an approximation algorithm to adapt parameter values of a given algorithm

Problem: I have an incremental online clustering algorithm which need 4 parameters that should be specified by the user before execution. The algorithm will gives "good results" if "a good parameter ...
8
votes
2answers
295 views

One-sided non-linear least squares with linear constraints

I am trying to solve a one-sided non-linear least-squares problem with linear constraints, i.e the problem: $\min_{\mathbf{x}} \quad \sum^m_{i=1} \mathbf{r}_i(\mathbf{x}) \qquad \text{ s.t } \quad A\...
3
votes
1answer
197 views

Can BFGS be used to minimise several functions at once?

I have multiple objective functions which are related to several parameters. I want to minimise more than one objective functions using several parameters. Is it even possible using BFGS? When I used ...
6
votes
4answers
279 views

Approximately “solving” a linear system of equations without a feasible solution

A linear system of equations has the form $Ax = b$, where a matrix $A$ and a vector $b$ are given, and I wish to find a solution vector $x$. Suppose that the system $Ax = b$ has no feasible solution. ...
15
votes
4answers
5k views

Linear programming feasibility problem with strict positivity constraints

There is a system of linear constraints ${\bf Ax} \leq {\bf b}$ . I wish to find a strictly positive vector ${\bf x} > 0$ that satisfies these constraints. That means, $x_i > 0$ is required for ...
3
votes
3answers
968 views

What is the best way to solve Ax = b (with A large, spd, sparse, banded and poorly conditioned)?

I'm trying to solve $Ax = b$ given a vector $b$ and a large, symmetric positive definite, sparse, banded matrix $A$ that has a very poor condition number. I know several iterative methods that ...
10
votes
1answer
6k 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 ...
15
votes
5answers
13k views

Minimizing the Sum of Absolute Deviation ($ {L}_{1} $ Distance)

I have a data set $x_{1}, x_{2}, \ldots, x_{k}$ and want to find the parameter $m$ such that it minimizes the sum $$\sum_{i=1}^{k}\big|m-x_i\big|.$$ that is $$\min_{m}\sum_{i=1}^{k}\big|m-x_i\big|.$$...
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 ...
12
votes
1answer
4k views

Efficient solution of mixed integer linear programs

Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation ...
-2
votes
1answer
303 views

Multi-objective optimization problem - Euclidean space

I am looking for some clues for an optimization problem. My problem consists of arriving to a image by optimizing multiple layers with the pixel position probability. This is an overview of the ...
21
votes
8answers
3k 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 $$ $$ ...
26
votes
3answers
20k 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 ...
4
votes
2answers
337 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)$ ...
83
votes
17answers
96k views

Is there a high quality nonlinear programming solver for Python?

I have several challenging non-convex global optimization problems to solve. Currently I use MATLAB's Optimization Toolbox (specifically, fmincon() with algorithm=<...

1
13 14 15 16
17