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
289 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
427 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
99 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
163 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
70 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
597 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 I can ...
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
88 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
216 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
236 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
192 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
80 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
143 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
107 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
143 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
590 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
78 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
91 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
32 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
41 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
41 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
58 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
174 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
58 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
81 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
188 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
297 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
268 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
373 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
898 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
114 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
300 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
284 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
484 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
30 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
49 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
31 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 ...
3
votes
0answers
25 views

Find lone peak with high sampling cost

(I'm not sure if this is the correct stackexchange place to ask; please redirect me if it doesn't belong here.) I have a 2D function f(x,y) which is (near-)zero ...
3
votes
0answers
40 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
3
votes
0answers
36 views

Add vectors from a set to reach the goal vector, using the minimum possible cost

I am trying to solve a problem in an optimal way. The problem is as follows: We have an n-dimensional space In this space, we have a "finish" point with n coordinates, all non-negative We have a set ...
3
votes
0answers
47 views

Finding L^1 centers of sets of probability distributions

Let $\mathcal{P}^n = \{ x \in \mathbb{R}^n : x \geq 0, \sum x = 1\}$. Suppose I have $p_1, \ldots, p_m \in \mathcal{P}^n$. I want to find an $L^1$ center for these points. i.e. $q \in \mathcal{P}^n$ ...
3
votes
0answers
61 views

Normalize gradient

I want to minimize a function $f \, : \, \mathbb{R}^{N} \, \longrightarrow \, \mathbb{R}$ (with $N \in \mathbb{N}^{\ast}$. In my problem, $N = 315$). I know that $f$ is differentiable on ...
3
votes
0answers
48 views

Finding disjoint intervals from Cantor Set

Consider $C$ the classic Cantor ternary set in $[0,1]$. I am interested in the following problem: Find the largest constant $0<k<1$ such that it is true that any interval $[a,b] \subseteq ...
3
votes
0answers
60 views

Time-optimal control - Coupled system of equations, control to the origin

I want to find the time-optimal control to the origin $\underline 0$ for the following: $\dot{x}_1=-3x_1 + x_2$ and $\dot{x}_2 = x_1 - 3x_2 + u$, $|u|\leq 1$ How do I go about doing this. I ...