# Questions tagged [nonlinear-optimization]

Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.

428
questions

**25**

votes

**5**answers

1k views

### Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...

**24**

votes

**1**answer

904 views

### Finding the closest matrix to $\text{SO}_n$ with a given determinant

$\newcommand{\GLp}{\operatorname{GL}_n^+}$
$\newcommand{\SLs}{\operatorname{SL}^s}$
$\newcommand{\dist}{\operatorname{dist}}$
$\newcommand{\Sig}{\Sigma}$
$\newcommand{\id}{\text{Id}}$
$\newcommand{\...

**14**

votes

**2**answers

817 views

### Conjecture on maximum of symmetric combinatoric function

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture).
(The question was first asked at math.SE, ...

**13**

votes

**1**answer

1k views

### An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.
These subgradients are (assume $x \in$ ...

**11**

votes

**2**answers

845 views

### Quadratic Farkas' Lemma?

The Farkas Lemma says that if a system of linear inequalities implies
yet another linear inequality, then this last inequality can be obtained by
taking a positive linear combination of the ...

**11**

votes

**2**answers

573 views

### Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$

Suppose $f:\mathbf{N} \to [0,1]$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $x,y$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ ...

**11**

votes

**1**answer

429 views

### Is there a “formula” for the point in $\text{SO}(n)$ which is closest to a given matrix?

$\newcommand{\Sig}{\Sigma}$
$\newcommand{\dist}{\operatorname{dist}}$
$\newcommand{\distSO}[1]{\dist(#1,\SO)}$
$\newcommand{\distO}[1]{\text{dist}(#1,\On)}$
$\newcommand{\tildistSO}[1]{\operatorname{...

**10**

votes

**0**answers

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

**9**

votes

**2**answers

241 views

### A (reverse)-Minkowski type inequality for symmetric sums

Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true?
\begin{align*}
\left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...

**8**

votes

**5**answers

344 views

### Nearest matrix orthogonally similar to a given matrix

Given $A,B\in\Bbb R^{n\times n}$ is there technique find $$\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_F\mbox{ or }\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$$ within additive approximation error in $\...

**8**

votes

**2**answers

511 views

### How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it.
Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...

**8**

votes

**1**answer

412 views

### Higher dimensional scutoids?

The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...

**8**

votes

**0**answers

177 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

**4**answers

483 views

### Software for rigorous optimization of real polynomials

I am looking for software that can find a global minimum of a polynomial function over a polyhedral domain (given by, say, some linear inequalities) in $\mathbb R^n$. The number of variables, $n$, is ...

**7**

votes

**2**answers

510 views

### Maximum average Euclidean distance between $n$ points in $[-1,1]^n$

For my research I have designed a metric that is based on the average Euclidean distance between $n$ points in the $n$-dimensional hypercube $[-1,1]^n$. However, I have a hard time finding the maximal ...

**7**

votes

**2**answers

301 views

### Proving an infinite norm minimization problem has finite support (non-convex p-norms)

Consider an optimization problem over infinite variables:
$$
\begin{align}
\min_{x}~& {\left\lVert{x}\right\rVert }_p
\\
\text{s.t}~& \left\langle x, a_n\right\rangle \ge 1~,~\forall n=1,\...

**7**

votes

**1**answer

235 views

### Is the solution of this optimization problem always positive semidefinite?

We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:
$$ \sup_H \left\{ x^*...

**7**

votes

**1**answer

285 views

### Generalized Rayleigh-quotient gradient flow on Grassmannian

The following theorem appears without proof in :
Helmke, Uwe, and John B. Moore. Optimization and dynamical systems. Springer Science & Business Media, 2012.
Let $A$ be a symmetric $n\times n$ ...

**7**

votes

**0**answers

158 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)=\...

**7**

votes

**0**answers

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

**7**

votes

**0**answers

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

**6**

votes

**4**answers

2k views

### Prove that this expression is greater than 1/2

Let $0<x < y < 1$ be given. Prove
$$4x^{2}+4y^{2}-4xy-4y+1 + \frac{4}{\pi^2}\Big[
\sin^{2}(\pi x)+ \sin^{2}(\pi y) + \sin^{2}[\pi(y-x)] \Big] \geq \frac{1}{2}$$
I have been working on this ...

**6**

votes

**2**answers

565 views

### How to prove $e^x\left|\int_x^{x+1}\sin(e^t) \,\mathrm d t\right|\le 1.4$?

Related question asked by me on Math SE a few days ago: How to prove $e^x\left|\int_x^{x+1}\sin(e^t) \,\mathrm d t\right|\le 1.4$?
A few days ago, somebody asked How to prove $ \mathrm{e}^x\left|\...

**6**

votes

**1**answer

295 views

### Generalization of the equilateral triangle?

I consider points in the two-dimensional plane.
An equilateral triangle is a set of three points in the plane which are equidistant.
Suppose now I have $n$ points $x_1,...,x_n$. What is the ...

**6**

votes

**2**answers

484 views

### Can we decompose a polynomial into difference of convex polynomials?

Given a multivariate polynomial $p(x_1, ..., x_n)$ on $\mathbb{R}^n$, can we always decompose it into the difference of two convex polynomials? i.e., is there a pair of convex polynomials $f$ and $g$, ...

**6**

votes

**1**answer

184 views

### How to solve optimization problems on manifolds?

I encountered some optimization problem on the special Euclidean group SE(3) at work and wonder how to solve it. The current approach of my colleagues was to use a local parametrization of the ...

**6**

votes

**1**answer

515 views

### Bound on the sum of arguments

Problem: Show that for all real $s,t,u$ and all complex $z$ with $|z|<1$ one has
$$(*)\qquad \arg\frac{1-zf(s-u)}{1-zf(s+u)}
+\arg\frac{1-zf(t+u)}{1-zf(t-u)}<\pi,
$$
where $f$ is the ...

**6**

votes

**1**answer

147 views

### Adding constraints as penalty with $\| \cdot \|_0$ norm

In the paper Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries (page 2), the authors rewrite the minimization problem
\begin{align}
\min_{\alpha \in \mathbb R^k} \| \...

**6**

votes

**1**answer

1k views

### Finding a point maximizing the minimal distance to a set of points

Given a set of of $N$ points $\{\mathbf x_i \in \mathcal{S}^d\}_{i = 1, \ldots, N}$, where $\mathcal{S}$ is a set of possible values, how can I find the point $\mathbf x^*$ that maximizes the minimum ...

**6**

votes

**1**answer

2k views

### max-min optimization problem

I'm curious if there is any nice way to approach solving the following kind of optimization problem. Given a $n \times m$ matrix $A = (a_{ij})$, I want to solve
\begin{align*}
& \max_{c}\min_{1 \...

**6**

votes

**0**answers

99 views

### another extremal property of regular polygons

$\newcommand{\R}{\mathbb{R}}\newcommand{\D}[1]{\Delta_{#1}}\newcommand{\set}[1]{\{#1\}}\newcommand{\abs}[1]{\lvert#1\rvert}\newcommand{\E}{\mathbb{1}}$
In 1984 S.D.Berman, a Soviet mathematician, ...

**6**

votes

**0**answers

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

**6**

votes

**0**answers

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

**5**

votes

**2**answers

381 views

### Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$

Look at the expression
$$
f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1.
$$
The numbers $x_1,x_2,x_3$ are non-negative, and I assume that $x_1+x_2+x_3=3$. This is a sum of squares and "...

**5**

votes

**4**answers

2k views

### Levenberg's original article “A method for the solution of certain problems in least squares”

Does there exist any digital copy of the original article (or a transcript) K. Levenberg, A method for the solution of certain problems in least-squares, Quart. Appl. Math. 2 (1944): 164-168?
It is (...

**5**

votes

**2**answers

1k views

### Find minimum-area ellipse which encloses two ellipses

I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...

**5**

votes

**2**answers

256 views

### Can this optimization problem be transformed into or approximated by a SOCP?

We would like to know if the following optimization problem can be transformed into an SOCP problem or maybe approximated by a SOCP problem. The objective function is defined as
$$
\mathrm{Obj}(x) = \...

**5**

votes

**1**answer

180 views

### Surprisingly simple minimum of a rational function on $\mathbb R_+^n$

Motivation:
The following problem has occurred in a study of energy dissipation in a chain of coupled, damped oscillators.
The problem:
Let me define specific rational functions $f$, $g$, and $...

**5**

votes

**1**answer

205 views

### Optimization problem on trigonometric polynomials

I would like to maximize
$$
\int_0^{2\pi} \frac{(f'(x))^2}{f(x)}dx
$$
subject to $f(x)\leq 1$ for all $x$
over the space of nonnegative trigonometric polynomials of degree smaller or equal to $n$.
...

**5**

votes

**2**answers

320 views

### convert a special case of nonlinear fractional programming into a convex problem

Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this ...

**5**

votes

**1**answer

855 views

### Solve equation with matrix variable

I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1...K$ are known, and are positive definite matrices. $\Omega$ also has to be ...

**5**

votes

**1**answer

160 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**5**

votes

**1**answer

201 views

### Bounding function of norms in constrained vector space

$v$ is a vector of length $n$, where $v_1 = 1$ and every element $v_i \in [0,1]$
$w = \| v \|_1^1 = \sum_i |v_i| = \sum_i v_i$
$x = \| v \|_2^2 = \sum_i |v_i|^2 = \sum_i v_i^2$
$y = \| v \|_3^3 = \...

**5**

votes

**2**answers

1k views

### Quadratically constrained linear program (QCLP) over $x$ with the linear constraint $x = Az$

I have a problem that looks very much like a norm-constrained linear program, but with an extra constraint that is unusual for me. The problem is the following. Given a matrix $A$ and a vector $w$,
$$...

**5**

votes

**1**answer

43 views

### Optimization with weaker oracle than projection

I'm looking to solve the optimization problem
$$
min_{x \in C} ~ f(x),
$$
where $C \subset R^n$ is a closed, convex, bounded set and $f : R^n \to R$ a Lipschitz differentiable (nonconvex) function.
...

**5**

votes

**1**answer

434 views

### Strong duality for a particular moment problem

Reading the paper in this Link (see pag 13) with the objective of understanding a topic related to stochastic optimization I came across a problem in demonstrating one of the theorems. The situation ...

**5**

votes

**2**answers

332 views

### Discrete optimization problem

Suppose you had $N$ many fixed points $X_1, X_2, ..., X_N$ in some Euclidean space $R^d$ and from these coordinates you had to choose $n$ many of them ($n \leq N$ also being fixed) to form a subset $S$...

**5**

votes

**1**answer

159 views

### Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...

**5**

votes

**1**answer

403 views

### Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...

**5**

votes

**1**answer

251 views

### optimization problem, any solution?

The objective is as follows:
$\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$
$s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$
...