Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
287 questions with no upvoted or accepted answers
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
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
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
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
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,155
5
votes
0
answers
199
views
measure of an image under an argmax function
I am trying to find any techniques to analyze the measure of an image of a set under an argmax function.
For example, let $\Omega\subset\mathbb{R}^n$ be compact and $\phi:\Omega\to\mathbb{R}$ be ...
5
votes
0
answers
404
views
Find subset of collection of sets whose intersection has minimum average value
Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...
- 300
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
4
votes
0
answers
121
views
$f(n) = \frac{n^2 + n + 4}{2}$, $g(f(n)) = f(g(n))$ such that $g(n)$ is an integer
Let $n$ be a strict positive integer and let's define an integer sequence $f(n)$ :
$$f(n) = \frac{n^2 + n + 4}{2}$$
so
$$
\begin{split}
f (\Bbb N)& \triangleq {3,5,8,12,17,23,30,38,47,\ldots}\\
f(...
- 763
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
4
votes
0
answers
146
views
An inequality for three iid random variables with a log-concave density
It was previously shown that
$$H\ge cG,\tag{1}$$
where $c:=1/14334$,
$$G:=E|X-Y|,\quad H:=E|X-Y|-\tfrac12\,E|X+Y-2Z|,$$
and $X,Y,Z$ are independent random variables with the same log-concave density.
...
- 128k
4
votes
0
answers
287
views
A conjecture about the barycenter of a polytope
Could someone help me with the following conjecture? Thanks a lot!
Suppose I have a polytope $\Delta$ in $\mathbb R^n (n\geq 2)$ with coordinates $(x_1,x_2,\cdots,x_n)$ defined by linear ...
- 1,121
4
votes
0
answers
275
views
Computing Bohr Radii
The Bohr radius $R$ for $\mathcal{H}(\mathbb{D})$ is defined as the radius $$R = \sup\limits_{0<r<1} \Bigl\{ r\ \Big|\sum\limits_{k=0}^{\infty}|a_k|r^k \leq |f|_\mathbb{D}, \text{ for all }f(z)=\...
- 3,209
4
votes
0
answers
228
views
Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables
Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest:
$1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed;
$...
- 359
4
votes
0
answers
234
views
Optimisation over $SO(3)$: is it safe to use a global parametrisation?
I am a functional analyst by training, but I am doing some numerical experiments which require me to minimise continuous functions $f:SO(3)\longrightarrow [0,+\infty)$ using a computer (I know that ...
- 778
4
votes
0
answers
241
views
Stochastic subgradient descent almost sure convergence
I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
- 141
4
votes
0
answers
707
views
What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?
I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well.
I am reading a paper [1] where they solve the following non-...
- 215
4
votes
0
answers
248
views
Comparison of Constrained Optimization Methods
I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...
4
votes
0
answers
405
views
maximize non-convex composite function
I want to maximize a composite function over a convex set
\begin{equation}
\begin{aligned}
& \underset{\mathbf{p}}{\text{maximize}}
& & f(\mathbf{p})-g(\mathbf{p})\\
& \text{subject to}...
- 61
4
votes
0
answers
233
views
Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same
I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e.,...
- 1,517
4
votes
0
answers
213
views
Optimization problem involving Multivariate Normal
I use $\phi(t)$ to describe the standard normal distribution density and $\Phi(t)$ as the normal distribution CDF and would like to prove that for all
$n\geq3$, the function:
$$h(\mu_{1},\ldots,\...
- 41
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,389
3
votes
0
answers
83
views
How many local maxima can $(x_1,\dots,x_r)\mapsto\|x_1A_1+\dots+x_rA_r\|_\infty/\|(x_1,\dots,x_r)\|_2$ have for Hermitian $A_1,\dots,A_r$?
Let $K\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$. Suppose that $A_1,\dots,A_r\in M_n(K)$ are all Hermitian.
Define a function $f_{A_1,\dots,A_r}:\mathbb{RP}^{n-1}\rightarrow[0,\infty)$ by setting
$$f_{...
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
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
3
votes
0
answers
72
views
Analytical solution of 2nd order nonlinear ODE ($y''+(a+by^2)y'+cy = 0$)
I encountered the following ode in the attempt to solve the problem of nonlinear van der pol equation. I have tried for a long time to give it a solution but failed.
$y''+(a+by^2)y'+cy = 0$
where $a$, ...
- 31
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 287
3
votes
0
answers
68
views
Convergence of iteration of a convex program
Let $\mathbf{V} \in \mathbb{R}_{+}^{n \times m}, \ \ \mathbf{E} \in \mathbb{R}_{+}^{n \times m}$, with $\mathbf{V} \mathbf{1}_{m} = \mathbf{1}_{n}$ and $\mathbf{E}^{T} \mathbf{1}_{n} = \mathbf{1}_{m}$...
- 53
3
votes
0
answers
240
views
Optimization with parametric constraints: solution maps
For constrained optimization problems
$$ \begin{array}{ll} \min\limits_{x \in \mathbb R^n} & f(p, x) \\
\text{s.t.} & x \in C \end{array} $$
where $p \in \mathbb R$ is a parameter, we can ...
- 791
3
votes
0
answers
255
views
How can we solve this kind of saddle point problem?
I'm trying to solve a saddle point problem of the following form: Let
$(E,\mathcal E,\lambda)$ be a measure space;
$p$ be a probability density on $(E,\mathcal E,\lambda)$ and $\mu:=p\lambda$
$W$ be ...
- 167
3
votes
0
answers
202
views
Maximize an $L^p$-functional subject to a set of constraints
Let
$(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces
$f\in L^2(\lambda)$
$I$ be a finite nonempty set
$\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
- 167
3
votes
3
answers
550
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 ...
- 2,246
3
votes
0
answers
106
views
Dependency of the Wasserstein distance on the parameter: a differential perspective
Let $\mu(dx)=\sum_{i=1}^np_i\delta_{x_i}(dx)$ and $\nu(dy)=\rho(y)dy$ be two probability measures on $\mathbb R^d$. Consider the $2-$Wasserstein distance below:
$$W_2(\mu,\nu)^2 \quad := \quad \inf_{\...
- 345
3
votes
0
answers
121
views
Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution
I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$
p^* = \...
- 283
3
votes
0
answers
645
views
Can a quadratic matrix inequality constraint be convex?
I have an optimization problem with a semi-definiteness constraint:
$$
N \preceq 0
$$
where the entries $N^{AB}$ of the matrix $N$ are defined through
$$
N^{AB} = \sum_{i,j} x^i M_{ij}^{AB} x^j
$$
The ...
- 131
3
votes
0
answers
105
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
- 13.9k
3
votes
0
answers
239
views
Constrained optimization with a Proportional-Integral-Derivative (PID) controller
My engineering colleagues have devised an interesting approach to equality-constrained optimization. I.e. they wish to solve the problem $\min_x f(x)$ subject to the constraint $g(x) = 0$ where $f, g ...
- 163
3
votes
0
answers
148
views
The complexity of an optimization problem involving sum of binomial coefficients
I'm just new to this community. So please forgive me if the question is not properly asked.
I would like to get the natural number e such that the following function can be minimized:
$f(e)=\frac{b}{...
- 31
3
votes
0
answers
203
views
Can the following system of equations be solved analytically/in a closed form?
From a constrained non-linear maximization problem I obtained the following system of equations:
$a_1=\frac{1+a_3-\sqrt{a_2a_3}\sqrt{v_1}}{1+\sqrt{\frac{a_3}{a_2}}\sqrt{v_1}}$
$a_2=\frac{2-a_3-\sqrt{...
- 41
3
votes
0
answers
962
views
Minimize L-infinity norm with restrictions
I need to minimize the following L-infinity norm with respective to $\tau$. L-infinity norm of a matrix $A$ is defined as $\|A\| = max_{i,j}|a_{i,j}|$.
$$
min_{\tau} \| I -S(S+\tau)^{-1}\|
$$
$$
\...
- 31
3
votes
0
answers
214
views
existence of optimal control
I'm looking for an existential result in optimal control for the following class of problems:
Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times \...
- 251
3
votes
0
answers
104
views
Sequence transformations that are entropy invariant
Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Define entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$
by $$H(\mathcal{A},m)=-\...
- 13.9k
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
2
votes
0
answers
93
views
Curve fitting with "rough" loss functions
Many real-valued classification and regression problems can be framed as minimization in the following way.
Setup:
Let $\Theta \in \mathbb{R}^p$ be the parameter space that we are searching over.
For ...
- 200
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