# 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 ...

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-...

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 ...

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:
$\...

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
vote

0
answers

36
views

### LICQ vs MFCQ who is stronger [closed]

I want to ask you which constraint is stronger: MFCQ or LICQ.

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 ...

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 ...

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 ...

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}...

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=(\...

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 ...

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 ...

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}^...

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
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 ...

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 ...

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:...

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}^{*} \\ \...

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 \...

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(...

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,...

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 &...

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 ...

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}^...

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} {\...

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_{...

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]$ ...

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 ...

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 ...

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? ...

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 ...

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}$ ...

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 ...

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\...

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 ...

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 $...

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 $\...

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)...

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|^...

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$.
...

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
$$
...

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 ...

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 ...

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}...

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
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 < \...