All Questions
Tagged with nonlinear-programming or nonlinear-optimization
639 questions
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 ...
- 431
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
26
votes
1
answer
1k
views
Finding the closest matrix to $\text{SO}_n$ with a given determinant
$\newcommand{\GLp}{\operatorname{GL}_n^+}$
$\newcommand{\SLs}{\operatorname{SL}^s}$
$\newcommand{\dist}{\operatorname{dist}}$
$\newcommand{\Sig}{\Sigma}$
$\newcommand{\id}{\text{Id}}$
$\newcommand{\...
- 6,741
14
votes
3
answers
2k
views
How to prove $e^x\left|\int_x^{x+1}\sin(e^t) \,\mathrm d t\right|\le 1.4$?
Related question asked by me on Math SE a few days ago: How to prove $e^x\left|\int_x^{x+1}\sin(e^t) \,\mathrm d t\right|\le 1.4$?
A few days ago, somebody asked How to prove $ \mathrm{e}^x\left|\...
- 1,326
14
votes
2
answers
963
views
Conjecture on maximum of symmetric combinatoric function
A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture).
(The question was first asked at math.SE, ...
- 155
14
votes
1
answer
2k
views
An intuition for three different types of subgradients (proximal, regular, limiting)
I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.
These subgradients are (assume $x \in$ ...
- 249
12
votes
2
answers
1k
views
Quadratic Farkas' Lemma?
The Farkas Lemma says that if a system of linear inequalities implies
yet another linear inequality, then this last inequality can be obtained by
taking a positive linear combination of the ...
- 23k
12
votes
2
answers
350
views
A (reverse)-Minkowski type inequality for symmetric sums
Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true?
\begin{align*}
\left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...
- 1,034
11
votes
2
answers
425
views
Maximization of a cubic form over the $14$-dimensional sphere
For any integers $i$ and $j$ such as $1\le i<j\le6$, let $x_{ij}$ be a nonnegative real number.
Is it true that, given the condition
$$\sum_{1\le i<j\le6}x_{ij}^2=1,$$
the sum
$$\sum_{1\le i<...
- 128k
11
votes
1
answer
565
views
Is there a "formula" for the point in $\text{SO}(n)$ which is closest to a given matrix?
$\newcommand{\Sig}{\Sigma}$
$\newcommand{\dist}{\operatorname{dist}}$
$\newcommand{\distSO}[1]{\dist(#1,\SO)}$
$\newcommand{\distO}[1]{\text{dist}(#1,\On)}$
$\newcommand{\tildistSO}[1]{\operatorname{...
- 6,741
11
votes
0
answers
291
views
$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan
There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
- 399
10
votes
2
answers
612
views
Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$
Suppose $f:\mathbf{N} \to [0,1]$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $x,y$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ ...
- 9,722
9
votes
3
answers
2k
views
Smallest root of a degree 3 polynomial
Is it true that the smallest root $t$ of the polynomial
$$
20 t^3 - 30 t^2 + (12 - 4 \cos^2 \alpha - 4 \cos^2 \beta - 4 \cos^2 \gamma) t + \cos^2 \alpha + \cos^2 \beta + \cos^2 \gamma - 2 \cos \alpha \...
- 171
9
votes
5
answers
646
views
Software for rigorous optimization of real polynomials
I am looking for software that can find a global minimum of a polynomial function over a polyhedral domain (given by, say, some linear inequalities) in $\mathbb R^n$. The number of variables, $n$, is ...
- 7,836
8
votes
5
answers
2k
views
Prove that this expression is greater than 1/2
Let $0<x < y < 1$ be given. Prove
$$4x^{2}+4y^{2}-4xy-4y+1 + \frac{4}{\pi^2}\Big[
\sin^{2}(\pi x)+ \sin^{2}(\pi y) + \sin^{2}[\pi(y-x)] \Big] \geq \frac{1}{2}$$
I have been working on this ...
- 99
8
votes
5
answers
481
views
Nearest matrix orthogonally similar to a given matrix
Given $A,B\in\Bbb R^{n\times n}$ is there technique find $$\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_F\mbox{ or }\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$$ within additive approximation error in $\...
- 13.9k
8
votes
1
answer
690
views
How many saddle points can a quartic polynomial in two real variables have? All 9?
By Bézout's theorem a quartic polynomial $p(x,y)$ can have at most 9 isolated critical points. Can all of them be saddle points?
In case of a cubic polynomial there is a mechanical way to answer this ...
- 291
8
votes
2
answers
2k
views
What is Young measure?
I read about Young measures from the book, Weak convergence methods for nonlinear partial differential equations by L.C. Evans. He introduces the concept by the following theorem:
Theorem. Assume ...
8
votes
1
answer
2k
views
Finding a point maximizing the minimal distance to a set of points
Given a set of of $N$ points $\{\mathbf x_i \in \mathcal{S}^d\}_{i = 1, \ldots, N}$, where $\mathcal{S}$ is a set of possible values, how can I find the point $\mathbf x^*$ that maximizes the minimum ...
- 183
8
votes
2
answers
380
views
Projecting onto space of matrices with spectral radius less than one
Consider the space
$$ S = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(|A|) \leq 1 \right\}$$
where $|A|$ is the entry-wise absolute value. Given a matrix $M \in \mathbb{R}^{n\times ...
- 123
8
votes
1
answer
497
views
Higher dimensional scutoids?
The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
- 10.5k
8
votes
0
answers
278
views
The busy Star Guardian
On an infinite plane, the Prime Star has disintegrated into four constituent stars, the North Star, the South Star, the East Star and the West Star, each traveling at a constant speed of $1$ in their ...
- 2,619
8
votes
0
answers
210
views
Concavity of product and ratio of sums
Apologies if this question is not appropriate for MathOverflow. I have asked at Math.StackExchange without success.
Consider the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined as
$$
f(x)=\...
- 379
8
votes
0
answers
196
views
Solving matrix equation $X^{-1}=\sum_{i=1}^n D_i X A_i$
Does anybody know an algorithm to solve the following matrix equation?
$$X^{-1}=\sum_{i=1}^n D_i X A_i$$
where $D_i$s are diagonal and $A_i$s are symmetric matrices.
It would be great to have an ...
7
votes
1
answer
1k
views
Can a cubic polynomial in two real variables have three saddle points?
Is there a cubic polynomial $c(x,y)$ with exactly 3 saddle point critical points?
In other words, can a cubic polynomial in two variables have three critical points, all of which are saddle points? ...
- 291
7
votes
1
answer
371
views
An elementary inequality for three complex numbers
The following problem arose in asymptotic analysis of difference equations.
Numerical maximization suggests that for all nonzero complex numbers $a,b,c$ we have
$$h\big(r(a,b,c),r(b,c,a),r(c,a,b)\big)...
- 128k
7
votes
2
answers
1k
views
Maximum average Euclidean distance between $n$ points in $[-1,1]^n$
For my research I have designed a metric that is based on the average Euclidean distance between $n$ points in the $n$-dimensional hypercube $[-1,1]^n$. However, I have a hard time finding the maximal ...
- 71
7
votes
1
answer
313
views
Surprisingly simple minimum of a rational function on $\mathbb R_+^n$
Motivation:
The following problem has occurred in a study of energy dissipation in a chain of coupled, damped oscillators.
The problem:
Let me define specific rational functions $f$, $g$, and $...
- 686
7
votes
1
answer
422
views
Generalization of the equilateral triangle?
I consider points in the two-dimensional plane.
An equilateral triangle is a set of three points in the plane which are equidistant.
Suppose now I have $n$ points $x_1,...,x_n$. What is the ...
- 840
7
votes
1
answer
838
views
How to solve optimization problems on manifolds?
I encountered some optimization problem on the special Euclidean group SE(3) at work and wonder how to solve it. The current approach of my colleagues was to use a local parametrization of the ...
- 198
7
votes
2
answers
568
views
Proving an infinite norm minimization problem has finite support (non-convex p-norms)
Consider an optimization problem over infinite variables:
$$
\begin{align}
\min_{x}~& {\left\lVert{x}\right\rVert }_p
\\
\text{s.t}~& \left\langle x, a_n\right\rangle \ge 1~,~\forall n=1,\...
- 673
7
votes
1
answer
373
views
Is the solution of this optimization problem always positive semidefinite?
We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:
$$ \sup_H \left\{ x^*...
- 73
7
votes
1
answer
483
views
Generalized Rayleigh-quotient gradient flow on Grassmannian
The following theorem appears without proof in :
Helmke, Uwe, and John B. Moore. Optimization and dynamical systems. Springer Science & Business Media, 2012.
Let $A$ be a symmetric $n\times n$ ...
- 318
7
votes
2
answers
632
views
Determining if a quadratic form is non-negative if variables are non-negative
Let $f(x_1,\dots,x_n) = \sum_{1 \le i \le j \le n} c_{i,j}x_ix_j$ be a homogeneous quadratic form. Is there a quick-ish way to determine whether $f(x_1,\dots,x_n) \ge 0$ for all $x_1,\dots,x_n \ge 0$?
...
- 1,355
7
votes
2
answers
4k
views
Quadratically constrained linear program (QCLP) over $x$ with the linear constraint $x = Az$
I have a problem that looks very much like a norm-constrained linear program, but with an extra constraint that is unusual for me. The problem is the following. Given a matrix $A$ and a vector $w$,
$$...
- 93
7
votes
3
answers
698
views
How to solve such an optimization problem
I encounter the following optimization problem, but I can't solve it.
Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...
- 71
7
votes
0
answers
469
views
Analytic expression for the Tsirelson bound of the I3322 inequality?
Finding Tsirelson bounds for Bell inequalities is a well-loved problem in quantum information theory. A famous case where it is still open is for the I3322 inequality. In this paper Pál and Vértesi ...
- 702
7
votes
0
answers
217
views
Characterizing matrices with rank constraint
Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
- 13.9k
6
votes
2
answers
2k
views
Find minimum-area ellipse which encloses two ellipses
I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...
- 61
6
votes
2
answers
718
views
Can we decompose a polynomial into difference of convex polynomials?
Given a multivariate polynomial $p(x_1, ..., x_n)$ on $\mathbb{R}^n$, can we always decompose it into the difference of two convex polynomials? i.e., is there a pair of convex polynomials $f$ and $g$, ...
- 81
6
votes
2
answers
492
views
Does this polynomial have a real zero less than or equal to $1/2$?
Is the smallest root $x$ of
$$
10x^{3}-30x^{2}+\left(30-2\sum_{1\le i<j\le6}\cos^{2}\alpha_{ij}\right)x\\
+2\sum_{1\le i<j\le6}\cos^{2}\alpha_{ij}-\sum_{1\le i<j<k\le6}\cos\alpha_{ij}\cos\...
user538574
6
votes
2
answers
8k
views
How to fit the parameters of differential equations with known data?
I have the following data from chemical kinetics research to fit the parameters of ordinary differential equations:
$$
\left[
\begin{array}{ccccccc}
\text{No.}& t & y_1(t)&y_2(t) & ...
- 197
6
votes
1
answer
1k
views
Solve equation with matrix variable
I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1,\ldots,K$ are known, and are positive definite matrices. $\Omega$ also has to ...
- 173
6
votes
1
answer
536
views
Bound on the sum of arguments
Problem: Show that for all real $s,t,u$ and all complex $z$ with $|z|<1$ one has
$$(*)\qquad \arg\frac{1-zf(s-u)}{1-zf(s+u)}
+\arg\frac{1-zf(t+u)}{1-zf(t-u)}<\pi,
$$
where $f$ is the ...
- 128k
6
votes
1
answer
155
views
Adding constraints as penalty with $\| \cdot \|_0$ norm
In the paper Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries (page 2), the authors rewrite the minimization problem
\begin{align}
\min_{\alpha \in \mathbb R^k} \| \...
- 113
6
votes
1
answer
596
views
Combinatorial equation system with exponentially many equations in quadratic many variables
A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of ...
- 155
6
votes
1
answer
1k
views
Solving a linear program, but over the unit sphere
I want to solve a linear program but with a subset of the variables taken from a unit sphere.
That is, given fixed $\textbf{c} \in \mathbb{R}^{n}$, $\textbf{A} \in \mathbb{R}^{m \times (n+k)}$,
I want ...
- 63
6
votes
1
answer
5k
views
max-min optimization problem
I'm curious if there is any nice way to approach solving the following kind of optimization problem. Given a $n \times m$ matrix $A = (a_{ij})$, I want to solve
\begin{align*}
& \max_{c}\min_{1 \...
- 161
6
votes
0
answers
255
views
Concavity of a function implicitly defined by a polynomial
Consider the following system of $n$ equations:
\begin{equation}f_j^2 = x_j^2\sum_{i=1}^n A_{ij} f_i
\tag{$\star$}
\end{equation}
where $A_{ij}\geq 0$ are known constants and where $x_j>0$ for ...
- 379
6
votes
0
answers
77
views
Bounding volume of cell in complement of zero set
I am given an integer polynomial $f \in \mathbb{Z}[X_1, \ldots, X_n]$ of bounded degree and bounded coefficient size. The polynomial's zero set partitions $\mathbb{R}^n$ into cells. What I am looking ...
- 1,312