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.

learn more… | top users | synonyms (5)

19
votes
0answers
350 views

Can Three Equilateral Triangles with Sidelength $s$ Cover A Unit Square?

A previous question on the site asked for a short proof of the fact that three equilateral triangles with unit side length cannot be arranged to cover a square with unit side lengths. Given the truth ...
10
votes
0answers
434 views

Is the layout of Burning Man's city “grid” optimal?

My intuition is that the layout of Burning Man's city "grid" optimizes for the smallest sum of all distances between any two points on the map. Am I correct? Is the proof obvious? Or is there another ...
7
votes
0answers
216 views

Maximal minimum for a sum of two (or more) cosines

Please prove (or disprove, and give the correct answer): $$2 =\mathrm{argmax}_{r\geq 1}\min_{x\in \mathbb{R}}\left[\cos\left(x\right)+\cos\left(rx\right)\right] $$ In other words, find $r \geq 1$, ...
7
votes
0answers
107 views

Consider the problem minimize $f(x)= x^4 −1. $

I am studying for a test and I found this problem in the textbook that I'm using, there may be a conceptual problem that I'm coming across. My test is on unconstrained optimization (multi-variable) ...
6
votes
0answers
164 views

The minimum of $I_{n,k}=\int_0^{2\pi}\sqrt{3+2\cos(nx)+2\cos(kx)+2\cos(nx+kx)}dx$ is attained for $k=n$

I have the following conjecture: ``For each given $n\in\mathbb{N},\ n\ge 2$ the minimum of the sequence of integrals $I_{n,k}=\int_0^{2\pi}\sqrt{3+2\cos(nx)+2\cos(kx)+2\cos(nx+kx)}dx,\ k=1,2,\dots,n$ ...
6
votes
0answers
98 views

Condition for trigonometric inequality

I want to prove the following statement: Suppose $\frac{1}{4}(\cos(\theta_1)+\cos(\theta_2))^2+\lambda^2(a\sin(\theta_1)+b\sin(\theta_2))^2\leq 1$ holds for all $\theta_1,\theta_2\in[-\pi,\pi]$, then ...
6
votes
0answers
74 views

How to solve this equation (may be with least squares)?

I have a system of linear equations in the following form. How can I solve it? $$\operatorname*{argmin}_{a,b} \sum_{i,j} \left( \left| X(i,j)-aY(i,j)\right|-b \right)^2$$ Where $X$ and $Y$ are ...
6
votes
0answers
605 views

Optimization / personalization within clusters

I have the following optimization problem: I have a (random and very noisy) objective function $f(A, P)$, where $A$ is a vector of "observable" parameters of the input and $P$ is the parameters that ...
6
votes
0answers
155 views

Selecting a subset from a set such that a given quantity is minimized

Let $A$ be is a set of some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^A$ denote the mean Euclidean distance from the point $x$ to its $k$ nearest points in $A$ (others than $x$). Let $C ...
6
votes
0answers
89 views

Do balls optimize the boundary area for a fixed volume?

I recently saw this question, asking if the circle is the planar figure which has the least perimeter given the area. As far as I know, this is a classical problem, and the answer is affirmative. I am ...
6
votes
0answers
222 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
6
votes
0answers
238 views

Is this minimization problem NP-Complete?

We are given an $n\times(n+k)$ matrix $A$, with entries in $GF(2)$, of the form $A=\begin{pmatrix}I_n & B\end{pmatrix}$, where $I_n$ is the $n\times n$ identity matrix, and $B$ has no "zero" rows ...
6
votes
0answers
196 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
5
votes
0answers
42 views

Minimize $f(m)=\sum_{n=1}^\infty n^m / m^n $

For what real value of $m$ such that $\displaystyle\sum_{n=1}^\infty \frac{n^m}{m^n} $ is minimized? I've been told that it's equivalent of solving for $ \text{Li}_{-n}\left(\frac1n\right)$ for the ...
5
votes
0answers
82 views

Find a function that maximizes $\int_{0}^{1}f(x)\,\rm dx$ with given constraints

Find a function $f(x)$ that maximizes the following integral $$\max\int_{0}^{1}f(x)\,\rm dx\quad \text{s.t.}\quad \frac{d}{dx}ln(f(x))<0$$ $f(x)$ also continues, $f:[0,1]\rightarrow R$ and we ...
5
votes
0answers
155 views

