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

learn more… | top users | synonyms

1
vote
0answers
13 views

Benchmark an stochastic constrain solver

I wrote a small simulated annealing library in C++. Right now is just a few classes, a toy project I want to use to test some ideas. But before I move on I want to be sure that it works. Meaning, that ...
0
votes
1answer
34 views

Optimizing multiple output parameters for a given input

Problem statement: I'm trying to solve a problem statement using C# as programming language. In the problem system for an input (double/decimal) say $H_i$, the output generated is a form of dataset ...
3
votes
1answer
51 views

Understanding the conditions for which ADMM can be applied

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
2
votes
2answers
152 views

Fitting orthogonal planes to a point set

I have a set of 3d points to which I want to fit two planes. I know the assignment of points to the planes so I don't need any RANSAC or similar. Currently, I'm using a PCA-based approach to fit two ...
7
votes
1answer
77 views

N-body simulation optimisation, looking for name or existing work

during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before. It ...
1
vote
0answers
19 views

optimal SAT solver with weighted variables

I have $n$ boolean variables $x_1,\ldots,x_n$ with associated real-valued costs $c_1,\ldots,c_n$, respectively, and a boolean function $(x_1,\ldots,x_n)\mapsto\Phi(x_1,\ldots,x_n)$ in conjunctive ...
1
vote
1answer
106 views

Round-robin pairings: Everybody need to meet everybody

I have the following problem, I have a class of N people and I want them to do stuff by pair, but I want them to do this with everybody but as fast as possible. For N = 4 I got this: ...
1
vote
1answer
56 views

Simplex method - cycling and condition “>=” or “>” in choice of pivot row

I'm coding the simplex method and observing that it easily falls into cycling, even if Bland's rule is used. It seems to me I have found the reason and I would like to check my understanding is ...
3
votes
1answer
149 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 ...
3
votes
2answers
112 views

Disadvantages of adding an extra variable to an optimization problem

Suppose we have an optimization problem $$ \mathbf{x} = (x_1, x_2, \ldots, x_m) = \arg\!\min_{\mathbf{x}\in \mathbb{R}^m}f(\mathbf{x})$$ and a second related problem: $$ \mathbf{y} = (y_1, y_2, ...
1
vote
1answer
111 views

How to efficently solve: min $\sum_{ij}(a_{ij}x_{ij}^2 + b_{ij}x_{ij})$ s.t

I am trying to solve the following problem, where $a_{ij} \ge 0 \ \forall i,j$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject ...
-5
votes
1answer
94 views

Do you think this p=np workaround worth to try?

I need consultancy for a possible p=np workaround. First of all sorry for my English because it is going to be long question:) To better understand the architecture which I design maybe you will need ...
1
vote
0answers
56 views

Divide and Conquer division algorithm explained (as used in GMP bignum)

I am trying to understand the divide and conquer division algorithm that is used in the GMP bignum arithmetic library. The code is very optimised and that makes it somewhat hard to understand. the ...
3
votes
1answer
111 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
7
votes
2answers
131 views

Name of an Optimization Approach to Reduce Size of Variable Space

I am dealing with an optimization problem that has a large number of variables to optimize over - for example let's call these variables $x$, $y$, and $z$ and I wish to minimize the function ...
1
vote
1answer
45 views

Expected number of steps before a global optimum is found with Simulated Annealing

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link. Given $G=(V, E)$ is the graph ...
1
vote
1answer
78 views

Iterative Closest Point Algorithm

I am currently working on an iterative closest point algorithm (in C++, see here). I understand the basic premise of an ICP algorithm. You have two point clouds (a target and a reference) and you ...
4
votes
1answer
155 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. ...
0
votes
0answers
55 views

Iterative optimization problem

