All Questions
Tagged with nonlinear-programming or nonlinear-optimization
639 questions
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 163
1
vote
0
answers
58
views
Solving an equation involving exponential function (for optimization )
I have the equation
$$ c \tan \left(\theta\right)+\frac{a b A \exp \left(-b\left[\theta-a\right]\right)}{\left[1+a \exp \left(-b\left[\theta-a\right]\right)\right]^2}=0 $$
where $a,b,c$ and $A$ are ...
- 11
0
votes
1
answer
50
views
Find an optimizer for $g(x,y)$ if it exists
Consider $f:\mathbb{R}^{2}_{0} \to \mathbb{R}_{0}$ such that $f(x,y)$ is a continuous function and satisfies the following properties:
$f(x,y) = f(y,x)$
$f(tx,ty) = tf(x,y) \ \forall \ t > 0 $
$f(...
3
votes
1
answer
344
views
How to find the maximum of a sum of squares of sums?
Is there any better than a brute force method for finding the maximum
$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user494931
5
votes
3
answers
496
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 2,135
1
vote
3
answers
345
views
How to optimize for the best fit nonuniform-scale-rotation to a given 3×3 matrix?
Given a matrix $L\in \mathbb{R}^{3 \times 3}$, I'm looking for a method to find the closest (in a least squares sense) product of a non-uniform scaling matrix and a rotation matrix:
$$
\min_{s\in\...
- 723
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
1
vote
0
answers
143
views
Can I solve this quadratic program "fast"?
We are given a matrix $D \in \mathbb{Z}^{C \times C}$ of non-negative entries, an integer $k \geq 1$ and we need to maximize the quadratic form $x^T D x$ under some simple constraints. For all ...
- 85
1
vote
0
answers
97
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
3
votes
1
answer
330
views
Variant of Wahba's problem
Wahba's problem is the following:
$$\min_R \sum_{k=1}^K \|v_k - Rw_k\|^2$$
where $v_k$ and $w_k$ are arbitrary $3\times 1$ vectors, and $R$ is a rotation matrix (i.e., orthogonal with $\det(R)=1$).
A ...
2
votes
0
answers
64
views
Question about (stochastic parallel-gradient descent) SPGD and (simultaneous perturbation stochastic approximation) SPSA [closed]
I wonder if someone could shed some light on this. I'm curious if stochastic parallel-gradient descent and simultaneous perturbation stochastic approximation refer to the same optimization techniques.
- 21
2
votes
0
answers
78
views
The fastest way to sample points on an implicit manifold, or projecting points on a manifold
Given a compact manifold $M$ in $R^n$, $M = f(x)$, f(x) is infinitely differentiable. $x$ $\in$ $R^n$, I want to find a bunch of samples on the manifold.
Currently, I'm setting up an SQP optimization ...
- 21
1
vote
0
answers
41
views
Fitting a non-periodic sum of periodic time series
The problems is as follows: you have $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ and you want to fit the following equation to the data points:
$$y=\theta_1\cos(\theta_2 x+\theta_3) + \theta_4\cos(\theta_5 ...
- 3,098
1
vote
0
answers
78
views
Minima of a cdf of multivariate normal distribution with respect to a parameter
Let $\mathrm{X}\sim\mathcal{N}_{3}(\boldsymbol{\mu},\mathrm{\Sigma})$ where
\begin{equation}
\boldsymbol{\mu} = n[(\mu_1-\mu_2)\sqrt{\xi_1\xi_2/(\xi_1+\xi_2)}, (\mu_1-\mu_3)\sqrt{\xi_1\xi_3/(\xi_1+\...
- 11
0
votes
0
answers
75
views
Maximize entropy under Kulback-Leibler divergence
I posed this question in math.stackexchange.com, but have not received any answer. I would like to try my luck here.
In this question, it is to solve
\begin{align}
\max_p &-\int dy\,p(y)\ln p(y) \\...
- 2,239
1
vote
0
answers
89
views
Variational problem with constraint
Let $D\subseteq [0,2\pi]\times [0,2\pi]$ and ${D}^\complement$ be the complementary region, i.e.
$D \cup {D}^\complement = [0,2\pi]\times [0,2\pi]$ and
$D\cap {D}^\complement = \emptyset$.
I would ...
1
vote
0
answers
202
views
Matrix relative condition number
I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.
Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
- 11
0
votes
0
answers
156
views
Optimal solution of complex optimization problem
Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
- 287
0
votes
1
answer
65
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
1
vote
1
answer
50
views
Point of tangency is an optimal point for a monotone, quasi-concave function
Given $U : \mathbb{R^2} \to \mathbb{R}$ is monotone and quasi-concave, consider the following problem :
$$\max_{(x,y) \ \in \ \mathbb{R}^2}[U(x,y)] \text{ subject to } p_1 x + p_2 y \leq M ; \ (p_1, ...
4
votes
1
answer
163
views
Gap to fill in the Aubin–Ekeland proof of the mountain-pass theorem
Working through the proof of the mountain-pass theorem given in Applied Nonlinear Analysis by Aubin & Ekeland, at what seems to be a critical point of the proof (the top of page 274) they refer to ...
- 193
3
votes
0
answers
108
views
Are square configurations the only critical points of the energy on the circle?
$\newcommand{\S}{\mathbb{S}^1}$
$\newcommand{\la}{\lambda}$Let$$M=\{(x_1,x_2,x_3,x_4) \in (\S)^4\,\, |\,\, \text{ all the } x_i \, \text{ are distinct}\} $$
Define $E:M \to \mathbb{R}$ by
$$E(x_1,x_2,...
- 6,741
1
vote
0
answers
53
views
Unique solution to nonlinear optimization through gradient descent
I am trying to estimate the path of a random walk described by the following SSM
$$
\begin{align}
x_{t+1} &= x_{t} + q_{t+1} \newline
y_{t+1} &= h(x_{t+1}) + r_{t+1}
\end{align}
$...
- 11
2
votes
0
answers
44
views
Convergent algorithm for minimizing nonconvex smooth function
Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
- 6,853
4
votes
2
answers
272
views
The mower's challenge
Weeds have taken over the paths (two squares). If mowed, they don't grow back, but unmowed weeds spread at speed $1$ along the road. What's the minimum speed of the mower to get rid of all the weeds? ...
- 2,619
1
vote
2
answers
270
views
Can we substitute this KKT condition into this optimization problem to reformulate the optimization problem?
Suppose I have the following optimization problem
$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$
It is already known that the target function $f$ is continuous and ...
- 73
0
votes
1
answer
191
views
Calculating derivatives of arbitrary-order at an operator's root
Consider roots $f = 0$ of a nicely-behaved real function $f(x, t)$ of two (real) variables.
Namely, points $(x, t)$ on which $f$ vanishes, $f(x, t) = 0$.
Suppose that $x$ can be written as function of ...
- 583
0
votes
0
answers
77
views
Get a specific number of points from a density distribution area to minimize the average distances
Assuming that an area $A$ on the plane has a known density distribution function $\rho (x, y)\geqslant 0$, now the goal is to obtain $n$ points $p_1, p_2, ..., p_n$ on the area so that $\iint_{}^{} \...
- 143
1
vote
0
answers
56
views
Minimising risk in dynamical systems
I have been reading the paper of Goerner and Ulancowicz - "Quantifying economic sustainability" in which it is suggested that there is a tradeoff between sustainability and efficiency. ...
user478214
3
votes
1
answer
217
views
Obtaining the "best possible" inequality by tuning hyper-parameters
I encountered the following problem in one of my research projects which can be encapsulated as follows. Let's say we have a set $\mathcal{C}$ of functions $f$ defined from $\mathbb R_+$ to $\mathbb R$...
- 730
2
votes
2
answers
173
views
Analytic solution of low-dimensional Riccati equation
Consider the nonlinear map $F_i:\mathbb R^2 \to \mathbb R$
$F_i(x):=\varepsilon^2\langle x, A_i x\rangle +\varepsilon\langle b_i,x \rangle + x_i,$
where $A_i$ is some matrix and $b_i$ some vector
Can ...
- 192
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
0
votes
1
answer
100
views
Formulating a problem as a mixed-integer conic program
I have the following integer optimisation problem, and I wonder whether it can be reformulated as a conic program that can be solved with, e.g., Mosek. Suppose the $n$-dimensional vectors $a, b$ and $...
- 13
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
4
votes
1
answer
336
views
Which set of functions admits the existence of the minimizer?
Let $a,b \in \mathbb R$ and consider the functional $J$ on $X$:
$$J[u] = \int_0^1 \left( (u'(x))^2 -a)^2 + b \ln (1+ u^2(x))\right) dx$$
Providing reasons specify if the $\inf J$ over $X$ is attained ...
- 159
1
vote
2
answers
278
views
Optimization of a integral function
I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function
\...
- 211
2
votes
1
answer
148
views
The regularity theorem, a non-regular minimizer problem
During my self study to the calculus of variations I come across this problem. Because of my search, I know what I wanted to do but I need some help to do them.
The function $f:[-1,1] \times \mathbb R ...
- 159
0
votes
0
answers
222
views
Convergence of ODE solutions almost everywhere to a stable equilibrium point
Theorem: Suppose ${\bf g} :\mathbb{R}^n \mapsto \mathbb{R}^n$ is continuously differentiable, there exists a set $\mathcal{A} \subset \mathbb{R}^n$ such that $\bf g$ is uniformly Lipschitz on $\...
- 1
5
votes
2
answers
248
views
Integrals can sometimes be computed through their saddle points. Are there examples of converse, when saddle points are found via integrals?
Under some reasonable assumptions integrals with large exponents can often be computed via saddle point approximations, e.g.
$$\int e^{-\lambda f(x)}\approx e^{-\lambda f(x_0)},\qquad \lambda\to\infty$...
- 319
3
votes
1
answer
322
views
Special version of Tonelli’s theorem
I am trying to prove this theorem. I have not found anything similar to it on the internet.
Special version of Tonelli’s theorem
Assume that the functions $f(x,u): [a,b] \times \mathbb{R} \to \mathbb{...
- 159
1
vote
1
answer
190
views
Proof of extended version of non-random "almost supermartingale"
In this question, a non-random version of "almost supermartingale" theorem is proved.
Here, I would like to extend/apply the non-random version to the slightly different situation. I wonder ...
- 45
2
votes
1
answer
111
views
Why is the Ekeland variational principle called a principle? [closed]
Why is the Ekeland variational theorem called the Ekeland variational principle?
I think (or maybe I studied somewhere) this is because of its equivalency with the Takahashi theorem, the Caristi ...
- 179
1
vote
1
answer
271
views
Can we invoke "almost supermartingale" Theorem for deterministic sequences?
Perhaps stupid question.
Question: Can "almost supermartingale" theorem be equally applicable to prove the convergence of some algorithms solving non-random optimization problems?
Attempt ...
- 45
2
votes
1
answer
304
views
On the Lipschitz continuity of $x \mapsto \arg\min_{c \in C}d(x,c)$ w.r.t Hausdorff distance
Let $C$ be a (nonempty) compact subset of euclidean $\mathbb R^n$, and consider the set-valued map $p_C:\mathbb R^n \to 2^C$ defined by
$$
p_C(x) = \{c \in C \mid \|x-c\| = \mbox{dist}(x,C)\},
$$
...
- 6,853
3
votes
0
answers
91
views
What is the name for this type of optimization problem?
As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...
- 141
4
votes
5
answers
2k
views
Reference request: importance of Lipschitz continuity
I see that Lipschitz continuity is a common assumption used in optimisation, statistics, machine learning, etc.
Could you point me in the direction of some literature that discusses why Lipschitz ...
- 161
0
votes
0
answers
109
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
0
votes
1
answer
143
views
Transformation of an unconstrained binary quadratic optimization problem into a constrained binary linear programming problem
I know that a constrained linear optimization problem can be transformed into an unconstrained binary quadratic optimization problem (UBQP). Does anyone know if the inverse result is solved in the ...
- 61
3
votes
1
answer
227
views
Relaxations for the spectral norm maximization problem
Optimizing the spectral norm of some positive semidefinite matrix $A(x) \in S^{n}$, w.r.t. a list of variables $x \in \mathbb{R}^d$ and semidefinite constraints is, in general, a nonconvex problem (...
- 33
0
votes
0
answers
92
views
Optimization problem where the objective function returns a function instead of a real number
As we all know, a classic optimization problem can be represented in the following way:
Given: a function $f: A \rightarrow \mathbb{R}$ from some set $A$ to the real numbers
Sought: an element $x_0 ∈ ...
- 141