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

learn more… | top users | synonyms (1)

11
votes
2answers
577 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
2answers
580 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
2answers
436 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
1answer
246 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
1answer
464 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
0answers
61 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
2answers
494 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
2answers
301 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
1answer
312 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
2answers
270 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
1answer
163 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
0answers
163 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 ...
5
votes
0answers
183 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 ...
4
votes
2answers
275 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
2answers
217 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
2answers
106 views

Convexity of a (non-symmetric) function of matrices

Let $f : H_{n\times n} (\mathbb{C}) \rightarrow \mathbb{R}$ be the function on Hermitian, positive semidefinite matrices $f(A) = \frac{M_i (A)}{\det(A)}$ where $M_i(A)$ is the determinant of the the ...
4
votes
1answer
241 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
1answer
183 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
1answer
278 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
0answers
151 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
2answers
1k 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
1answer
525 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
2answers
139 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
1answer
150 views

Find a line such that sum of perpendicular distances of points to the line is minimized

Given a set of points (column vectors) $S = \{p_1, p_2, \cdots, p_n\} \subset \Re^d$, let $A \in \Re^{n \times d}$ be a matrix of which each row is just $p_i^T$. It is easy to find a unit vector $s_1$ ...
3
votes
1answer
59 views

Constrained vs Unconstrained Optimization

I'm currently working on an optimization problem with a linear objective with linear and nonlinear constraints, i'm facing difficulties reaching a good solution, so i was advised to move the nonlinear ...
3
votes
1answer
65 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 ...
3
votes
1answer
132 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
1answer
196 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
1answer
216 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
1answer
77 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
0answers
105 views

existence of optimal control

I'm looking for an existential result in optimal control for the following class of problems: Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times ...
3
votes
0answers
82 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 ...
3
votes
0answers
273 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
5answers
252 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
3answers
155 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
2answers
261 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 ...
2
votes
1answer
106 views

Optimization over symmetric polynomials

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 ...
2
votes
2answers
256 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
1answer
236 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
1answer
145 views

Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?

I would like to know whether the following problem is decidable. Is the system $x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$ $x^T Q_j x + r_j \neq 0 \mbox{ for } j = k+1, ..., t$ feasible, ...
2
votes
1answer
357 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
2answers
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
1answer
56 views

Rate of convergence for cyclic gradient descent

I'm trying to solve the optimization problem $\min_x \frac{1}{n} \sum_{i=1}^n f_i(x)$ where $f_i$ are (strongly) convex, smooth, lower semi-continuous, etc. However, I am not able to do conventional ...
2
votes
1answer
46 views

When is a convex program continuous in its constraint vectors?

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
2
votes
1answer
68 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
3answers
349 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
2answers
158 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
1answer
242 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
1answer
401 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
1answer
223 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 ...