0
votes
0answers
39 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
0
votes
0answers
48 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
3
votes
0answers
18 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
3
votes
2answers
54 views

Minimize Sum a_i / Sum b_i over subsets

I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes: $$\frac{\sum_{i \in I} a_i}{\sum_{i ...
1
vote
2answers
265 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
0
votes
1answer
39 views

Concrete Example of Maximum Likelihood Estimator

I was reading this article, about how seatgeek creates its algorithm for choosing the optimal seat: http://chairnerd.seatgeek.com/the-math-behind-ticket-bargains Most of it is straightforward up ...
0
votes
0answers
16 views

Quantization minimizing the quadratic error

I am working on a quantization problem which could be express in these terms : Given a set of positive reals $\{x_1, x_2,\dots,x_M\}$, I need to find another set $\{y_1,y_2,\dots,y_N\}$ of size $N ...
0
votes
1answer
33 views

Assigning workers to tasks such that difference of the number of workers for each task to a given optimum is minimized

Im trying to find an algorithm to solve the following problem: We have a set of workers and some tasks, with not every worker being able to do any kind of task (but at least one). Theres is ...
2
votes
2answers
42 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
0
votes
0answers
37 views

Keller 6 graph and maximum clique

Based on the DIMACS maximum clique benchmark, http://iridia.ulb.ac.be/~fmascia/maximum_clique/, the Keller 6 graph contains a clique of size 59. The clique number however is at least 59 (as can be ...
3
votes
3answers
43 views

How to combine Unitary Matrices in a clever way?

I am trying to implement genetic-type algorithms on unitary matrices. Hopefully I should be able to use this question for the mutation part. But I am having an issue with the cross-over step. So here ...
0
votes
1answer
31 views

Halting of an algorithm

Suppose there is an algorithm that runs on a finite set. If we do not directly specify a halting condition, such as reaching a certain value, or after given number of iterations, what are the methods ...
0
votes
0answers
39 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
1
vote
1answer
34 views

Reverse engineering the objective function

If there is a finite iteration algorithm can we find a function that this algorithm optimizes, in hindsight? Edit: Suppose there is a set of functions $f_i(x)$, where $x\in \mathbb R^n$, ...
0
votes
0answers
30 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
1
vote
0answers
40 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
3
votes
1answer
111 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
0
votes
0answers
42 views

Need suggestions for this real world problem

I have a real-world optimisation problem. Following is the problem. At last have the hope for mathematics. Problem: One person Mr. X works as supervisor for a home appliances repairing company. Mr. X ...
0
votes
1answer
34 views

Is it possible to always get the optimal formula regardless of the derivation method?

Today I've tried to solve a geometric problem (collision point between two circles in a specific situation). I found a working solution but I'm not sure if it was optimal (maybe my solution took more ...
0
votes
1answer
41 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
2answers
27 views

Minimize error function with integer constraints

Much time has passed since I studied any form of math so I wanted to take this cheap shot of asking someone else to think for me. I need to write some software that, for any given real number ...
0
votes
0answers
26 views

Bound for the greedy algorithm solution to the cover set problem

This is from Algorithms by Dasgupta et al.: Claim Suppose B contains $n$ elements and that the optimal cover consists of k sets. Then the greedy algorithm will use at most $k$ ln $n$ sets. ...
1
vote
1answer
136 views

Which greedy algorithm is optimal?

The following question is a homework problem for a course called Design and Analysis of Algorithms. In the problem, there is a minimized cost function and two greedy algorithms. I am asked to show ...
0
votes
3answers
61 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
1
vote
1answer
16 views

How to recognize if an algorithm working on ordinal data will also work if the ordering is reversed?

Inspired by a comment on this question. Assume that I have an algorithm which uses ordinally scaled data. The algorithm in the original question was the solution of the Secretary Problem. It uses ...
0
votes
0answers
15 views

chained max notation

I'm confused on how to implement a quality indicator for multi-objective optimization. I don't understand the following notation. $$I_{\epsilon} (A,B)=\max_{z^2 \in B} \min_{z^1 \in A} \max_{1 \le i ...
0
votes
2answers
63 views

Find $n$ and $k$ such that maximum element is minimum

Given $a_1, a_2, a_3, \ldots, a_m \in \mathbb {Z}$. How do I find $n \in \mathbb Z, k \in \mathbb N$ such that $$\max \{|n - a_1|, |n+k-a_2|, |n+2k-a_3|,...\}$$ is minimum? The original problem was ...
1
vote
0answers
18 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
2
votes
1answer
66 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
0
votes
0answers
56 views

3D Space Covering-Problem

Given a finite amount of "slots" in 3D space, e.g. $$S = [(1,2,3),(1,3,3),(1,4,3),(1,3,4)] \in \mathbb{N}^3.$$ I'm trying to find an efficient algorithm to determine a minimal set of (rectangular) ...
0
votes
1answer
34 views

Implement ideal line search algorithm

I have the function $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x$. I want to use the steepest descent algorithm where $Q$ is the diagonal matrix $\begin{bmatrix}1 & 0\\0 & 20\end{bmatrix}$ and ...
0
votes
0answers
26 views

How can Ant Colony Optimization be made to produce more consistent results?

I developed a software implementation of Ant Colony Optimization to solve the Traveling Salesman Problem, but due to ACO's stochastic nature, each execution of the ACO algorithm produces a different ...
0
votes
1answer
79 views

Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
1
vote
0answers
27 views

Need an optimization algorithm

I need this algorithm for one of my projects. I will paraphrase the problem. There are 'n' ropes that have different colored rings on them. (The colors might repeat on the same rope or across ...
1
vote
1answer
39 views

Optimization of several cost functions together

Say I want to minimize several functions together: $$\min \lVert f_1\rVert, \min \lVert f_2\rVert, \min \lVert f_1-f_2\rVert$$ where $\lVert f\rVert$ is the $L_2$ norm of $f$. I am wondering can I ...
1
vote
1answer
63 views

Is there a name for this optimization algorithm?

I'm a software developer trying to design an optimization algorithm and I'm wondering if what I'm trying to do resembles any of these. There's a daunting number and rather than read each one, perhaps ...
0
votes
1answer
28 views

Adding a point to shortest path

If there exists a set of n points in a 2D coordinate system and an n-dimensional vector V ...
0
votes
0answers
33 views

Why is Expectation Maximization algorithm guaranteed to converge to minimum, even local?

I have read a couple of explanations of EM algorithm (e.g. from Bishop's Pattern Recognition and Machine Learning and from Roger and Gerolami First Course on Machine Learning). The derivation of EM is ...
0
votes
2answers
56 views

Prove that so and so is $O(x^4)$

Given $f(x) = x^3 + 20x + 1$, how would I prove this is $O(x^4)$? By definition, the function is $O(x^4)$ iff $f(x) <= cn^4$, where $c$ is some constant. However, I'm not sure where to go from ...
0
votes
0answers
34 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 [ ...
1
vote
1answer
36 views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ...
0
votes
0answers
47 views

Find all $a_i$ such that $(x_{a_1} - x_{a_2} + x_{a_3}) +\ldots + x_{a_{3k}}$ min

Given $n$ numbers $x_1, x_2, \ldots,x_n \in \mathbb{Z}$ and an integer $k \le\frac n 3$. Find $a_i$ $(i = \overline{1,2,3,\dots,3k}),\ 0 < a_i < a_{i+1} \le n$ such that: $$M = (x_{a_1} - ...
-1
votes
2answers
96 views

How do I guess an intital step length in a line search (minimization)?

I am currently trying to write a "simple" minimizer for a function $y = f(x)$ where $x$ is a multidimensional vector and $y$ is a real number where I have access to the derivate vector. If I have a ...
4
votes
0answers
60 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
0
votes
0answers
52 views

GA (Genetic Algorithm) and stochastic simulation to solve optimization in R

My problem is to solve the following optimisation problem using GA (Genetic Algorithm)and stochastic simulation. The goal is to solve the maximisation problem : \begin{equation*} \begin{aligned} ...
1
vote
1answer
30 views

organizing rectangles on top of each other

We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the ...
3
votes
0answers
54 views

Operational Research. (Ressource Management)

I am looking for a solution that i know exists already in the field of "Operational Research"... I Just can't put my finger on the name of the thing. An heuristic to solve a very common and simple ...
0
votes
0answers
28 views

Algorithm Request, choosing rows from a sparse table of integers to sum to a minimum row value

I'm writing some software, and one part of the software needs to be able to solve this problem as well as possible. Consider a table of integers and goal, for example: $$T = \begin{array} ...
0
votes
1answer
80 views

Jacobian in Levenberg-Marquardt for 4-Parameter equation

I am trying to fully understand how I can use Levenberg-Marquardt to minimise a 4 parameter equation. There are lots of fancy programs to do this but the documentation about the mathematics is ...
0
votes
1answer
106 views

nth root algorithm: value of initial guess?

I wonder what value one would choose to maximize efficiency to make an initial guess for the nth root algorithm (supplementary constraint: only with the five operations: +, -, *, /, % (integer ...