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

**11**

votes

**2**answers

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

**11**

votes

**2**answers

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

**7**

votes

**2**answers

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

**6**

votes

**1**answer

243 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

**0**answers

59 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

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

**5**

votes

**1**answer

308 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

137 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**5**

votes

**2**answers

267 views

### Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

Consider hermitian positive semi-definite matrices $A_1$ and $A_2$. Consider also positive definite matrices $B_1$ and $B_2$. I want to maximize the minimum of the two Generalized Rayleigh Ritz ratios ...

**5**

votes

**1**answer

150 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

**0**answers

89 views

### Characterizing matrices with rank constraint

Given matrix $M\in\Bbb Z_{\geq0}^{n\times n}$ with highest entry $b$, is there a nice method to characterize non-negative matrices $Q$ such that $$\mathsf{rank}(M+Q)\leq s\cdot\mathsf{rank}(Q)$$with ...

**4**

votes

**2**answers

259 views

### Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...

**4**

votes

**2**answers

196 views

### Convexity of a function of matrices

Let $A$ be an $n\times n$ positive-definite matrix. Let $0<\lambda _1 \leq \lambda_2 \leq \lambda _3 \ldots \leq \lambda _n$ be the eigenvalues of $A$. Let $n\geq k\geq 1$. Is the function $f(A) = ...

**4**

votes

**1**answer

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

**4**

votes

**1**answer

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

**4**

votes

**1**answer

267 views

### Finding all local maximum points of a function?

Let ${\boldsymbol \theta}=(\theta_1,\theta_2,\ldots,\theta_n) \in{\mathbb T}^n$ and $P:{\mathbb T}^n\rightarrow {\mathbb R}$ be a function defined on $n$-torus as
$$
P({\boldsymbol \theta}) = ...

**4**

votes

**0**answers

147 views

### Optimization problem involving Multivariate Normal

I use $\phi(t)$ to describe the standard normal distribution density and $\Phi(t)$ as the normal distribution CDF and would like to prove that for all
$n\geq3$, the function:
...

**3**

votes

**2**answers

945 views

### Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...

**3**

votes

**1**answer

483 views

### The average number of people that can sit on a bench of a given length.

Let me explain what I mean:
The width of the average person varies, perhaps with a normal distribution.
Given a specific variance, how many people (on average) can sit side-by-side on a bench of a ...

**3**

votes

**2**answers

238 views

### Why eigenvectors optimize this orthogonally constrained nonlinear minimization problem?

Given a $p \times p$ positive definite matrix $\Sigma$, why eigenvectors of $\Sigma$, stacked as columns of a matrix $R \equiv [r_1 \, r_2 \, \ldots \, r_p]$, optimize the following orthogonally ...

**3**

votes

**2**answers

131 views

### QR-Decomposition of matrix valued function

Suppose I have a matrix valued function
$$
F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T
$$
where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, ...

**3**

votes

**1**answer

119 views

### Decomposition of a semi-definite matrix into sums of sparse semi-definite matrices

I'll first provide the background.
Let $x\in\mathbb{R}^N$ be decomposed into $n$ non-overlapping blocks of variables
$x^{(1)},\ldots,x^{(n)}$.
We say that $f:\mathbb{R}^N\rightarrow\mathbb{R}$ is ...

**3**

votes

**1**answer

193 views

### Intuition on a certain class of quadratic optimization problems

Let $\mathcal{X} = \{\mathbf{X}\in\mathbb{C}^{d\times d}:\|\mathbf{X}\|\leq 1\}$, where $\|\cdot\|$ is the Frobenius norm. Let $\mathbf{y}\in\mathbb{C}^{d\times 1}$. We are familiar with the following ...

**3**

votes

**1**answer

207 views

### Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type.
Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities
$$Az≥b,$$
and we ...

**3**

votes

**1**answer

75 views

### Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...

**3**

votes

**0**answers

75 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**2**

votes

**5**answers

241 views

### Distance between two sets

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem.
$$ \min ...

**2**

votes

**3**answers

154 views

### Constraint optimization problem for any dimensionality $n>1$.

