Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
77
questions
30
votes
5
answers
13k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
1
vote
1
answer
189
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
34
votes
3
answers
3k
views
What is the best way to peel fruit?
A mango made me wonder about this. (See also this question, which is in a similar spirit.)
Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset \mathbb{R}^3$...
29
votes
1
answer
1k
views
Can a real quartic polynomial in two variables have more than 4 isolated local minima?
This question: "Can a real quartic polynomial in two variables have at most 4 isolated local minima?" came up in this post on Math SE but with no answer so far.
Finding examples of 4 ...
28
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
21
votes
4
answers
2k
views
Fairest way to choose gifts
Suppose that a parent brings home from a trip $2n$ gifts of roughly equal value for his/her two children. The children get to choose one at a time which gifts they want. What is the fairest way to ...
15
votes
3
answers
1k
views
Optimal inspection path on a sphere
Suppose you would like to "inspect" every point of a unit-radius
sphere $S \subset \mathbb{R}^3$ by walking along a path $\gamma$
on $S$, but you can only see a distance $d$ from where you ...
12
votes
1
answer
356
views
An averaging game on finite multisets of integers
The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...
8
votes
1
answer
2k
views
Symplectic block-diagonalization of a real symmetric Hamiltonian matrix
Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal?
Being ...
7
votes
2
answers
3k
views
Conic hulls and cones
Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
5
votes
2
answers
1k
views
Minimum of squared sum minus sum of squares
I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
3
votes
2
answers
375
views
Generalized Moore Graphs
A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore ...
2
votes
0
answers
103
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
2
votes
0
answers
107
views
Maximization of an integral functional over a closed convex set
I want to maximize $$F(w):=\sum_{1\le i,\:j\le2}\int\lambda^{\otimes2}({\rm d}(x,y))\left(w_i(x)f_j(x,y)\wedge w_j(y)f_i(y,x)\right)g_{ij}(x,y)$$ over the closed convex set $$S:=\left\{w\in{\mathcal L^...
1
vote
1
answer
141
views
How can we calculate the generalized gradient of $L^2\ni x\mapsto a\min(x(s),by(t))$?
Let $(T,\mathcal T,\tau)$ be a measure space, $a,b\ge0$, $s,t\in T$ and $$f(x):=a\min(x(s),bx(t))\;\;\;\text{for }x\in L^2(\tau).$$
How can we calculate the generalized gradient $\partial_Cf(x)$ of ...
13
votes
5
answers
3k
views
Application of polynomials with non-negative coefficients
Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...
38
votes
5
answers
6k
views
When does symmetry in an optimization problem imply that all variables are equal at optimality?
There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such ...
33
votes
2
answers
3k
views
Functions whose gradient-descent paths are geodesics
Let $f(x,y)$ define a surface $S$
in $\mathbb{R}^3$ with a unique local minimum at $b \in S$.
Suppose gradient descent from any start point $a \in S$
follows a geodesic on $S$ from $a$ to $b$.
(Q1.)
...
27
votes
1
answer
976
views
The lion and the zebras
The lion plays a deadly game against a group of $N$ zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the $N$ zebras may ...
20
votes
2
answers
3k
views
How to optimally bet on a biased coin?
A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you.
You start with a total ...
16
votes
1
answer
1k
views
What braking strategy is most fuel-efficient?
You notice a stop-light ahead of you and it is currently red. You can't run the red light, so you will have to brake, but braking wastes energy and you want to be as fuel efficient as possible. What ...
16
votes
1
answer
862
views
A simple stochastic game
An individual, henceforth called the runner starts at the center of an open two dimensional square $\Omega$ of side length $r \geq 2$.
At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
13
votes
2
answers
713
views
Is there a class of optimization problems more general than semidefinite programming?
I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there ...
13
votes
4
answers
576
views
Minimal-length embeddings of braids into R^3 with fixed endpoints
(Apologies in advance for any imprecision in the following; I am a computer scientist and regret never having taken an actual course on topology.)
One way to define the pure braid group $P_n$ is as ...
10
votes
1
answer
302
views
In what area of study does one encounter this principle in timetabling?
A while ago I saw an image like the one below in a lecture, which was supposed to represent a rail network in a (square) city:
The circles represent trains that are moving either North/South or East/...
10
votes
2
answers
8k
views
When do maximum and expectation commute?
Hi, I'm looking for conditions on $G(t,x)$ such that
$$
\sup\limits_{t\in [0,1]}E[G(t,X)]=E[\sup\limits_{t\in [0,1]}G(t,X)]
$$
where $X$ is a random variable (it's easy to see that $\sup\limits_{t\in [...
10
votes
1
answer
397
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
10
votes
4
answers
897
views
The distribution of the shortest path through $n$ points
In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...
8
votes
0
answers
229
views
Decay of orthogonal contributions in a random set of vectors
Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:
$$\frac{v_1}{\|v_1\|},\...
8
votes
2
answers
919
views
Applications of Topological Complexity of configuration space
I'm starting to work on topological complexity of configuration spaces.
Articles say that this field has applications in robotic and control theory. One of the important articles belongs to Michael ...
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
7
votes
1
answer
396
views
Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?
"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...
7
votes
1
answer
489
views
Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently
What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and ...
7
votes
3
answers
263
views
Shrinking subset and product
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|...
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
6
votes
1
answer
315
views
The Euclidean norm and $k$ largest elements
This is not a homework problem, although I fear it may turn out to be at that level. For any nonnegative $x\in\mathbb{R}^n$, let $f_k(x)$ be the sum of the $k$ largest values in $x$, and define $$f(x)...
6
votes
1
answer
2k
views
Non-negative quadratic maximization
For a given symmetric and positive semidefinite $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \ x\geq 0} x^T A x.$$
Here, $x\geq 0$ indicates that $x$ must be component-wise ...
5
votes
3
answers
6k
views
Optimization over permutation?
Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > ...
5
votes
1
answer
370
views
Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum
Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...
5
votes
2
answers
605
views
Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2")...
5
votes
0
answers
421
views
The Gömböc and monostatic objects
This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...
5
votes
2
answers
619
views
Intuition behind Gubinelli derivative
I apologise for the confusion of the following sentences. I'm lazy to give more information about Rough path theory as Is a fairly broad subject.
On page 14 of "A Course on Rough Paths
With an ...
4
votes
2
answers
1k
views
Optimizing over matrices with spectral radius <1?
Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so ...
4
votes
4
answers
3k
views
Minimizing the modulus of a polynomial around a circle
I'm probably missing something elementary here, but I guess the only way to be sure is to ask here.
Now, I have encountered a situation where given an nth-degree polynomial $p_n(z)$ with complex ...
4
votes
2
answers
344
views
Minimising the squared sum minus the sum of squares
I'd like to know how to show $$\min_{\Vert x\Vert_2=1=\Vert y\Vert_2}\left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2\geq -1/2.$$
The inequality is discussed in a previous post Minimum of ...
4
votes
1
answer
512
views
Generalisation of the squared sum minus the sum of squares inequality
I'd like to know how to prove
$$\min_{\Vert x\Vert_2=1=\Vert y\Vert_2}\left|\sum_{k=1}^nx^*_ky_k\right|^2-\sum_{k=1}^n|x_k|^2|y_k|^2\geq -1/2$$
for $x,y\in\mathbb{C}^n$ with $\Vert x\Vert_2=\Vert y\...
4
votes
3
answers
151
views
Find distribution that minimises a function of its moments
Imagine a probability density function $f(x)$, defined for positive $x$, and let's note its $n$th non-centred moment $x_{n}$. The mean $x_{1}$ is fixed (and positive).
How can I find $f(x)$ that ...
4
votes
1
answer
442
views
Controlling subsolutions of a second order linear ODE
Let $f:[0,\infty) \to \mathbb{R}$ obey the differential inequality
$$f'' - 2\alpha f' + 2\alpha f \leq 0$$
where $0 < \alpha < 2$ is some constant. If $f(0) = 0$ and $f'(0) = 1$, can I say that $...
4
votes
0
answers
138
views
Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum - part II
Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...