All Questions
Tagged with nonlinear-programming or nonlinear-optimization
640 questions
2
votes
2
answers
89
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 ...
- 922
1
vote
1
answer
187
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} \...
- 135
1
vote
0
answers
91
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$. ...
1
vote
1
answer
84
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
140
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
1
vote
0
answers
70
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
174
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
209
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 ...
- 697
2
votes
1
answer
163
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 ...
- 32.5k
2
votes
1
answer
274
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
83
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,593
1
vote
0
answers
32
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
233
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
55
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
1
vote
1
answer
209
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
41
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 ...
- 69
0
votes
0
answers
88
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}
&\...
1
vote
0
answers
36
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
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(...
- 769
1
vote
1
answer
100
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
152
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
249
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
5
votes
1
answer
265
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}^...
- 171
0
votes
2
answers
531
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
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_{...
1
vote
0
answers
161
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.9k
2
votes
1
answer
196
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 ...
- 291
8
votes
1
answer
690
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 ...
- 291
7
votes
1
answer
1k
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? ...
- 291
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
1
vote
0
answers
67
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
147
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
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
2
votes
0
answers
87
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 ...
- 13
1
vote
0
answers
113
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 $...
- 1,389
2
votes
1
answer
100
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 $\...
- 1,389
0
votes
0
answers
53
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)...
- 147
0
votes
0
answers
57
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
121
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
178
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
139
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
189
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
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,465
1
vote
1
answer
132
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,465
1
vote
1
answer
210
views
Solution of nonlinear differential equation $g = c_1 f^2 + c_2 (f')^2$ for function $f$
I would like to find an analytic solution (if possible) of the differential equation:
$g = c_1 f^2 + c_2 (f')^2$
Where $c_1$ and $c_2$ are constants, $g$ is a known function of $x$, $f$ is another ...
- 83
3
votes
1
answer
133
views
Is the smallest root of this quartic always the closest point on the Hyperbola? [closed]
Let $a>b>0$.
Suppose we want to minimize
$$
f(x)=(x-a)^2+(1/x-b)^2,
$$
over $x>0$.
Equating $f'(x)=0$ leads to the quartic equation
$$
g(x)=x^4-ax^3+bx-1=0. \tag{1}
$$
Question:
Is the ...
- 6,741
1
vote
1
answer
130
views
Analytic expression for the min value of $g(t):= \sqrt{(t-1)^2 + a^2}+ b|t|$ subject to $|t-1| \le c$
Disclaimer. Not sure this is MO-level but would really appreciate some help with this. Thanks in advance. Moved from SE.
Let $a,b,c \ge 0$, and define a function $g:\mathbb R \to \mathbb R$ by $g(t) :=...
- 6,853
-2
votes
1
answer
183
views
Property of positive semi-definite
Let $A$ is a positive semi-definite matrix like this:
$$ A = \begin{bmatrix}
1 & \alpha_{1,2} & \alpha_{1,3} & \alpha_{1,4}\\
\alpha_{1,2} & 1 & \alpha_{2,3} & \alpha_{2,4}\\
\...
- 25
1
vote
0
answers
32
views
Convergent gradient-type scheme for solving smooth nonconvex constrained optimization problem
Let $x_1,\ldots,x_n \in \mathbb R^d$ and $y_1,\ldots,y_n \in \{\pm 1\}$, and $\epsilon, h \gt 0$. Define $\theta(t) := Q((t-\epsilon)/h)$, where $Q(z) := \int_{z}^\infty \phi (z)\mathrm{d}z$ is the ...
- 6,853