Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.
162
votes
16answers
6k views
Optimizing response times of an ambulance corp: short-term versus average
Background: I work for an Ambulance service. We are one of the largest ambulance services in the world. We have a dispatch system that will always send the closest ambulance to any emergency call. ...
36
votes
1answer
1k views
What's the largest possible volume of a taco, and how do I make one that big?
Let $f$ be a continuous, even, positive function over some interval $I=[-a,a]$ such that the total arc length of $f$ over $I$ is at least $2$, $f(0)=0$, and $f$ is increasing on $(0,a)$. View the ...
29
votes
4answers
771 views
AM-GM-HM Triplets
I want to understand what values can be simultaneously attained as the arithmetic (AM), geometric (GM), and harmonic (HM) means of finite sequences of positive real numbers. Precisely, for what points ...
29
votes
4answers
1k views
Run away from lions in a cage
I came across an interesting problem:
There is a round cage and you are in it. Also two lions are in this cage
too. The start position is that the distance between you and both lions is
the ...
20
votes
5answers
630 views
Math Wizardry - Formula for selecting the best spell
Imagine we have a wizard that knows a few spells. Each spell has 3 attributes:
Damage, cooldown time, and a cast time.
Cooldown time: the amount of time (t) it takes before being able to cast that ...
17
votes
2answers
588 views
Largest circle between $y=x^n$ and $y=\sqrt[n]{x}$
Something I have been wondering about for a while. Let us look at the area between $x^n$ and $\sqrt[n]{x}$ when $x\in [0,1]$. Where $n$ is a positive integer.
Below is an image.
With a given n, how ...
15
votes
4answers
325 views
Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$
Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$.
What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?
14
votes
4answers
534 views
Gerrymandering/Optimization of electoral districts for one particular party
I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows:
Hey--
This is Zach from SMBC, and I have a math ...
13
votes
1answer
402 views
Minmax problem for polygons
Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ sides. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles whose vertices are some vertices of $P$. I ...
13
votes
2answers
389 views
The Farmyard problem
Problem:
There is a farmer who has a $1\text{ mile}\times 1\text{ mile}$ square piece of land. He knows that there is a completely straight pipe underneath some part of his property, but it could ...
12
votes
2answers
527 views
the least value for :$\frac{a}{b^3+54}+\frac{b}{c^3+54}+\frac{c}{a^3+54}$
For every $a,b,c$ non-negative real number such that:$a+b+c=1$ how to find the least value for :
$$\frac{a}{b^3+54}+\frac{b}{c^3+54}+\frac{c}{a^3+54}$$
11
votes
6answers
1k views
How to prove the sum of squares is minimum?
Given $n$ positive values. Their sum is $k$.
$$
x_1 + x_2 + \cdots + x_n = k
$$
The sum of their squares is defined as:
$$
x_1^2 + x_2^2 + \cdots + x_n^2
$$
I think that the sum of squares is ...
11
votes
6answers
265 views
Maximizing the sum $\sum\limits_{i=1}^nx_ix_{i+1}$ subject to $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$
Is there an efficient way of solving the following problem?
Given $x_i\in \mathbb R$, and that $\sum\limits_{i=1}^nx_i=0$ and $\sum\limits_{i=1}^nx_i^2=1$. I want to maximize ...
11
votes
3answers
357 views
Combinatorial optimization - improve performance
I am writing a program to solve a combinatorial optimization problem. I have been working on an algorithm that gets the desired results, but I am having difficulties getting the algorithm to perform ...
11
votes
1answer
217 views
Arnol'd's trivium problem #68
I came across this blog that says that its French version has answers to most of Arnol'd's trivium problems, and I figured I'd try my hand at some of the ones they don't have. Number 68 raised my ...
11
votes
2answers
384 views
2 circles and one ellipse and minimum area problem.
2 circles ($r_1 \neq r_2$) and one ellipse touch each other as shown in Figure-1. What is the minimum area (A) among them ? Please consider $a,b,r_1,r_2$ given values(constants). Let's imagine we ...
10
votes
2answers
675 views
Derivation of the method of Lagrange multipliers?
I've always used the method of Lagrange multipliers with blind confidence that it will give the correct results when optimizing problems with constraints. But I would like to know if anyone can ...
10
votes
2answers
301 views
Does a polynomial that's bounded below have a global minimum?
Must a polynomial function $f \in \mathbb{R}[x_1, \ldots, x_n]$ that's lower bounded by some $\lambda \in \mathbb{R}$ have a global minimum over $\mathbb{R}^n$?
10
votes
5answers
417 views
Why is convexity more important than quasi-convexity in optimization?
In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
10
votes
4answers
2k views
How do Lagrange multipliers work to find the lowest value of a function subject to a constraint?
I have been using Lagrange multipliers in constrained optimization problems, but I don't see how they actually work to simultaneously satisfy the constraint and find the lowest possible value of an ...
10
votes
3answers
538 views
Why is $(0, 0)$ not a minimum of $f(x, y) = (y-3x^2)(y-x^2)$?
There is an exercise in my lists about those functions:
$$f(x, y) = (y-3x^2)(y-x^2) = 3 x^4-4 x^2 y+y^2$$
$$g(t) = f(vt) = f(at, bt); a, b \in \mathbf{R}$$
It asks me to prove that $t = 0$ is a ...
10
votes
1answer
204 views
Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM
Question:
Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$)
More precisely, for $n \in \mathbb{N}$, we can a find ...
10
votes
3answers
957 views
Best fit ellipsoid
Given a collection of points $P \subset \mathbb R^3$, a crude characterization of the "shape" of $P$ is sometimes given by the principal components. We construct a covariance matrix, e.g., if $P$ is ...
10
votes
1answer
298 views
A (mathematically) sound investment strategy
It is common wisdom in the investment community that a long-term investor saving for his future would do well to invest in high-risk/high-return assets when he is young, slowly switching his portfolio ...
9
votes
4answers
3k views
Do dynamic programming and greedy algorithms solve the same type of problems?
I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically,
As far as I know, the type of problems that dynamic ...
9
votes
2answers
271 views
Can there be a cubical bubble?
Although not physically perfect, a reasonable mathematical model for a bubble's shape is that it minimizes surface area subject to fixed volume.
A single floating bubble is usually a sphere, but ...
9
votes
3answers
245 views
Find the maximum and minimum of $\sum_{i=1}^{n-1}x_ix_{i+1}$ subject to $\sum_{i=1}^nx_i^2=1$.
Find the maximum and minimum of
$$
\sum_{i=1}^{n-1}x_ix_{i+1}
$$
subject to
$$
\sum_{i=1}^nx_i^2=1
$$
for all $n\in\mathbb{N}-\{1,0\}$.
9
votes
2answers
517 views
Augmented Reality Transformation Matrix Optimization
i am a software developer, i'm working on an Augmented Reality system.
I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast.
Here's the situation:
...
9
votes
2answers
383 views
A numerical optimization problem with a convolution in the constraint
I have a problem of the following form:
minimize $\|Dx\|_2$
subject to $\|x*x\|_2 = 1$
where $x\in\mathbb R^n$, $D$ is a given diagonal matrix of positive entries, and $*$ represents convolution, ...
8
votes
4answers
966 views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i ...
8
votes
6answers
191 views
Optimization problem (in linear algebra course!)
Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots +a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$?
I'd ...
8
votes
2answers
622 views
Minimize exponential function over an interval
I want to minimize the function
$$f(x) = e^{ax^2} + e^{b(1-x)}$$
with respect to $x$ (where $a$ and $b$ are constants), subject to the constraint that $0 \leq x \leq 1$.
I know that $x = 0$ and $x = ...
8
votes
1answer
772 views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
8
votes
2answers
85 views
How to find the minimum of f(x)?
I need to find the minimum of $f(x)$ with
$$f(x)=(\sin(x)+\cos(x)+\tan(x)+\cot(x)+\sec(x)+\csc(x))^2$$
Could you help me with some clues?
8
votes
3answers
2k views
Lagrange Multipliers with Inequality Constraints
I do not have much experience with constrained optimization, but I am hoping that you can help. My current problem involves a more complex function, but the constraints are similar to the ones below. ...
8
votes
2answers
294 views
Optimization of the area of a cross inscribed in a circle
I've really been scratching my head over this optimization problem. "Consider a symmetric cross inscribed in a circle of radius $r$." The length from the center of the cross to the middle of one of ...
8
votes
1answer
197 views
Simple question: the double supremum
Let $f:A\times B\to \mathbb R$. Is it always true that
$$
f^* = \sup\limits_{a\in A,b\in B}f(a,b) = \sup\limits_{a\in A}\sup\limits_{b\in B}f(a,b).
$$
I proved it by the $\varepsilon$-$\delta$ ...
8
votes
1answer
205 views
Minimizing Lagrangian with two functions
I read this problem where I have to minimize a functional $E[L]$ using calculus of variations, but I'm not sure what is the procedure to follow.
The functional is the expected loss:
$$E[L] = ...
7
votes
1answer
210 views
Maximum subset sum of $d$-dimensional vectors
This is a $d$-dimensional generalisation of the post Inequality with Complex Numbers. (See my comment under Robert Israel's answer.)
Generalising Potato's proof for $d$-dimensions, we can show the ...
7
votes
3answers
2k views
Gradient Descent with constraints
In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method:
$$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$
where $\alpha_k$ is the step size ...
7
votes
2answers
323 views
Generalization of the Sultan's dowry problem
We know the solution of the Sultan's dowry problem:
To reject the first $n/e$ candidates and then to select the first who exceeds the best of the sample.
How to find the best strategy if we want ...
7
votes
3answers
540 views
Understanding the concept behind the Lagrangian multiplier
I've been trying to understand the principles behind the Lagrangian multipliers and I think I've got a rough understanding of it. Would appreciate it if you guys could help me answer a few questions!
...
7
votes
1answer
295 views
Manifold with minimum surface distance between two points
The book "The World is Flat" uses flatness as a metaphor for a global economy. In fact, a spherical world would seem to be better than a flat world in terms of reducing the distances between two ...
7
votes
3answers
447 views
Decomposing a discrete signal into a sum of rectangle functions
Hello math@stackexchange community !
I have a simple question that seems to have a non trivial answer.
Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
7
votes
1answer
255 views
invex functions and their usefulness?
An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
7
votes
1answer
179 views
Stochastic assignment problem
Given an $n \times n$ real matrix $C$, we can try to maximize
$$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)}
$$
over $\pi \in S_n$, the set of all permutations on $n$ objects. What can one say ...
7
votes
1answer
149 views
Practical applications of the $L^p$ norm when $p \neq 1,2,\infty$
I'm roughly familiar with the concept of $L^p$ norms -- what they represent and how they are computed -- though I am far from educated in functional analysis in general. For reasons that are more or ...
7
votes
1answer
500 views
Looking to find the largest rectangle, by area, inside a polygon
I'm looking to print text inside a polygon, programmatically. I'd like to find the largest rectangle to position the text inside the polygon out of a sub set of rectangles, ie those oriented with ...
7
votes
3answers
355 views
Optimization problem for a parity-check code
I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
7
votes
1answer
216 views
How to compute the change in the angle between two unit norm vectors as the $\ell_1$ norm of one vector changes?
Motivation
Suppose that $u \in \mathbb{R}^d$ is a unit-norm vector, $\|u\| = 1$, $a, b, c$ are some positive constants and $\xi \in [0,1]$ is another constant (usually chosen close to 1). I am ...
