3
votes
2answers
39 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
0
votes
0answers
26 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
6
votes
0answers
97 views
+50

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
2
votes
0answers
78 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
1
vote
0answers
37 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
0
votes
1answer
30 views

Evolutionary algorithm

Can someone provide me a good reference for the CMA-ES algorithm? I'm new in the world of optimization and just reading the author reference doesn't help me a lot. I know the basic idea of a genetic ...
3
votes
2answers
20 views

Smallest linear combination of a set of vectors

I'm searching for an algorithm to accomplish a (hopefully) simple task. If I have a set of vetors, (e.g. $\left( ...
0
votes
0answers
24 views

Alternative to Hungarian Algorithm to determine minimum cost?

Is there a graphic calculator (CAS technology) method to solve minimum cost problems/allocations that are normally completed with the Hungarian Algorithm... Hungarian Algorithm is time consuming, ...
2
votes
0answers
38 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
2
votes
1answer
73 views

How can I find the point (X, Y, Z) which minimizes this quantity?

I have a number of equally powerful light sources $L_i, 1 \le i \le N$ at points within a cube $(x_i, y_i, z_i), -1 \le x_i, y_i, z_i \le 1$. The intensity of each light falls off with distance ...
3
votes
2answers
46 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
2
votes
1answer
20 views

How to efficiently compute the pareto front in a >2 dimensional multi-objective case?

I'm currently working on an optimization problem with 4 different objective functions and need an algorithm to compute the pareto frontier from several "solutions" to that problem. I already found ...
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
50 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
19 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
55 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
274 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
42 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
18 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
38 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
45 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 ...
2
votes
3answers
44 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
43 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
33 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
41 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
43 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
31 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
29 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
140 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
63 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
65 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
57 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
36 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
27 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
80 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
28 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
40 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
29 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
35 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 ...