Questions tagged [nonlinear-optimization]
Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.
598
questions
0
votes
0
answers
15
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 ...
- 759
0
votes
0
answers
40
views
Error bound for stohastic 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-...
- 759
1
vote
1
answer
80
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 ...
- 87
0
votes
1
answer
131
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:
$\...
- 11
0
votes
0
answers
26
views
Analytic solution for minimax optimization problem
In my personal studies/exploration I have come across the following problem:
$$\inf_{a \geq 0} \sup_{\substack{0 \leq z \leq 1\\t > 0}} z\sqrt{b(a^2
+ s^2)} - \dfrac{at}{2} -
\dfrac{az^2}{...
- 1
1
vote
0
answers
36
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
- 11
2
votes
1
answer
111
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 ...
- 43
2
votes
1
answer
86
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 ...
- 403
1
vote
1
answer
91
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 ...
- 27.9k
2
votes
0
answers
63
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}...
- 21
3
votes
1
answer
61
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=(\...
- 4,463
0
votes
0
answers
13
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 ...
- 101
1
vote
0
answers
25
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 ...
- 11
3
votes
1
answer
198
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=...
0
votes
0
answers
51
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
42
views
A dilemma in a lemma regarding Hexagonal Fuzzy approximation of parabolic fuzzy number
I was reading Nayagam & Murugan - Hexagonal fuzzy approximation of fuzzy numbers and its applications in MCDM paper regarding hexagonal fuzzy approximation. In that, the statement of Lemma 3.1 and ...
- 1,841
1
vote
1
answer
156
views
Does the value function of a quadratic program stay convex when adding constraints?
I am interested in the value function of a quadratic program of the form
$$
v(y)=\min_x \frac{1}{2} x^\top Q(y) x,
$$
subject to a linear equality constraint
$$
E(y)x=d(y),
$$
and a linear inequality ...
- 379
1
vote
0
answers
34
views
Computational comparison in solving two optimization problems
Can I get some inputs on whether the following two optimization problems are computationally the same, or one of the problems is easier to solve computationally than the other, such as, finding their ...
- 33
0
votes
0
answers
42
views
How to solve mckp (multiple-choice knapsack problem) problem with non-linear constraint
How to solve the below optimization problem? $P$ is a probability matrix, $0\le P_{ij}\le 1$. Are there any developed tools to solve this? Thanks a lot.
\begin{equation*}
\begin{aligned}
&\...
0
votes
0
answers
52
views
An optimization problem defined by optimal transportation
Let $\mu,\nu$ be two probability measures on $E:=\mathbb R^d$ and denote by $\gamma:=\mu\otimes \nu$ the product measure on $E\times E$. Define $\mathcal K$ to be the class of continuous functions $k:...
- 759
0
votes
0
answers
49
views
An integer optimization problem on the simplex
For $K \geq n$ and some $\sigma_i > 0$, I am looking for a solution to the following optimization problem:
\begin{equation}
\underset{\begin{smallmatrix} t_1, \cdots, t_n \in \mathbb{N}^{*} \\ \...
- 347
1
vote
0
answers
29
views
Minimizing a ratio related to scalar subset sums
Let $a = (a_1, a_2, \cdots, a_n)$ be non-zero real numbers. Let $[n] = \{1,2,\cdots,n\}$ be a set of indices. Define the maximum absolute subset sum of the array $a$ as:
$$\mathrm{MASS}(a) = \max_{T \...
- 11
4
votes
0
answers
110
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(...
- 677
1
vote
1
answer
70
views
Maximizing the ratio of multilinear polynomials
Consider two multilinear Polynomials $A(x_1,x_2,x_3,\dotsc,x_n)$ and $B(x_1,x_2,x_3,\dotsc,x_n)$ of $n > 2$ variables $x_i \in \mathbb{R}$ and their ratio
\begin{equation*}
F(x_1,x_2,x_3,\dotsc,...
- 13
1
vote
0
answers
133
views
Constrained trace optimization with relavance to optimal asset selection
Let $D$ and $Q$ be two real $m\times m$ diagonal matrices given
$$
D=\left(\begin{array}{cccc}
d_1 & 0 & \cdots & 0\\
0 & d_2 & \cdots & 0\\
\vdots & \vdots & \ddots &...
- 43
3
votes
1
answer
178
views
Interesting question about the Thomson problem for arbitrary number of electrons
This question is crossposted from here I believe this is a pretty hard question and so I decided to repost the question in the Math Overflow forum. If there is something wrong with doing this, I am ...
- 51
4
votes
1
answer
125
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}^...
- 131
0
votes
2
answers
122
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} {\...
- 21
3
votes
0
answers
79
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_{...
- 26.9k
1
vote
0
answers
156
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.5k
2
votes
1
answer
109
views
How many strict local minima can a quintic polynomial in two real variables have?
A quadratic or cubic polynomial (in two variables) can have at most one strict local minimum. A quartic polynomial can have up to five strict local minima [1]. So, how many strict local minima can a ...
- 301
9
votes
1
answer
584
views
How many saddle points can a quartic polynomial in two real variables have? All 9?
By Bézout's theorem a quartic polynomial $p(x,y)$ can have at most 9 isolated critical points. Can all of them be saddle points?
In case of a cubic polynomial there is a mechanical way to answer this ...
- 301
7
votes
1
answer
903
views
Can a cubic polynomial in two real variables have three saddle points?
Is there a cubic polynomial $c(x,y)$ with exactly 3 saddle point critical points?
In other words, can a cubic polynomial in two variables have three critical points, all of which are saddle points? ...
- 301
1
vote
0
answers
34
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 ...
- 190
1
vote
0
answers
51
views
Sum of absolute values of trigonometric polynomials
I am trying to tackle the following problem:
Let $A_{f},A_{g} \in \mathbb{R}^{3 \times 3}$ be symmetric matrices and let $f: [-\pi,\pi)^{2} \to \mathbb{R}$ and $g: [-\pi,\pi)^{2} \to \mathbb{R}$ ...
- 19
0
votes
1
answer
106
views
Seeking closed-form solution for vector equation
I'm working on a problem that involves vectors and scalar values, and I'm looking for a closed-form solution. I hope someone can help me with this or provide insights into how to approach it. Here's ...
- 111
2
votes
1
answer
161
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
2
votes
0
answers
79
views
A complex problem involving densities (likelihood functions) and optimization
Consider the following autoregressive process with normal errors:
\begin{equation}\label{7YlUV4i8nuO}\tag{I}
y_t = \phi y_{t-1}+ u_t, \quad u_t \overset{iid}{\sim} N(0,\sigma^2)
\end{equation}
We ...
- 161
1
vote
0
answers
89
views
Maximisation of a convex (quadratic) function
This post is a continuation of A variant of (discrete) optimal transport problem
For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $...
- 759
2
votes
1
answer
66
views
A variant of (discrete) optimal transport problem
Let $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$ and $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ be given and satisfy
$$\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j.$$
Define $\...
- 759
0
votes
0
answers
49
views
Upper-bound on energy of nonlinear boundary-value problem
The problem:
Consider the following boundary-value problem for the function $\rho : \mathbb{R}^{+} \to \mathbb{R}$ with boundary conditions $\lim_{x\to \infty}\rho(x) \to 1$ and $\lim_{x\to 0}\rho(x)...
- 105
0
votes
0
answers
29
views
optimization of mixed linear and infinity norm
I have the following optimization problem:
Given a complex sequence $H_i$, $1 \leq i\leq N$. Find a complex sequence $G_i$ that minimizes:
$$ \lambda\cdot\max_i { |H_i\cdot G_i - 1|^2 } + \sum_i |G_i|^...
- 101
1
vote
2
answers
111
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
- 175
2
votes
0
answers
93
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at Computational Science SE
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
...
- 21
0
votes
1
answer
93
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 ...
29
votes
1
answer
1k
views
Can a real quartic polynomial in two variables have more than 4 isolated local minima?
This question: "Can a real quartic polynomial in two variables have at most 4 isolated local minima?" came up in this post on Math SE but with no answer so far.
Finding examples of 4 ...
- 431
3
votes
1
answer
98
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
0
votes
0
answers
62
views
How to solve a system of polynomial equations which are mostly factored?
If I have a system of $k$ equations
$$
\begin{cases}
F_1(x) = 0,\\
\quad\vdots \\
F_k(x) = 0.
\end{cases}
$$
with
$$
F_i(x) = c_i + \prod_{j=1}^n f^i_j(x)\quad i=1,\ldots,k
$$ where
$f^i_j: \mathbb{R}...
- 101
4
votes
1
answer
196
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,283
1
vote
1
answer
109
views
Local maxima of the sum of Gaussian functions in *one dimension* are always strict local maxima - proof?
Motivated by this question asked earlier, I was wondering whether one can prove easily that the local maxima of the sum of Gaussians:
$$f_n(x):= \sum_{i=1}^{n}e^{-(x-x_i)^2}, \quad x_1 < x_2 < \...
- 1,283