There is problem which I am stuck in that for nearly a month. I have encountered a problem which is as follows (equation (1)). \begin{align} &\min_x &f(x) &\quad\implies \text{represents ...
0
votes
0answers
62 views

Iterative Optimization [duplicate]

I have encountered a problem which is as follows \begin{align} &\min_x &f(x)\\ &\operatorname{subject to} &h_i(x) =0\\ & &g_i(x) = 0 \end{align} where $f(x)$ is a quadratic ...
4
votes
1answer
57 views

Balancing number of points in a 2D grid

In a parallel MPI code, I have load balancing issues. My 2D computational domain is distributed on a 2D MPI Cartesian topology, which leads to equal sized 2D sub-domains per MPI process. However, the ...
0
votes
1answer
103 views

How to avoid the round-off errors in the larger calculations?

Now I need to sum up more than one thousands of terms and then make the four-dimmensional integral in my Fortran program. I found that there are some numerical errors. Can you give me some suggestions ...
0
votes
0answers
27 views

Pickup and delivery problem with time windows and container repositioning

Given a set of ships, harbors, batches, containers, and, a matrix of distances between harbors. At any given point in time a harbor has some number of containers which can either be available or used ...
2
votes
1answer
43 views

Sampling vector so they will have a given euclidean distances matrix

Given a matrix $M\in\mathbb{R}^{P\times P}$ , is it possible to sample $P$ vectors $u_i\in\mathbb{R}^N$, $i=1..P$ so that $\|u_i-u_j\|=M_{ij}$. Obviously for not any $M$ this is possible, i.e. it has ...
3
votes
0answers
133 views

Reference Request: Variational Problem

I want to solve approximately the following variational problem: Given a function $c:[-1,1]^2\rightarrow [0,1]$, constants $p_1...p_n\in \mathbb{R}^+$, $\alpha_1...\alpha_n\in \mathbb{R}$, and ...
0
votes
0answers
30 views

CPLEX: function convex on search space but not on whole R^n

I have an optimization problem where the function i want to minimize is convex; it's of the form $f = \sum_i - x_i y_i$, all variables have a constraint $x_i \geq 0, y_i \geq 0$, and all other ...
0
votes
0answers
66 views

Looking for a C/C++ implementation of the Hungarian method for real-valued cost matrix

I am looking for a C/C++ implementation of the Hungarian method for solving the linear assignment problem with real-valued cost matrix. Some implementation I found, such as this one, only work for ...
0
votes
0answers
23 views

Algorithm for SDP with repeated structure, diagonal blocks

I wish to solve a semidefinite relaxation of the following problem: $$ \begin{array}{rl} \min_{z_1,\ldots,z_k\in\mathbb R^n}\ & z^\top A z\\ \textrm{s.t.} & z_i^\top B_j z_i+c_j^\top z_i=0\ ...
0
votes
1answer
56 views

Definition of the DTLZ 5 - 7 Problems

For a multi-objective optimization task I want to use the DTLZ5, DTLZ6 and DTLZ7-problems definied by Deb et al. in their Paper "Scalable Multi-Objective Optimization Test Problems". There are ...
0
votes
0answers
50 views

How to Optimisation to return decimal and integer values-Python?

I want to optimize a function, where the optimization algorithm should return parameters of two types, decimal and integer. Is this possible? I am using python.
3
votes
0answers
94 views

Eigenvalue-style optimization with quadratic constraints

Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric and positive definite and that we have several symmetric matrices $B_i\in\mathbb{R}^{n\times n}$ that are low-rank and indefinite. I need an ...
3
votes
1answer
72 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 ...
5
votes
4answers
458 views

cost function: why use power of two ? abs(x - xhat) / x better?

Why do people use the classical least squares approach so often ? If I use the absolute value instead of the power, I immediately know how far away the solution is: $$ res = \frac{abs(x - ...
1
vote
2answers
85 views

Traveling Salesman Problem

First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in ...
2
votes
1answer
227 views

Difference between Gauss-Newton method and quasi-Newton method for optimization

Can anybody help me? I heard that Gauss-Newton method compute an aproximation of the Hessian instead of the true Hessian, but, quasi-Newton method too, don't it? what is the differences between them? ...
3
votes
1answer
55 views

Maximizing a function over a polytope

I have to maximize $$f(x,y)=-\log(xy)$$ However I need it over the polytope $T=\mathrm{conv}\{(1/2,1/2),(1,2),(2,1)\}$ and this gives me problems: Then I get $$f_x(x,y)=1/x=0$$ $$f_y(x,y)=1/y=0 $$ ...
6
votes
0answers
57 views

Accelerated convergence for Sparse NMF

In the Non-Negative Matrix factorization (NMF), you basically compute an approximation of a given matrix $V \in \mathbb{R}_{+}^{n \times m}$ into matrices $W$ and $H$ such that $W \in ...
2
votes
0answers
51 views

Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
0
votes
1answer
43 views

Solving a quadratic pseudo-boolean optimization problem where the integral constraints are relaxed

Quadratic Pseudo-Boolean Optimization (QPBO) problem: Problem 1. Minimize $\sum_i a_ix_i + \sum_{i<j} a_{ij}x_i x_j$ subject to $x_i\in\{0,1\}\forall i$. Consider the following problem, where the ...
4
votes
1answer
59 views

Trust region - Newton: how to choose constants that determine trust region bound

In a trust region based Newton method, a number of constants are given as inputs to the algorithm that determine the updating rules for the trust region bound. Are these constants chosen arbitrarily ...
2
votes
0answers
46 views

Find constrained vectors maximizing angles between them - methods?

This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
4
votes
0answers
49 views

Is there a term for Goodhart's Law in the context of optimization?

Let's say I'm optimizing something. To pick an arbitrary example, let's say I'm choosing the shape of some part to maximize strength-to-weight ratio. So I get some FEM software, parametrize the shape, ...
2
votes
0answers
46 views

Symmetric nonnegative matrix factorization

Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving $$ \begin{array}{rl} \min_U & \sum_{ij} ...
2
votes
2answers
233 views

what does -ffast-math do?

What kind of optimisations does the option -ffast-math do ? I saw that the time taken for a simple $O(n^2)$ algorithm being reduced to that of an $O(n)$ algorithm ...
2
votes
1answer
63 views

Parameter reduction algorithm for least square model

Question I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements. The model function ...
6
votes
1answer
155 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, ...
0
votes
0answers
30 views

Displacement response on the boundary for isotropic elascticity

Let $\Omega$ be a smooth domaine of $\Re^{3}$ and $\Sigma$ a surface of $\Re^{3}$ smooth enouth but not necessarly simply connected (cracks). weconsider the following elastostatic problem(P): ...
0
votes
1answer
72 views

Changing min function to max function for optimization

I want to maximize an objective function using quasi-newton optimization method. But i couldn't find any function for maximizing a function. All inbuilt functions are for minimization. For eg. fminunc ...
0
votes
1answer
40 views

Solve a pair of coupled nonlinear equations within certain limits

This answer to this question works only for situations in which the desired solution to the coupled functions is not restricted to a certain range. But what if, for example, we wanted a solution such ...
3
votes
0answers
56 views

How to implement conjugate gradient method to minimize this nonlinear action?

Given a 2D stochastic differential equation: \begin{align} \dot{x}_{i}=f_{i}(\textbf{x})+g_{ij}\xi_{j}(t), \end{align} where $i=2$, $g_{ij}g_{jk}=2\epsilon\delta_{ik}$ and ...