Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
613
questions
1
vote
0
answers
24
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}$ ...
2
votes
1
answer
291
views
Is it possible to find an upper bound and a lower bound for $(f(\xi)-f(\tilde{\xi}))^T(\frac{\partial f}{\partial \xi}(\bar{\xi}))(\xi-\tilde{\xi})$?
For a system engineering problem I have to solve the problem below, but since I am not a mathematician, I am not sure if I have enough knowledge to solve it.
Problem definition: Let $f(\xi) \in \...
1
vote
1
answer
274
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 ...
1
vote
1
answer
112
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 ...
1
vote
1
answer
119
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} \...
0
votes
1
answer
66
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$ ...
2
votes
2
answers
287
views
Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$
Let $\Omega\subset \mathbb R^d$ be compact, $\rho$ be a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ be weights satisfying $\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$. We consider the ...
4
votes
1
answer
239
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
vote
0
answers
57
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,...
0
votes
0
answers
22
views
How to control the angles of Kuramoto model by controlling its order parameter?
Consider Homogenous Kuramoto model in this paper. In theorem 3.1, the author derive condition on $A$ such that all second-order critical points of $E(\theta)$ are in two opposite quadrants, by saying ...
1
vote
0
answers
44
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 ...
0
votes
0
answers
30
views
Efficient algorithms to find the global minimum of a non-convex quadratically-constrained quadratic program
I am working on a problem involving a non-convex quadratically-constrained quadratic program and am seeking efficient algorithms to find its global minimum. The problem is structured as follows:
Fix ...
2
votes
1
answer
347
views
A "nice" (but non-definite) quadratic programme
For integers $n\geq k>0$, let $f$ be the following quadratic form:
$$f(x_1,\ldots,x_n)=\sum_{i=1}^n\sum_{j=0}^{k-1}x_ix_{i+j\bmod n}.$$
Is it true that the minimum of $f$ over the unit simplex is ...
1
vote
1
answer
85
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(...
2
votes
1
answer
290
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\...
0
votes
0
answers
35
views
Seeking help with a matrix optimization problem involving matrix exponentiation
I'm working on an optimization problem where I need to find matrices $P$, $Q$, and $C$ that minimize the norm of the difference between a given matrix $A$ and another matrix defined as $e^{P(Q + Q^T - ...
0
votes
0
answers
145
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 ;...
3
votes
3
answers
453
views
Looking for a very particular kind of non-convex functions
I want some examples (hopefully parametric families!) of non-convex functions which satisfy the following properties simultaneously,
It should be at least twice differentiable.
It should have a ...
0
votes
1
answer
71
views
Optimization: Determine the categorical pmf that maximizes the objective function
Let $T$ denote a $J$-component categorical random variable with pmf
$$
\mathsf P(T=t_j)=w_j,\quad j=1,2,\dots,J,
$$
where $t_j\in[0,t_\max]$, $t_\max>0$.
I came across a problem that seeks to ...
4
votes
1
answer
153
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 ...
0
votes
1
answer
474
views
How do I get an analytical solution to this nonlinear equation?
I posted this question over on Math Stack Exchange (link), but have not received a response. I'm wondering if it's too complicated for that audience, so I'm posting it here in the hopes that someone ...
0
votes
1
answer
102
views
An optimization problem with variables on the exponential of a complex number
$$\min_t \quad\operatorname{Re} \sum\limits_{i = 1}^N {\left( {{e^{ - j2\pi {f_i}t}}{r_i}} \right)}, $$where $\operatorname{Re}$ refers to get the real part of a complex number, $\{f_i\}$ is an ...
0
votes
0
answers
90
views
Primal optimal attained implies dual optimal attained
Given some optimization problem
$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$
we can find the dual problem
$$\max_{\lambda\in\mathbb{R}^m} g(...
3
votes
1
answer
156
views
Numerical scheme for convex optimization
Given $(e_n)_{-N\le n\le N}\in\mathbb R^{2N+1}$ and $-1<x<1$, solve
\begin{eqnarray}
&&\max_{(q_n)_{-N\le n\le N}\in\mathbb R^{2N+1}_+}~ \sum_{n=-N}^N (e_n-\log(q_n))q_n \\
\mbox{s.t.} &...
0
votes
0
answers
25
views
Which penalization works for this optimisation problem?
Let $m,n$ be given integers. Set $K:=[0,1]^{mn}$ and define the function $L:K\times\mathbb R_+^m\times\mathbb R_+^n\to\mathbb R$ as follows : for $z=(z_{i,j})\in K$, $a=(a_i)\in\mathbb R_+^m$, $b=(...
2
votes
1
answer
149
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
0
votes
2
answers
277
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} {\...
0
votes
1
answer
114
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
4
votes
2
answers
626
views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
0
votes
0
answers
70
views
Error bound for stochastic gradient descent method
To solve an optimization problem $\min_x G(x)$ using standard stochastic gradient descent method, we let $x_0$ be the initial point and $x_k$ be the $k$-th point such that
\begin{equation}
x_k = x_{k-...
4
votes
1
answer
210
views
Equivalence of bounded gradient flow solutions and uniformly bounded gradient descent trajectories for definable functions
I am reading paper [1] by C. Josz regarding the global convergence of the gradient method. The main result is the following:
$\textbf{Theorem}$: For a definable differentiable function $f : \mathbb{R}^...
1
vote
1
answer
160
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 ...
2
votes
2
answers
73
views
Reference for article that introduces and motivates different notions of subdifferentials
I saw a tutorial/expository journal article a while ago that focused on introducing intuitively different notions of subdifferentials appropriate for general nonlinear optimization. I forgot the ...
4
votes
1
answer
789
views
Lagrange-Newton minimization and initial value for the Lagrange multipliers
Short version. How to choose the initial values for the Lagrange multipliers in the Lagrange-Newton
equality-constraint minimization method?
Introduction. The problem to solve is
\begin{equation}
\...
0
votes
0
answers
33
views
Solving optimization problem restricted to non-convex subset
I have two continuous random variables that have pdfs with respect to the Lebesgue measure $p_{-1}(x), p_1(x)$.
Let $m(x) := \frac{p_{-1}(x)+p_1(x)}{2}$ be a mixture of these two distributions.
Let $B(...
1
vote
0
answers
78
views
Positive semidefinite maximum principle
Let $K\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$. Let $\mu$ be a Borel probability measure on $M_n(K)$ supported on a compact set $C$ of positive semidefinite matrices with $\mathbf{0}\not\in C$. ...
0
votes
0
answers
26
views
Convergence bound for zero-order optimization method
I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method.
To solve an nonsmooth optimization problem $min_x G(x)$ where $G$ is only a ...
1
vote
1
answer
81
views
optimization over moving domains
Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem:
$$L(a)=\inf_{b\in B_a}\ell(b),$$
where $\ell(b)$ is a infinite-times ...
0
votes
1
answer
139
views
nonlinear equation problem
Can you please help me solve the following nonlinear equation to determine the value of the vector $z$ :
$$
\boldsymbol{a}=\boldsymbol{z}^{2} \odot \boldsymbol{K}*\boldsymbol{z}^{-1}$$
Where:
$\...
-1
votes
1
answer
693
views
How can I deploy a CG-Steihaug algorithm for trust region sub-problem solving?
I'm studying various optimization methods and on this occasion, I'm trying to tackle the Trust Region Problem by solving the sub-region problem with the Steihaug-CG algorithm in Python. I'm using the ...
1
vote
0
answers
53
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
2
votes
1
answer
141
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
7
votes
3
answers
678
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 ...
2
votes
1
answer
136
views
Argmax of a function of $n$ variables under linear constraint
(I start by saying that the tags are probably not accurate but I didn't know what to put, so if someone knows what I could tag this question with, let me know in the comments and I'll provide to edit ...
1
vote
1
answer
125
views
Maximal entropy distribution on three variables knowing its marginals on any two
Observation 0: Given a finite set $X$, the probability distribution on $X$ with highest entropy is the uniform one. This is well known.
Observation 1: Given two finite sets $X,Y$ and two probability ...
3
votes
1
answer
73
views
Detecting linear operator from actions of powers on subspace
Say I have a sequence of linear operators $A_1,...,A_n$ on a (real) vector space $V_1$. I suspect that there's a second vector space $V_2$, and an operator $A$ on $V_1\oplus V_2$, such that $A_i=(\...
0
votes
0
answers
20
views
Numerical solution to partially-free boundary optimization problem
Background
First of all, I'm a PhD physicist working in numerical analysis, so I apologize for possible easy-to-spot mistakes (they're most likely not that easy for me).
The problem I'm trying to ...
1
vote
0
answers
30
views
Weighted Least squares with Multiple Unknowns and Iterations
I am currently working on a problem involving the minimization of the $\chi^2$ deviation between a model matrix ($C_\text{model}$) and a measured matrix ($C_\text{measured}$). by finding the best-fit ...
3
votes
1
answer
222
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=...
4
votes
3
answers
348
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):=\...