Optimal Strategy for “I'm Thinking of a Number” Game

This question is inspired by one of the classic ways of breaking ties: the "I'm thinking of a number" game. In this game, one person thinks of a number in some range, say from $0$ to $100$ ...
5
votes
0answers
114 views

Measure minimization for a combination of overlapping sets

This problem may have been worked out before but I don't know where to start looking so I hope one of you can help me. The problem is as follows: There are $N$ variable-sized finite sets ...
5
votes
0answers
150 views

optimal road layout problem - how to convert to maths and see the shapes it makes?

I have this puzzle going round my head about optimal road layouts, but I'm a programmer not a mathematician and I don't really know how to specify it as a maths problem. Once it's well-specified I can ...
5
votes
0answers
602 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} ...
5
votes
0answers
79 views

$\int_{-\infty}^{+\infty}\left|f(g(t))-f(h(g(t)))\right| \,dt=0$ How to find $f$?

Let $h,g$ be given entire functions. Consider $$\int_{-\infty}^{+\infty}|f(g(t))-f(h(g(t)))|\, dt=0,$$ where $|\cdot|$ means modulus. How do I find non-polynomial analytic solutions for $f\,$? ...
4
votes
0answers
95 views

StackEgg optimal algorithm

What is the minimum number of days that is needed to complete the StackEgg game? (It's on the right if anyone didn't notice.) There are four markers (Questions, Answers, Users, Quality) I believe each ...
4
votes
0answers
73 views

Calculation of an expression ($\max_{U}\min_i \sum_j |U_{ij}|^2 |e_i^j|^2$)

