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)

10
votes
0answers
399 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
78 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
61 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
568 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
150 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
85 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
192 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
231 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
183 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
64 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
83 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 ...
5
votes
0answers
86 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
96 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
121 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
538 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
77 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
32 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
36 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
55 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
168 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
51 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
75 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
139 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
86 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
80 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
114 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
295 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
261 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
343 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
831 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
113 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
287 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
261 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
470 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
46 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
41 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
52 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 ...
3
votes
0answers
32 views

Compactness in minimax theorem

According to Von Neuman's minimax theorem we have $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} \max_{x\in X} f(x,y)$$ for some compact sets $X$ and $Y$ and a convex (in $y$), concave (in $x$) ...
3
votes
0answers
63 views

What is the 'optimal' equal-area partition of a circle?

What is the (an?) n-partition of a circle that meets the following criteria: The boundaries of each partition can be represented as a union of finitely many finite-piecewise-smooth simple closed ...
3
votes
0answers
135 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 ...
3
votes
0answers
54 views

Are there some functions that cannot be optimized using calculus?

I've been working on a project to maximize a functions output using a genetic algorithm. However, from the limited calculus I know I thought there were methods to find the maximum of a mathematical ...
3
votes
0answers
45 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
3
votes
0answers
22 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
0answers
74 views

Finding Positive Odd Integers

$m$ is a positive odd integer. $(m+4\times 41)(m^{2}+4^{2}\times 41^{2})$ is a perfect square. Find the minimum value of $m$
3
votes
0answers
79 views

How to find the minimal path between points in a planar set with holes in it?

When I was a commuter student, I would park in a very large parking that that had a set of stairs in a corner that I had to climb. In general, I had to park far away from this corner in an almost full ...
3
votes
0answers
42 views

Find closest vector to a given vector from a particular set of vector

Let $x=\left(x_t\right)_{t=1}^n$ be a vector such that $$ x_t = \prod_{i=1}^t u_i, \tag{1} $$ where each parameters $u_i$ can take any of two value $$ u_i \in \left\{a,b \right\} = \left\{ 1.3, 0.8 ...
3
votes
0answers
107 views

Calculus of variations for implicitly defined functional

I would like to minimize a functional of the type: $$L[\gamma]=\int_a^b F(T(\gamma(t))dt$$ on the space of paths $\gamma$, where $T=T(\gamma,t)$. Now, usually I would simply apply Euler-Lagrange's ...
3
votes
0answers
41 views

Mathematical analysis of e-shop

I'm ukrainian student, studying applied mathematics in Kiev. I have an online store and some statistics data on it's work. Also I've learned a bit about optimization problems and operation reasearch. ...
3
votes
0answers
83 views

Convergence of sequences of sets

Assume we have the indicator function $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and the sequence of its approximation functions $\{ I_{\nu}(x) ...
3
votes
0answers
61 views

Optimization problem (Sum of distances)

Given an ordered sequence $x_1 \leq x_2 \leq \cdots \leq x_n $ of length $n$ and a cost function $C(i) = \sum_{j}^{n}{\left|x_i-x_j\right|}$. The goal is to minimize the cost function. How do you ...