Tagged Questions
1
vote
2answers
35 views
gradient descent optimal step size
Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
1
vote
2answers
46 views
genetic algorithm binary encoding
I am trying to write a program for maximizing a function using a genetic algorithm. The function has $n$ integer variables $x_1 \dots x_n$, such that each variable is in the range [-n,n].
What is ...
2
votes
1answer
36 views
Quadratic Forms and Newton's Method
Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
1
vote
0answers
50 views
How to effectively detect negative cycles in graph?
I proposed to check the edge weighs and then run shortest path and check if the shortest path weight is not going to $-\infty$. Any better ideas?
0
votes
0answers
27 views
Example of delayed column generation
Can someone point me to a small example of how delayed column generation works for the cutting stock problem. I have found several sources that describe it abstractly but I still don't understand ...
1
vote
1answer
35 views
Finding optimal recipe proportions
Is there a mathematical optimisation technique or algorithm that could, at least in principle, be applied to find optimal ingredient proportions for a given recipe using a minimal number of ...
0
votes
0answers
109 views
Multivariable optimization Algorithm using Matlab
i am working on Multivariable OPTIMIZATION PROBLEM, where i have to optimize 5 impedance variables i.e. Z1,Z2,Z3,Z4 and Z5 (where range of all impedance lies 50 to 150 ohms).
for eg. my proposed ...
1
vote
0answers
32 views
Statistical significance test in polygaussian fitting, using Levenberg-Marquardt
I have a set of dihedral angle values that I have fitted using a polygaussian function via the Levenberg-Marquardt algorithm
http://en.wikipedia.org/wiki/Levenberg-Marquardt. Specifically, the ...
2
votes
1answer
48 views
Optimal distribution of weighted votes
I'm working on a project for my university in wich the students can choose their preferred seminars for the next semester.
My goal is it to allocate these weighted votes in an optimal way to the ...
3
votes
0answers
72 views
How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?
I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
1
vote
1answer
68 views
minimize absolute value
Suppose we have $n$ real numbers $a_1, a_2, \ldots, a_n$. We know that the solution which minimizes
$$
\sum_{i=1}^n |x-a_i|
$$
is $x^*=$ median of $a_1, a_2\ldots, a_n$.
Now suppose that we should ...
3
votes
2answers
49 views
Algorithm to find the optimal setup
Suppose I have $2n$ numbers, from which I will compute $n$ sums of two-number pairs. For example, I have $6$ numbers $(1, 2, 3, 4, 5, 6)$ and I can generate three sums of $1+3=4$, $2+6=8$, and ...
1
vote
1answer
72 views
Properties of shortest walks and simple paths during optimization
Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...
2
votes
1answer
79 views
Minimim steps required based on game logic
I have the following simple game logic.
You start with G gold and 0 experience at Time = 0 minutes.
There are different types of houses what you can build, each with his own properties.
House A ...
0
votes
0answers
56 views
What is the best algorithm to solve a 2000+ node instance of the CVRPTW (capacitated vehicle routing problem with time windows)?
I have an instance of the CVRP in which a handful of customers have (relatively wide) time windows. The majority of customers have no restriction on time window.
More specifically: The problem is to ...
1
vote
0answers
34 views
Optimizing a matrix
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
...
0
votes
0answers
38 views
Another Matrix Algorithn
Another Matrix algorithm
input: $b_1,b_2,...,b_n$ positive integers.
$a_1<a_2<...a_n$ positive integers
output: positive integer
I'm given
$b_1$ columns of the form
$ \left( ...
4
votes
2answers
315 views
Change-making problem - counterexample for greedy algorithm
Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one.
I found statement that if for given set ...
2
votes
0answers
53 views
Determine if a polyhedron is a polytope
Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.
Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
0
votes
0answers
22 views
maximizing sum of a 3 numbers to
There are n lines of length 90 inches which need to be cut at 1/2 places so that the new parts formed after cut have a total length as close as possible to 90.
...
3
votes
1answer
56 views
How to compute the pareto frontier for dimensions higher than 2?
I'm looking for an intuitive way to compute the pareto frontier for dimensions higher than 2, i.e. a generalization of this (very nice) solution: How to compute the Pareto Frontier, intuitively ...
0
votes
0answers
17 views
Effective Strategies on optimizing a separable function
The problem statement is
$max \sum_i f_i(x)$
$s.t. x\in X$
Is there any effective strategies/frameworks that allows me to optimize a separable function?
Like an objective function analogy of ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
4
votes
2answers
80 views
Squared linear sum
Is there any effective algorithm for a squared linear sum assignment problem?
For squared linear sum assignment problem I mean the following:
$$\min\left(\sum_i \sum_j c_{ij}x_{ij}\right)^2$$
with ...
3
votes
2answers
143 views
Finding the nearest integers to real numbers defined implicitly
I was trying to bound the maximum cost of top-down merge sort:
$$
f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1,
$$
where $\lg n$ is the binary logarithm of $n$ and ...
2
votes
1answer
68 views
Maximizing a linear combination of certain integers
Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
0
votes
0answers
79 views
Steps of Non-negative Least Squares Algorithm
I already searched pseudocode for the NNLS Algorithm in the Web, but I only found complicated pseudocode that I couldn´t understand.
What are the rudimentary steps that NNLS takes? (Just the abstract ...
5
votes
3answers
277 views
Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D
I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
1
vote
1answer
71 views
Hausdorff-like distance between two arrays
Let $(X,d)$ be a metric space and $a,b\in X^n$ be two arrays of elements of $X$. Define
$$
\rho(a,b):=\inf\limits_{\sigma\in \Sigma}\sup\limits_{1\leq i\leq n}d(a_i,b_{\sigma(i)})
$$
where the ...
0
votes
0answers
45 views
Algorithms for solving/decomposing very large IP/MIP/BIP
I need to compare some algorithms used to solve integer/mixed integer/binary integer problems.
The number of variables is very large, probably in the tens of thousands, or even hundreds of thousands.
...
0
votes
2answers
63 views
$l_1$ norm projection with regularization term
I recently encountered an optimization problem and looking for some technical paper for the same.The problem is give as below,
$\min f(x)+\lambda*r(x) $
$\ s.t \ x \geq 0, ||x||_1 = 1$.
where $x$ ...
0
votes
0answers
77 views
2D Correlation Optimized Warping algorithm (COW) - dynamic programming
I have read this paper about correlation optimized warping algorithm for time series (or here chromatograms) alignment.
Level of detail is not sufficient regarding implementation of optimization ...
2
votes
1answer
308 views
Shortest distance between two shapes
This is the scenario of my problem. I have an image of two objects ( of arbitrary shape, not convex, not touching or crossing each other, kept a few space apart).
And I am supposed to find the ...
1
vote
0answers
23 views
Petri net analysis.
I have problems with this exercise. First: can the token in place $p_1$ to enable the transitions $t_2$ and $t_3$? The place $p_1$ has a single token, I think it fails to enable $t_2$ and $t_3$. Any ...
2
votes
1answer
70 views
Maximizing the number of points covered by a circular disk of fixed radius.
Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?
1
vote
2answers
223 views
Minimizing Sum of Product
I'm given 3 multisets $A$, $B$, and $C$ each with $n$ elements. Now I'm to form $n$ (say $D_1$ to $D_n$) multisets of 3 elements each from $A$, $B$, and $C$, such that each of these $n$ multisets ...
2
votes
1answer
123 views
Longest cycle containing two nodes
We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
2
votes
3answers
184 views
Lowest value from multiple possibles
Sorry about the title. Not sure what to call this question.
I am trying to calculate the lowest total cost of lets say a box, circle and square over n amount of suppliers. Each supplier charges a ...
2
votes
0answers
58 views
Petri net analysis (attainability)
how to analyse safe petri net for attainability?
(i need algorithm)
I have an oriented multigraph $\mathbb{G}$.
$A$ - adjacency matrix.
$m$ - the count of input elements.
$n$ - the count of ...
3
votes
2answers
125 views
No identical rectangles in a matrix
I have a matrix of dimensions N x M.
Every cell has an integer.
Now, I want for every 'rectangle', to verify that all its corners are not the same.
Example:
This matrix is fine:
This matrix is not:
...
3
votes
1answer
217 views
How shall I understand this simple example of No Free Lunch theorem?
I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization:
My understanding is that a cost function is a ...
3
votes
0answers
61 views
Existence of a general-purpose (almost) universal optimization strategy
From Wikipedia about interpretations of no free lunch theorem
A conventional, but not entirely accurate, interpretation of the NFL
results is that "a general-purpose universal optimization ...
3
votes
1answer
154 views
What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?
EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
4
votes
1answer
2k views
How to compute the Pareto Frontier, intuitively speaking?
I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost.
Now the question is 'how does one compute a pareto frontier'? ...
2
votes
1answer
69 views
game strategy question
Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the ...
1
vote
1answer
695 views
Two-Phase Method (Linear Programming)
In Linear programming, when is it beneficial to use the Two-Phase Method? Why not just use the Simplex Method?
(edit: typo)
2
votes
3answers
448 views
Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)
We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks ...
1
vote
2answers
95 views
A very simple optimisation problem
Given any set of real scalar values $V=\{v_i | 1 \leq i \leq n\}$ and a distinct value $v_p$ define c:-
$$ c= \sum_{i=1}^n |v_i-v_p| $$
What is the easiest way to determine $v_p$ such that $c$ is ...
2
votes
1answer
336 views
Greedy Algorithm Proof
My problem seems similar to the Interval Scheduling problem (processing as many jobs as possible), which I understand but can't seem to apply properly in this case. I've tried to simplify the problem ...
1
vote
1answer
87 views
What is the maximum value of the minimum number of balls per bin?
$S$ people, $N$ bins, each person has a given subset of bins he can cover,
each person is given $t$ balls.
Question: What is the maximum value of the minimum number of balls per
bin? i.e., allocate ...