I am going to post a particular example for the sake of clarity.
One needs to maximize a real function
$F = a_1a_2 + a_2a_3 + \cdots + a_{n -
> 1}a_n + a_na_1;$
with active ...

**2**

votes

**2**answers

174 views

### How to fit the parameters of differential equations with known data?

I have the following data from chemical kinetics research to fit the parameters of ordinary differential equations:
$$
\left[
\begin{array}{ccccccc}
\text{No.}& t & y_1(t)&y_2(t) & ...

**2**

votes

**1**answer

232 views

### How to minimize $-\sum p_b \ln{p_b}$?

Consider multisets of the form $A = \{a_1,\dots,a_n\}$ of integers. Let $q = P(a_i = a_j)$ when $i$ and $j$ are chosen independently and uniformly from $\{1,\dots, n\}$. Let $B$ be the set of ...

**2**

votes

**1**answer

313 views

### lipschitz constant of a multivariate function

I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...

**2**

votes

**2**answers

1k views

### Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...

**2**

votes

**1**answer

65 views

### Entropy dominance

Let $0<a<b<c$ be distinct positive reals.
Define four different probability distributions:
$$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$
...

**2**

votes

**3**answers

327 views

### Solving a quadratic matrix equation with non-squared matrix

I was trying to solve the problem of finding the value of a non-squared matrix $T$ ($n \times m$) which solves
$$ T^T T = X$$
where $X$ is a symmetric and positive semidefinite $m \times m$ matrix, ...

**2**

votes

**2**answers

140 views

### How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?

everyone.
It has been well known that the following minimization problem of a Bregman divergence with linear inequality
can be solved by successively projecting the current point to each constraint ...

**2**

votes

**1**answer

237 views

### Non-linear 1st order difference equation

I have been trying to solve the following difference equation for some time now : $$u^3(n+1) = a - b\cdot u^2(n) + u^3(n), \qquad a \ne 0 \ne b$$
I have tried various substitutions, simplifications ...

**2**

votes

**1**answer

361 views

### Finding zeros of a multi-variable nonlinear trigonometric function

I am trying to calculate analytic solution (or locus) of zeros of a very large multi-variable function which is consisted of thousands of nonlinear trigonometric terms. All the variables are real ...

**2**

votes

**1**answer

215 views

### Does Quadratic Programming get easier when it's described by a diagonal matrix?

Generally, Quadratic Programming solves the problem
$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$
In this form, Quadratic Programming is ...

**2**

votes

**2**answers

188 views

### product of variables in objective function

Hi there,
I'm looking for a solver that allows me to solve an optimization problem of the form min x1*x2*x3,...,xn subject to some linear constraints. I've used gurobi before, however I couldn't find ...

**2**

votes

**1**answer

407 views

### An algorithm for checking if a nonlinear function f is always positive

Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?
The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or ...

**2**

votes

**0**answers

50 views

### How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem
$$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$,
$$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...

**2**

votes

**0**answers

77 views

### Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem:
\begin{align}
&\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\
&\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}.
...

**2**

votes

**0**answers

44 views

### Sequence transformations that are entropy invariant

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Define entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$
by ...

**2**

votes

**0**answers

82 views

### Techniques for proving that a set of constraints over the integers are inconsistent

I have a problem which boils down to showing that a set of constraints has no solutions. A simplified version of this constraint system would be the following system:
$$
\left\{
\begin{array}{l}
...

**2**

votes

**0**answers

222 views

### Subtour Elimination in Travelling Salesman Problem using MTZ

I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints.
To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

146 views

### Quadratic optimization with parameter in constraint

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum.
Question: Given a function $q: \mathbb R^{N\times N}\mapsto ...

**2**

votes

**1**answer

403 views

### Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...

**1**

vote

**2**answers

189 views

### what method can I employ to solve this optimization problem which involves \min?

The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N ...

**1**

vote

**1**answer

47 views

### Maximizing a certain concave function over a non-convex set

I have been working on a problem which involves maximizing a concave function over a non convex constraint set. The problem is the following $$max. \frac{1}{2}x^TBx\\ s.t.\ x_i(1-x_i)=0,\ \ ...