Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
615
questions
1
vote
0
answers
188
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
1
vote
0
answers
52
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
1
vote
0
answers
54
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
1
vote
0
answers
97
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{...
- 311
1
vote
2
answers
263
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
1
vote
0
answers
59
views
Minimizing square roots with the consecutive ones property
Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all ...
- 3,929
1
vote
0
answers
134
views
Factorization of argmax
We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$.
Question: What is ...
- 1,117
1
vote
1
answer
153
views
Does coercivity/supercoercivity conjugates?
According to Wikipedia, a function $f: \mathbb{R}^n \to \mathbb{R} \cup \{-\infty, +\infty\}$ is called coercive if,
$$f(x) \to +\infty \text{ as } \|x\| \to +\infty$$
and it is super-coercive if
$$\...
- 125
1
vote
0
answers
53
views
Nested, successive minimization solved by asympotic minimization?
I am curious about the general relation between nested, successive minimization (M1) and asymptotic minimization (M2) as defined in the following. What one wants is to implicitly minimize a sequence ...
- 390
1
vote
0
answers
65
views
Minimize smooth function $(x,y) \to f(x,y)$ subject to $x \perp y$
Let $V$ be a finite-dimensional real vector space (e.g space of $m \times n$ real matrices equiped with Hilbert-Schmidt inner product $(A,B) \to \mathrm{tr}(AB^\top)$, and let $f:V^2 \to \mathbb R$, $(...
- 6,726
1
vote
0
answers
33
views
Are such assumptions of functions similar to strong convexity reasonable in convex optimization?
For $\mu$-strongly convex function $f:\mathbb{R}^d\to\mathbb{R}$, the following property holds: for any given $x,y\in\mathbb{R}^d$, we have
$$
(\nabla f(x) - \nabla f(y))^\top(x-y) \ge \mu \|x-y\|^2.$$...
- 95
1
vote
0
answers
105
views
Taut string algorithm and TV-minimization equivalence
Given real numbers $y_i's$, consider the following convex optimization problem:
$$
\min_{x_i's} \sum_{i=1}^N(y_i-x_i)^2 + \lambda\sum_{i=1}^{N-1}|x_{i+1}-x_{i}|.
$$
The paper A Direct Algorithm for 1D ...
- 1,196
1
vote
0
answers
35
views
Maximizing the volume of the intersection of a fixed ball with a cube with varying width and location
Given a ball $B$ and a linear subspace $L$ in $\mathbb{R}^n$, what is the maximum value of
$\frac{vol(B \cap C)}{vol(C)}$
where $C$ is a cube of the form $x + [0, h]^n$ for $x \in L$ and $h \in \...
- 5,099
1
vote
0
answers
27
views
Using Regula-Falsi to determine the solution to a non-linear system [closed]
Apologies, for this isn't a field or subject I know much about.
Regula Falsi (I believe some may know this as "double false position" or something like this) can be used trivially, of course,...
- 111
1
vote
0
answers
46
views
Prove that a polygon is convex over a circle
The problem
Let $C_A$ (resp. $C_B$) a circle of center $A = (x_A,0)$ (resp. $B = (x_B,0)$) and radius $r_A$ (resp. $r_B$).
For $k = 0,1,2,3,4$, let $D_k$ some points on $C_A$ with $D_0 = (x_0,0)$
Let $...
- 131
1
vote
0
answers
102
views
Minimising kurtosis (non-convex). Can I use algebraic geometry or alternate methods to show uniqueness of a particular solution?
I consider a weighted sum of $n$ identically-distributed correlated random variables. The weights in the sum, $w_i$ for $i=1, 2,...,n$, satisfy $w_i>=0$ and $\sum_{i=1}^{n}w_i=1$. I am ...
- 173
1
vote
0
answers
46
views
Various definitions of coercivity
In this post one says that a functional $F:H\rightarrow [0,\infty]$ on an infinite-dimensional Hilbert space $H$ is (strongly) coercive if there exists a constant $k>0$ such that
$$
F(x)\geq k\|x\|...
- 4,969
1
vote
0
answers
145
views
Maximizing variance of bounded random variable through convex optimization
I am interested in maximizing the variance of a random variable $X$ supported on $[0,1]$. Formally,
$$\max_{P_X: X \in [0,1]} {\rm Var}(X),$$
where $P_X$ is a distribution of $X$. This question is ...
- 631
1
vote
0
answers
78
views
Can this problem be rephrased as optimization on a manifold?
I have question. I have a Riemmanian manifold $\mathcal{M}$, like an $n$-dimensional regular surface in $\mathbb{R}^n$. And I have a smooth scalar field defined on this manifold $f:\mathcal{M} \to \...
- 103
1
vote
0
answers
146
views
A real system of bilinear equations with $2n$ unknown and equations
I have the following system of $2n$ bilinear equations, for a square invertible matrix $A \in \mathbb{R}_{n \times n}$, and $2n$ unknowns organized in vectors $x,y \in \mathbb{R}^n$:
$$
diag(y) A x = ...
- 560
1
vote
0
answers
59
views
Maximum value of $\int (aF^2(x)g(x)+G^2(x)f(x))dx$ over all $f,g$ densities satisfying $\int F(x)g(x)dx=1/2$
I want to maximise $$I(f,g):=\int_{-\infty}^\infty (aF^2(x)g(x)+G^2(x)f(x))dx$$ where $a>0$ is a given constant, over all possible probability densities $f,g$ satisfying $$\int_{-\infty}^\infty F(x)...
- 299
1
vote
0
answers
82
views
Gradient descent in $U(n)^r$
I have a function $f:U(n)^r\rightarrow \mathbb{R}$ which I would like to minimize. Here, $U(n)$ is the set of unitary matrices, and $r$ should be considered to be much bigger than $n$. For instance, $...
- 111
1
vote
0
answers
28
views
Gradient descent to estimate the ground truth pdf
I have a function $I_d(x)$ which defined over a plane. I could simulate the values of this function at different points. I have a ground truth probability density vector $p({\bf x})=(p_1(x),...,p_d(x))...
- 113
1
vote
0
answers
78
views
Solve optimal control problem whose associated system is nonlinear
Solve the optimal control problem of the LQR kind
$$
\min_u \int_0^{+\infty} x_1^2+x_2^2+\gamma(u_1^2+u_2^2) \, dt \quad\text{such that}\quad \begin{cases}\dot x_1=\alpha(x_2-x_1)+u_1,& x_1(0)...
- 207
1
vote
0
answers
149
views
Minimax optimization of diagonal entries of function of matrix
Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...
- 311
1
vote
0
answers
113
views
Showing existence of a solution to an underdetermined system of equations with non-negativity constraints
Let $K$ be a positive integer, let $p\in (0,1)$, and let $\{W(k,i),W^B(k,i), \varphi_k(i)\}_{1\leq i\leq k\leq K}$ be variables.
I need to prove that there exists a solution to the following system ...
- 63
1
vote
0
answers
71
views
Reduce the asymptotic variance for a class of Metropolis-Hasting estimates
I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
- 161
1
vote
0
answers
230
views
Maximize a smooth integral functional by pointwise maximization of the integrand
Let $(E,\mathcal E,\lambda),(E',\mathcal E',\lambda')$ be measure spaces, $I$ be a finite nonempty set, $p,q_i$ be probability densities on $(E,\mathcal E,\lambda)$, $\varphi_i:E'\to E$ be bijective ...
- 161
1
vote
0
answers
79
views
Minimization of a smooth integral functional over a closed convex set
Let $(E,\mathcal E,\mu)$ be a probability space, $I$ be a finite nonempty set, $\gamma:(E\times I)^2\to[0,\infty)$ be measurable, $$F_1(g,w):=\sum_{i\in I}\int\mu({\rm d}x)w_i(x)g(x)\sum_{j\in I}\int\...
- 161
1
vote
0
answers
104
views
Show a Poincaré inequality for a Markov kernel and minimize the Poincaré constant
Let $\tilde\kappa$ denote the transition kernel of the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $\tilde Q$ and target distribution $\tilde\mu$ (see definitions ...
- 161
1
vote
0
answers
152
views
solving a non-linear Matrix equation
I am working on a problem of optimization of wireless sensor networks in order to achieve the optimal power allocation in the network. I find an equality matrix problem that can be written as ...
- 367
1
vote
0
answers
473
views
Variational derivative of Wasserstein distance using Benaumou-Brenier formulation
I learned from the gradient flow theory in Wasserstein space that an equation of gradient flow type
$$\partial_t \rho + \nabla \cdot (\rho \nabla \frac{\delta F}{\delta \rho})=0,$$
can be derived as ...
- 429
1
vote
0
answers
96
views
Minimize $\langle(1-\kappa)^{-1}f,f\rangle$ for a parameter-dependent integral operator $\kappa$
I've got a contractive self-adjoint linear integral operator $\kappa$ of the form $$(\kappa g)(x):=g(x)+\int\lambda({\rm d}y)k(x,y)(g(y)-g(x))\;\;\;\text{for }g\in L^2(\mu),$$ where $k$ depends on the ...
- 161
1
vote
0
answers
260
views
Computing the nearest hermitian positive semi-definite matrix
The real case of finding the nearest semi-definite matrix in terms of the Frobenius norm was solved by Higham in 1988.
But is there any work on computing the nearest
hermitian positive semi-...
- 43
1
vote
0
answers
44
views
Finding a distribution satisfying uncountably many constraints: a follow up in a more restrictive setting
Recently, I posted the question Finding a distribution satisfying uncountably many constraints. Any relevant references?. Bjørn Kjos-Hanssen quickly and astutely pointed out that without further ...
- 33
1
vote
0
answers
153
views
Gradient formula for Clarke's generalized gradient on a general Banach space
In Theorem 10.27 of the book Functional Analysis, Calculus of Variations and Optimal Control, there is the following gradient formula:
($\operatorname{co}$ deotes the convex hull).
Is there an ...
- 161
1
vote
0
answers
144
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 161
1
vote
0
answers
112
views
look for differentiable symmetric functions whose global minimizer has all distinct components
For symmetric functions, people ask Do symmetric problems have symmetric solutions?, e.g., [3] and [4].
The answer is no in general. However, solutions of symmetric problems often exhibit certain ...
- 848
1
vote
0
answers
187
views
Solution to a Strongly Convex Non-smooth Minimization Problem involving an L1 Norm
Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1\}^{n}, \alpha \in [0,1], \lambda \in \mathbb{R}$. I have an expression that looks as follows
$\frac{1}{2}\|Xw -y \|_{2}^2 + \...
- 11
1
vote
0
answers
655
views
Matrix trace minimization of quadratic and linear terms under orthogonal manifold constraints
How would one solve the following orthogonal manifold problem?
$$\begin{array}{ll} \text{maximize} & \mbox{tr}(X^\top A X - X^\top B)\\ \text{subject to} & X^\top X = I\end{array}$$
where $A ...
- 21
1
vote
0
answers
55
views
Sum of squared nearest-neighbor distances between points on the sides of a rectangle
For positive real numbers $a,b$, let $R$ denote the $a\times b$ rectangle $[0,a]\times[0,b]$. Let $A_1,\dots,A_4$ be points on the sides of $R$, one point on each side. For each $j=1,\dots,4$, let $...
- 117k
1
vote
0
answers
63
views
Bayesian parameter estimation
I am generally not that knowledgeable for math, so if my question is too broad or inaccurate, please let me know.
I am currently reading a paragraph of one paper (https://www.fil.ion.ucl.ac.uk/spm/...
1
vote
0
answers
64
views
Curvature of projection function onto a smooth curve
Suppose we have a smooth curve $C$ lying in $\mathbb{R}^2$, and let us consider the orthogonal projection function $P_C(x)$ onto the curve, described by
$$P_C(x) = argmin_{y \in C} \Vert x - y \Vert$$...
- 141
1
vote
0
answers
130
views
Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?
Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no.
At least could it be true in $2\times2$ ...
- 13.7k
1
vote
0
answers
101
views
How to solve such integer program problem?
Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...
- 1,942
1
vote
0
answers
246
views
Minimum Preserving Transformations [closed]
If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...
- 4,969
1
vote
2
answers
596
views
Maximizing a sum of Gaussians
Let $\mathbf{x}_1, \dots, \mathbf{x}_n \in \mathbb{R}^d$ be $n$ given vectors. Define the function
$$ \mathcal{K}(\mathbf{x},\mathbf{y}) := \alpha\exp\left(-\frac{\|\mathbf{x}-\mathbf{y}\|^2}{2\sigma^...
- 1,371
1
vote
0
answers
215
views
Distance between quadric surface and point or Intersection of sphere and quadric surface
I asked a similar question on math.stackexchange, but the answer wasn't quite ideal for my application. Apparently analytic solutions are surprisingly rare for general quadric distances.
Given a ...
- 11
1
vote
0
answers
45
views
Rank Optimization over semi-definite constrains
Let $X$ and $Y$ be finite dimensional Hilbert spaces $\mathbb{C}^n$ and $\mathbb{C}^m$, $L(X)$ and $L(Y)$ be the sets of linear operators of $X$ and $Y$, $\text{Herm}(X)$ and $\text{Herm}(Y)$ be the ...
- 1,493
1
vote
2
answers
106
views
Optimization of non-smooth convex function in a polytope
We know that accelerated proximal gradient descent method can be applied to solve the following convex programming problem:
$$\min{f(x)+g(x)}$$
where $f$ is smooth and convex, and $g$ is a non-smooth ...
- 13