1
vote
1answer
23 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
12 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
32 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
108 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
39 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
32 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
36 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
17 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

Maximum Set Selection Problem

Mike has N different items. He has M orders of customers and each customer has a set of items they want. Customer will not accept partial order. So Mike can give one item to atmost 1 customer. Find ...
0
votes
0answers
15 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
112 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
52 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
15 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
56 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
16 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
60 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
47 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
24 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
24 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
68 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
26 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
38 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
59 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
30 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
55 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
28 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 [ ...
0
votes
1answer
25 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
45 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
76 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
51 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
44 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
27 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
44 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
24 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
63 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
71 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 ...
2
votes
0answers
76 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
3
votes
1answer
263 views

Proving that a greedy algorithm yields the optimal solution for a problem

I'm a college computer science student, working on a project. In my project i have an optimization problem, which i belive is optimally solveable with a greedy algorithm approach. In every case i have ...
3
votes
0answers
39 views

Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
1
vote
0answers
150 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
2
votes
2answers
131 views

Allocation optimization problem

Imagine that I have $1$ million dollars which I want to invest. I have a set of $N$ elements in which I can put the money and obtain a revenue. Each element has a function that determines how much ...
1
vote
1answer
46 views

How to schedule different planks to form bridges

Suppose we want to walk from place $A$ to place $B$, but there are several rivers between them. In order to walk from place $A$ to place $B$, we need to build a bridge for each river. We have ...
3
votes
1answer
68 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
5
votes
4answers
173 views

Looking for a significant example that highlights the suboptimality of the greedy algorithms

A week from now, I'll have to present my work to a bunch of coworkers who aren't used to the optimisation world and terminology. One of the main algorithms I implemented uses a greedy type algorithm ...
1
vote
0answers
96 views

Algorithm of projection

Suppose $S$ is a compact surface in $\mathbb{R}^{3}$ defined by a sufficiently smooth level set function $f$, that is, $S=\{s: f(s)=0\}.$ I am studying an algorithm that projects a point $x_{0}$on ...
0
votes
1answer
127 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial ...
1
vote
1answer
143 views

Minimize the sum of distance under maximum norm

Given a set of points (Xi, Yi). I need to find a point (doesn't have to be in the given set) that minimize the sum of distance to the other points. The tricky part is the distance is measured by ...
0
votes
1answer
93 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...