There is an orthonormal basis $\{e_i\}(i=1,\ldots,n)$ in $\mathbb{C}^n$, each of them is represented in form of column vectors $$\begin{pmatrix} e_i^1\\ \vdots\\e_i^n\end{pmatrix}.$$ My purpose is to ...
4
votes
0answers
37 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $\min_{x} (x'Ax)$ subject to $x'Bx = x'Cx = 1$. Where A is symmetric and B and C are diagonal. Does anyone have a suggestion for an ...
4
votes
0answers
46 views

Making sense of the big world of gradient methods

There are many extensions of gradient descent: stochastic-, Nesterov accelerated-, proximal-, conjugate-, dual-, mirrored-, splitted-, coordinate- gradient descend and more. It also appears that many ...
4
votes
0answers
232 views

mathematics of chemical stoichiometry

I would like to better understand the mathematical description of chemical stoichiometry and thermodynamic chemical equilibrium. This problem has many features and I know my description might be too ...
4
votes
0answers
46 views

Is there a name for systems of equations with min and max functions included?

In a big project I'm working on, I'm running into systems of equations that look like the following: $$a = \min(b, c)$$ $$b = d^2 + a$$ $$c = \max(a + b, d)$$ Basically, nonlinear systems of ...
4
votes
0answers
59 views

Closest Pair between 2 sets of powers

Assume $a$ and $b$ are natural numbers, $A=\{a,a^2,a^3,\cdots\}$ and $B=\{b,b^2,b^3,\cdots\}$, find $\min\left|a_i-b_j\right|$ where $a_i\in A$ and $b_j\in B$. For example, if $a=3$, $b=10$, then ...
4
votes
0answers
177 views

Measuring how change in input variables contributes to output in non linear equation.

How do we measure how a variable contributes to an output as its value increases, and how it relates to other input variables? Let's say we're playing a video game, where you can buy items to augment ...
4
votes
0answers
59 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 ...
4
votes
0answers
83 views

Conditions to satisfy trigonometric inequality

I'm looking for sufficient (and necessary would be good too) conditions on $a,b,c$ such that \begin{align} a\cos\phi + b \cos 3\phi + c \cos 5\phi \geq -1 \hspace{20pt} (\forall \phi) \end{align} ...
4
votes
0answers
199 views

Properties of the projection onto a nonconvex set

Consider a set $\Omega\subseteq\mathbb{R}^n$ being "sufficiently regular", for example being the image of a $C^1$ mapping from $\mathbb{R}^p$ for some $p\ge1$. We may then consider the mapping $$ ...
4
votes
0answers
87 views

How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$

This problem looks familiar, but I don't remember its solution: $$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$ subject to $$ b^k \ge n \\ b,n,k \in \mathbb{N} $$ Does it have a name? What's ...
4
votes
0answers
81 views

Find optimal measure

Let $\Omega$ be a convex compact set in $\mathbb{R}^n$, $f\colon \Omega \to \mathbb{R}$ be a convex function. Consider an optimization problem $$ \int\limits_{\Omega}f(x)\,\mu(dx) \to ...
4
votes
0answers
117 views

Solving a system of $3 \arg \max$ equations

Considering these 3 equations: $$ \alpha_{1} = \arg \max\limits_{\alpha \geq 0} \quad \Big \{ (\alpha - 1) \big (\frac{1/\alpha}{1/\alpha + 1/2 \alpha_{2} + 1/2 \alpha_{3}} \big)^2 \Big \} \\ ...
4
votes
0answers
298 views

(easier version)What is a working example for finding the maximum of a algebraic function $f(a,b,c,d,e)$ with 4 equality …

edit 2: If you are founding an answer would be interesting to you, please upvote this question, because i may use those point in order to start a new bounty. Edit 3: Can somebody answer? Edit 4:I ...
4
votes
0answers
269 views

Universal Correlation measure — ranking correlations

I have time series data of experimental observations for two related processes. I want to measure correlation for use in further analysis. Correlation of the series changes over time and across ...
4
votes
0answers
383 views

Constraint of a Lagrange multiplier

My question concerns Lagrange multipliers and the possibility to impose constraints on the multipliers themselves. I have a Stokes flow which is solved using the Finite Element Method on a domain ...
4
votes
0answers
912 views

Convergence of Gauss-Newton method for piecewise linear functions

Notation for Gauss-Newton method Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach. ...
4
votes
0answers
115 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
4
votes
0answers
305 views

$3$D oriented bounding box optimization

Given: a set $S$ of points in $\mathbb{R}^3$. Find: the smallest oriented bounding box that contains all the points. Note, the bounding box is "oriented" and thus need not be axis-aligned. Can this ...
4
votes
0answers
285 views

Extremal curve passing through a set of points

I'm having trouble recasting the following question in a form amenable to the calculus of variations. Question: Given a set of $n$ points $P=\{(x_1,y_1),..(x_n,y_n)\}$ what is the curve passing ...
4
votes
0answers
495 views

How to Minimize A Function Where The Number of Variables is Unknown

I have a standard linear programming problems I want to solve: $$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
3
votes
0answers
31 views

Minimizing Area by Approximation

Suppose I have an increasing step function $E_c$ given by $$E_c(\phi) = \sum_{i=1}^n E_i \theta(\phi - \phi_i),$$ where $\theta$ is the Heaviside step function and $E_i$, $\phi$, and $\phi_i$ are all ...
3
votes
0answers
67 views

How to solve the Few Scientists Problem (big word problem) in its general form?

I'm trying to figure out how to solve this word problem. I'm pretty sure it involves calculus or something even harder, but I don't know how to solve the general form. Let me start with the concrete ...
3
votes
0answers
30 views

What does it mean for a problem to be time-homogenous?

(This is an associated question to Scaling in utility maximisation. $c_t$, $w_t$, $n_t$, $A$ are defined there.) I am reading that because of time homogeneity $$\sup_{(n,c)\in ...
3
votes
0answers
31 views

Shortest system of roads between 4 cities

You have $4$ cities placed on the vertices of a square of side length $1$ km. You have to come up with a system of roads such that you can reach any city from another (directly or through another ...
3
votes
0answers
37 views

Converting a max-min problem to a max problem with a constraint

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ...
3
votes
0answers
52 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
3
votes
0answers
17 views

Optimal Matching Distance

I'm stuck on problem II.5.9 from Bhatia's Matrix Analysis. The problem is as follows: Let $\{\lambda_1,\dots,\lambda_n\},\{\mu_1,\dots,\mu_n\}$ by two $n$-tuples of complex numbers. Let $$ ...
3
votes
0answers
34 views

Box Optimization: find best boxes for multiple products

I have a company that sells all kind of products and we have many issues with boxes. We are going to buy wholesale volumes, so we need to get the sizes right. We are trying to develop an algorythm ...