All Questions
Tagged with nonlinear-programming or nonlinear-optimization
639 questions
0
votes
1
answer
90
views
How to calculate the maximum dimensions of a rectangle inside two concentric circles? [closed]
If I have a rectangle ABCD such that A and B touch two points of the outer circle and CD's touches one point of the inner circle, how could the maximum dimensions of the rectangle be calculated?
...
- 17
1
vote
0
answers
79
views
Markov Chain that maximises the entropy creation rate
I am working on MERW (Maximal entropy random walk) for a project.
I want to show that given a graph G, there is $\textbf{only one}$ aperiodic markov chain on G that maximises the entropy creation rate ...
- 11
3
votes
0
answers
144
views
An optimisation problem
Let $E\subset \mathbb R^2$ be compact, convex and connected. For $p_1,\ldots, p_n>0$ with
$$\sum_{i=1}^n p_i=1,$$
and a probability measure $\nu$ supported on $E$ of density $f$, we consider
$$\...
- 1,399
0
votes
0
answers
37
views
Maximise norm over the boundary of a convex set
Let $K\subset \mathbb R^2$ be compact, convex and connected. What is the know numerical scheme to find the extremal points of $K$?
Denote by $\partial K$ the collection of all extremal points of $K$. ...
- 1,399
0
votes
1
answer
60
views
Optimizing sum of discrete minimum
Please consider the following optimization problem: Given a fixed positive natural $n < N$, and a set of functions $f_i$ over a finite domain of nonnegative outputs, s.t. $1 \le i \le N$, then we ...
- 103
1
vote
0
answers
29
views
Change in active constraints when perturbing the objective of a QP
Suppose I have a quadratic program (with positive semidefinite cost matrix) with affine (polytopic) constraints. It is known that the solution to this is piecewise affine, with the ``pieces'' defined ...
- 11
0
votes
0
answers
22
views
Alignment of unit vectors under graph-neighbor constraints with a global vector
Statement
Let $G = (V, E)$ be a connected, unweighted, and undirected graph with $n$ nodes, represented by its adjacency matrix $A$. Suppose each node $i$ is associated with a unit vector $ \mathbf{v}...
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
0
votes
0
answers
55
views
How can we tighten the bounds of the $\ell_1$-norm of $\mathbf{A}x$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$?
I am curious about the upper bound of $\|\mathbf{A}x\|_1$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$, for a specific $\mathbf{A}$ as defined below.
I know this is an NP-hard ...
-2
votes
1
answer
141
views
Prove the function $g(x,y,t)\ge1$
I have the function
$$
g(x,y,t)=\frac{(8x^2y^2+f_+(x,y,t)-\cos(2t))(8x^2y^2(1+(x+y)^2)+(x+y)^2(f_-(x,y,t)-\cos(t))+4xy(x+y)\sin(2t))}{64x^4y^4(1+(x+y)^2)}
$$
with
$$
f_{\pm}(x,y,t) = 1+2x^2+2y^2\pm4xy\...
- 375
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
5
votes
0
answers
608
views
What is the correct $L^\infty$ limit of this strange variational problem, and what does it encode?
1. On the $L^\infty$ calculus of variations:
The field known as the $L^\infty$ calculus of variations is a relatively new field that concerns itself with minimising functionals involving the supremum ...
- 6,195
4
votes
0
answers
235
views
What is the maximum tidal force between two objects with unit volumes and unit density?
Motivation for this problem
This problem arises from the fact that the derivative of the gravitational force (tidal force) in the $z$-direction between two objects $A$ and $B$, which have equal ...
- 273
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
0
votes
1
answer
84
views
Transform a matrix optimization problem into a semidefinite programming
I am working on a matrix optimization problem, and the constraints are difficult to handle.
The constraints are in the following form,
\begin{align}
\text{Given: } &b \in \mathbb{R}^n \text{ , and ...
- 11
2
votes
1
answer
754
views
On a combinatorial inequality
Is it true that
\begin{gather}
\min\left(\lambda_{\min}(M_{12}), \lambda_{\min}(M_{13}), \lambda_{\min}(M_{14}), \lambda_{\min}(M_{15}), \lambda_{\min}(M_{23}), \\ \lambda_{\min}(M_{24}), \lambda_{\...
- 178
2
votes
1
answer
96
views
Why rough path theory principle is not applied in parameter estimation of stochastic differential equation(SDE)?
My apologies if this question is not proper for this site, but I could not figure out the following. Can anyone provide insight? It is almost certain that stochastic differential equations (SDEs) can ...
- 495
4
votes
1
answer
249
views
Does this functional admit an absolute minimizer?
This is a close relative of the following problem.
Let $\Omega$ be an open, bounded subdomain of $\mathbb R^n$ with smooth boundary, and $f_i \in W^{1, \infty} (\Omega)$ a sequence of functions ...
- 6,195
1
vote
0
answers
30
views
Critical point of perturbed stratifiable function has no cluster point
Given a smooth function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ and a smooth manifold $\mathcal{M}$. Now, consider the set
$$
S(v)=\{x:0\in x\circ(\nabla_{\mathcal{M}} f(x)+N_{\mathcal{M}}(x)+v)\}.
$$
...
- 43
3
votes
1
answer
138
views
Handling absolute value and other discontinuities in numerical optimization methods that use gradients
Suppose we have difficult peak fitting problems where the the users wish to fit asymmetric peaks to their experimental data by the least squares method. One such function is illustrated below:
Here
$...
- 879
2
votes
1
answer
61
views
$k$-subset with minimal Hausdorff distance to the whole set
Let $(\mathcal{M}, d)$ be a metric space. Let $k \in \mathbb{N}$. Let $[\mathcal{M}]^k$ be the set of $k$-subsets of $\mathcal{M}$. Consider the following problem:
$$ \operatorname*{argmin}_{\mathcal{...
- 2,203
1
vote
1
answer
309
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
- 879
0
votes
1
answer
104
views
Optimality condition for strongly convex function under sparsity constraint
Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
- 399
2
votes
1
answer
203
views
Does this maximisation problem admit a finite upper bound?
Let $\mathcal M_2$ be the space of real $2\times 2$ matrices and $\mathcal S_2\subset \mathcal M_2$ be its subset consisting of positive semidefinite elements, i.e. $A\in \mathcal S_2$ iff $A$ is ...
- 1,399
1
vote
1
answer
163
views
Numerical partial differentiation of a convolution product with FFT
How can one numerically calculate the partial derivatives of a convolution function, particularly when the closed-form or analytical expressions of the derivatives are not readily available? I am ...
- 879
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
0
votes
0
answers
63
views
A maximisation problem : finite or not?
Let $\mathcal M_2$ be the space of real $2\times 2$ matrices and $\mathcal S_2\subset \mathcal M_2$ be its subset consisting of positive semidefinite elements, i.e. $A\in \mathcal S_2$ iff $A$ is ...
- 1,399
1
vote
0
answers
56
views
Extension of this maximisation problem : finite or not?
$\mathcal M$ is the space of real $d\times d$ matrices and $\mathcal S\subset \mathcal M$ is its subset consisting of positive semidefinite elements. We consider the distance the product space $\...
- 1,399
0
votes
0
answers
35
views
A question on the optimisation problem and FWL theorem
Let's say we are considering the following model:
$$
(\beta^{\star},f^{\star}) := \arg\min_{\beta,f \in \mathcal{F}} \mathbb{E}[\left(Z_i - f(X_i, E_i) - \beta^\top \boldsymbol{\tau}_{i,E_i}\right)^2|...
0
votes
2
answers
531
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
0
votes
1
answer
74
views
Clarification about this optimisation problem
Good morning everybody. First of all, I apologise to ask here the same question I asked on MSE three days ago, but I am in fact re-asking since I obtained no relevant advice. Perhaps I will hear some ...
- 149
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
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
2
votes
0
answers
72
views
Gradient descent over the set of complex symmetric matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
- 21
1
vote
1
answer
187
views
Bound the distance between two vectors on the probability simplex
Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$
$$\sup_{x>0} \...
- 135
2
votes
1
answer
426
views
How to solve an optimization problem whose optimization variable is a function?
I would like to find an optimal probability density function (PDF) $f$. Given $b$,
$$ \begin{array}{ll} \underset {f} {\text{minimize}} & C \\ \text{subject to} & 1 + \frac{b}{x} \displaystyle\...
- 21
0
votes
0
answers
44
views
How to formulate piecewise quadratic function optimization without introducing binary variables?
I have a problem with logical constraints (either-or constraints). I know that it can be solved by either big-M or complementary formulations. However, i do not want to convert it into mixed-integer ...
1
vote
0
answers
61
views
How can we calculate the Euler-lagrange equations?
In this paper https://arxiv.org/pdf/1907.09605.pdf \
let $\Omega \subset \mathbb{R}^n$ with $n \geq 1$ be a bounded Lipschitz domain with boundary $\partial \Omega$, $f: \Omega \rightarrow \mathbb{R}$ ...
- 11
0
votes
0
answers
153
views
Do we have tetration uniqueness by $ A = \inf \sum_n a_n^2 $?
Let $f$ be a real analytic (on at least $|x|<2$) and real solution of the functional equation $f(0) = 1,f(x+1) = \exp(f(x))$. For the existence of such $f$, see here.
Then
$$
f(x) = \sum_n a_n x^n ;...
- 763
1
vote
1
answer
99
views
How to interpret the vector fields $F_p(x,u,Du)$ in a Lagrangian optimization problem
Let $\Omega$ be an open bounded subset of $\mathbb{R}^n$ with $C^1$ boundary. Let
$$
\begin{matrix}
F: \mathbb{R}^n \times \mathbb{R}^N \times \mathbb{R}^{nN} \to \mathbb{R},& \\
(x,z,p) \mapsto F(...
- 217
0
votes
0
answers
77
views
Generalizations of Berge's maximum theorem
I have a parameterized optimization problem
\begin{eqnarray}
\max_{x\in D(\theta)} f(x,\theta).
\end{eqnarray}
Assumptions of the standard Berge's maximum theorem are satisfied, so the value function $...
4
votes
1
answer
287
views
Local maxima of the sum of Gaussian functions in *multiple dimensions* are always strict local maxima - prove/disprove/prove conditionally?
This is a follow up of the question in one dimension, that asked to show that the all the maxima of the sum of Gaussian
$$f_n(x):= \sum_{i=1}^{n}e^{-(x-x_i)^2}, x_1 < x_2 < \dots < x_n$$
are ...
- 1,467
1
vote
0
answers
62
views
Under which condition, such that all second-order critical points satisfy $\sum_j\cos(\theta_i-\theta_j)>0$ for all $i\in[n]$?
Consider the following non-convex function
$$E(\theta):=-\sum_{i,j}A_{ij}\cos(\theta_i-\theta_j)$$
where $A$ is a symmetric, diagonal-free matrix whose non-diagonal element are $\pm 1$. In other words,...
- 49
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
3
votes
1
answer
233
views
Min problem on integers
Let $n$ be any integer greater than $2^{10^6}$. Given any $s\le (\log_2 n)/1000$ integers $1=q_1\le q_2\le \cdots q_{s-1}\le q_s=n$. Prove that
$$\min_\ell\left(\sum_{i=1}^\ell q_i\right)\left(\sum_{i=...
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
1
vote
1
answer
176
views
Maximization of $\ell^2$-norm
Consider for $r,c>0$ the set
$$X_{r,c}=\{x \in \ell^1(\mathbb{N}) \mid \|x\|_1=r,\, \forall i \in \mathbb{N}: |x_i|<c\}.$$
Then I can show that $\inf_{x \in X_{r,c}} \|x\|_2 = 0.$
But is it ...
- 11
1
vote
0
answers
48
views
How to derive a lower bound of a MinMax inequality?
Let $x_5,\cdots,x_n\in[0,\alpha]\cup[-\pi,\alpha-\pi]$ where $\alpha$ is a fixed angle $\in(0,\pi/2)$.
The goal
For a fixed $(A_{ij})_{1\leq i\leq 4,5\leq j\leq n}\in\{-1,+1\}$, verify whether it ...
- 405
0
votes
0
answers
36
views
How to prove the convergence of Gechberg-Saxton algorithm?
I just have a problem that Gerchberg-Saxton algortihm is no worse than the previous iteration
but not sure whether it is convergent.
