Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
613
questions
1
vote
1
answer
197
views
Calculus of variations for double sum with Lagrange multiplier
This cropped up in a research question I'm tackling.
I wish to solve the following optimization problem:
$$
\text{minimize}\ \sum_{i=1}^\infty f_i \sum_{j=1}^i \sqrt{f_j}
\quad\text{subject to}\ \sum_{...
0
votes
1
answer
123
views
What is the computational complexity of the calculation of $ \Psi(x) $?
What is the computational complexity of the calculation of $ \Psi(x) $ described below:
Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we ...
1
vote
2
answers
169
views
Does this non-negative function, with no stationary points, have only descent directions close to a constraint set?
Suppose $P: \mathbb{R}^n \rightarrow \mathbb{R}_{\ge 0} $ is a differentiable map, with $P(x) = 0 \ \forall x \in \mathcal{X}$ and $P(x) > 0 \ \forall x \in \mathcal{X}^c$. Further, suppose $P$ has ...
1
vote
1
answer
172
views
How to solve a system of nonlinear equation, with y known and x or its coefficients unknown? [closed]
While solving a complex problem I have ended up with this simplified problem:
There are eight straight lines in the plane. They are notated as follows:
\begin{gather}
\tag{1}
\label{1}
y=k_1 x+b_1\\
y=...
0
votes
1
answer
145
views
What to call a function that is negative on a set
Let $Y$ be a nonempty region in $\mathbb{R}^n$. I am designing an algorithm which given a point $x_0$ outside $Y$ in a finite number of steps lead to a point $x_n∈ Y$. The way I do it is that I have a ...
2
votes
0
answers
69
views
Monotone rearrangements of function, constrained optimization in $\mathcal{L}^p$
By $\mathcal{S}$ let us denote the set of such step functions $f:[0,1]\to [0,1]$ that additionally satisfy:
$$\forall_{ x>\frac{1}{2}} \ \ \lambda\Big(f=x\Big) \ = \ x\cdot \Big[\lambda\Big(f=x\Big)...
5
votes
1
answer
211
views
Minimizing the largest eigenvalue of matrix product
Let $A\in\mathbb{C}^{m\times n}$, $B\in\mathbb{C}^{n\times k}$, $C\in\mathbb{C}^{k\times m}$ be given complex matrices. The objective of the optimization problem is
\begin{equation}
\mathop {\arg \min ...
4
votes
3
answers
389
views
On some inequality (upper bound) on a function of two variables
There is a problem (of physical origin) which needs an analytical solution or a hint. Let us consider the following real-valued function of two variables
$y (t,a) = 4 \left(1 + \frac{t}{x(t,a)}\right)...
0
votes
0
answers
57
views
Numerically finding matrix approximation by lower-dimensional "pseudo-similar" matrix
Consider an $N\times N$ (real or complex) matrix $A$, and some $n<N$. Is there a good numerical algorithm that finds the set consisting of an $n\times n$ matrix $B$, an $n\times N$ matrix $I$, and ...
2
votes
0
answers
383
views
Global minimum of sum of a non-convex and convex function, where minima of the non-convex function can be found
I'm interested in finding $\arg\min_{x \in X} (f(x) + \lVert x\rVert_2^2)$ where $X$ is a $[0,1]^n$, $f$ is Lipschitz but non-convex and we already have a procedure to find some $x^* \in \arg\min_{x\...
1
vote
1
answer
262
views
Example of a differentiable function optimization where derivative free methods are used
While preparing a workshop on the derivative free methods, and fminsearch in MATLAB, I found an example function where fminsearch converges better and in less iterations than fmincon with calculated ...
0
votes
1
answer
285
views
Gradient-descent "type" Methods for non-convex and non-smooth functions
Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:
lower semi-...
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
votes
1
answer
92
views
Existence of continuous selection for metric projection
Let $(X,d)$ be a separable complete geodesic metric space and let $K$ be a compact (non-empty) subset of $X$. Without assuming things like linearity, the convexity of $K$, and locally convexity, ...
2
votes
1
answer
329
views
Normal cones and KKT conditions
I'm trying to understand a statement from the book "Perturbation Analysis of Optimization Problems", by Bonnans and Shapiro. Let me start by providing some context. In page 148, the authors ...
3
votes
1
answer
293
views
KKT conditions of problem with variational inequality constraint
I have an optimization problem with a variational inequality constraint:
$$
\begin{equation}
\begin{array}{ll}
\min_x & f(x) \\
\mathrm{s.t.} & g_i(x) \leq 0, \quad i=1,\ldots,m \\
& h_j(...
4
votes
1
answer
218
views
Nonlinear system of integral equations
I have encountered a system of nonlinear integral equations in my work. They take the form
$$\int_{0}^{1} \frac{1}{g(y)}e^{f(x)/g(y)}(x+f(x)/g(y)-f(x))dy=0$$
$$\int_{0}^{1}\frac{f(x)}{g(y)^2} e^{f(x)/...
2
votes
0
answers
64
views
Minimizing a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
5
votes
1
answer
316
views
On a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
1
vote
2
answers
188
views
Robust estimation of $Ax=b$
Problem setting :
$ \underset{x}{\text{min}} \|Ax-b\|$, where $A \in \mathcal{R}^{m \times n}, m\gg n $, full rank.
L1 loss is used for robust estimation using IRLS. The corresponding equation to ...
2
votes
0
answers
52
views
Which algorithm to optimize this problem?
I do need to find coefficients of a parametric model given observations, and I was wondering which algorithm I should use. The problem is as follows.
I have a set of values $\mathbf x_i = (x_{i,1},\...
2
votes
0
answers
47
views
A question about strong slopes (nonsmooth analysis)
Context. I'm reading the manuscrip "Nonlinear Error Bounds via a Change of Function" by Dominique Azé and Jean-Noël Corvellec (J Optim Theory Appl 2016), and I'm having a hard time ...
0
votes
0
answers
67
views
Convex optimization under asymmetric loss in infinite dimensional space
The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...
1
vote
0
answers
34
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 \...
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,...
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 ...
1
vote
0
answers
45
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 $...
1
vote
0
answers
101
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 ...
2
votes
0
answers
98
views
Sparse signal recovery (nonlinear case)
Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...
1
vote
1
answer
185
views
Metric / strong slope restriction of function on unit ball in $\mathbb R^m$
Diclaimer. I'm not sure this is the right venue for this question, but I'll give it a try
Definition [Strong / metric slope]. Given a complete metric space $(M,d)$ and a function $f:M \to (-\infty,+\...
5
votes
5
answers
615
views
Elementary inhomogeneous inequality for three non-negative reals
I need the following estimate for something I am working on, but I don't immediately see how to establish it.
For $x, y, z \in \mathbb{R}_{\ge 0}$, show that
$$2xyz + x^2 + y^2 + z^2 + 1 \ge 2(xy + yz ...
7
votes
1
answer
362
views
An elementary inequality for three complex numbers
The following problem arose in asymptotic analysis of difference equations.
Numerical maximization suggests that for all nonzero complex numbers $a,b,c$ we have
$$h\big(r(a,b,c),r(b,c,a),r(c,a,b)\big)...
0
votes
0
answers
35
views
Optimizing upper and lower bounds
Let $L_i:X\rightarrow [0,\infty)$ be continuous (objective) functions defined on a metric space $X$ and suppose that
$$
L_1(x)\leq L_2(x)\leq L_3(x)\qquad (\forall x \in X).
$$
Here, I imagine that $...
2
votes
1
answer
209
views
Using Nelder-Mead to solve system of polynomial equations
I am trying to solve a system of $9$ polynomial equations in $9$ unknowns over the non-negative reals.
Since the equations are quite large and I would like to use VBA, I prefer an algorithm that ...
0
votes
0
answers
52
views
An optimization problem about number series
Given $m>0$, we want to minimize
$$
\sum_{k=1}^r a_k \log b_k
$$
for arbitrary increasing number series $a_k\geq 1$ and $b_k\geq 1$ satisfies
$$
\sum_{k=1}^{\infty} \frac{1}{a_k}=1
$$
and $r$ ...
7
votes
2
answers
565
views
Determining if a quadratic form is non-negative if variables are non-negative
Let $f(x_1,\dots,x_n) = \sum_{1 \le i \le j \le n} c_{i,j}x_ix_j$ be a homogeneous quadratic form. Is there a quick-ish way to determine whether $f(x_1,\dots,x_n) \ge 0$ for all $x_1,\dots,x_n \ge 0$?
...
1
vote
1
answer
297
views
Dual problem with integrals
I am reading a paper where the author derives the following Lagrangian dual problem :
$\min_v \int_R \frac{1}{4} \frac{\beta^2}{v-2\|x\|}dx+v\;\;\;\text{s.t.}\;\;\;v\geq 2\|x\|\;\;\;\forall x \in R$
...
3
votes
0
answers
116
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+\...
0
votes
1
answer
148
views
Difference of two optimization problem's optimal value
Let we have two following optimization problems:
\begin{align}
\text{(P1)}\quad \alpha_1 = \max_{x_1,\ldots,x_M} &\quad \sum_{m=1}^{M}\log(1+f_m(x_1,\ldots,x_M))\\
\textrm{s.t.} &\quad \...
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\|...
2
votes
1
answer
128
views
Lower semi-continuity of length-dependent functional
Let $f:\mathbb{R}\rightarrow [0,\infty]$ be a lower semi-continuous function and define the functional
$$
\begin{aligned}
F_f:&\ell^1 \rightarrow [0,\infty]\\
(x_n)_{n=0}^{\infty} &\to \sum_{n=...
2
votes
0
answers
40
views
Numerical algorithms for geodesically convex optimization
I want to solve a minimization problem of the form
$\inf_{x \in M} f(x)$
where $M$ is a Hadamard manifold and $f$ is geodesically convex (but not differentiable). Since I know that in general a ...
0
votes
1
answer
182
views
Optimization problem involving matrix
I am struggling to solve an optimization problem of the following form:
$$\begin{array}{ll} \underset{A}{\text{maximize}} & \log \det (A) \\ \text{subject to} & a^T A^{-1} a \le b\end{array}$$
...
2
votes
0
answers
171
views
How to sweep the leaves efficiently?
A cleaner, denoted by $P$, aims to sweep $n\ge 1$ leaves that appear one by one in a courtyard modeled by a compact set $D\subset \mathbb R^2$. Denote by $x_0$ the initial position of $P$ and by $v>...
0
votes
0
answers
50
views
What transformation is required to find a unique solution of this problem instead of multiple solutions?
$$
\max\limits_{\mathbf{f},\ \|\mathbf f\|=1 } \log_2\left(\prod^K_{i=1} \ \frac{ \mathbf{f}^H {\mathbf E} (\mathbf{W}_i, \Theta, \tau_i) \mathbf{f}} { \mathbf{f}^H \mathbf{G}_i ( \mathbf{W}_i, \...
4
votes
1
answer
153
views
Is there a point in 6-dimensional space satisfying these polynomial inequalities?
I would like to know if there is a point $(a, b, p, q, x, y) \in [0,1]^6$ satisfying the following collection of inequalities.
$b \ge a$
$q \ge p$
$y \ge x$
$a \ge p \ge a^2$
$b \ge q \ge b^2$
$p \ge ...
3
votes
1
answer
393
views
Weird claims and conclusions in "Introduction to Shape Optimization"
I'm trying to understand the notions of Euler and Hadamard derivatives of shape functionals. All the lecture notes and papers on this topic that I've found seem to build up on the books Shapes and ...
4
votes
2
answers
209
views
If all points of a real function with positive values would be local minimum, can one say it is constant function?
During my studies I faced a function $f:\mathbb{R} \to \mathbb{R}^+ $ with the property: for all $x \in \mathbb{R} $ and all $y$ in open interval $(x-\frac{1}{f(x)} ,x+\frac{1}{f(x)}) $ we have $f(x) \...
2
votes
0
answers
45
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
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}$...