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

**11**

votes

**2**answers

613 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

628 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

457 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

257 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

**1**answer

479 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

378 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

**0**answers

65 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

654 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

348 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

**2**answers

102 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

104 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

384 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

153 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

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

**5**

votes

**1**answer

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

**5**

votes

**2**answers

299 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

210 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

178 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

**0**answers

249 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

**2**answers

322 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

252 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

**2**answers

136 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

**2**answers

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

**4**

votes

**1**answer

133 views

### Nonlinear least square with quadratic equality constraint

I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem:
$\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + ...

**4**

votes

**1**answer

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

**4**

votes

**1**answer

110 views

### Constrained optimization (QCLP) over $x$ with the 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, given a matrix $A$ and a vector $w$,
$$ \min_{x ...

**4**

votes

**1**answer

319 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

169 views

### Comparison of Constrained Optimization Methods

I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

139 views

### maximize non-convex composite function

I want to maximize a composite function over a convex set
\begin{equation}
\begin{aligned}
& \underset{\mathbf{p}}{\text{maximize}}
& & f(\mathbf{p})-g(\mathbf{p})\\
& \text{subject ...

**4**

votes

**0**answers

41 views

### How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...

**4**

votes

**0**answers

156 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

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

**1**answer

742 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

**1**answer

96 views

### Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

332 views

### Valid KKT Constraint Qualification? Linear constraints not full rank, Jacobian of nonlinear constraints full rank and independ. of linear constraints

For a nonlinear optimization problem having only linear constraints, by the Linearity Constraint Qualification, no further constraint qualification is required for the Karush-Kuhn-Tucker (KKT) ...

**3**

votes

**2**answers

192 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

252 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

**1**answer

260 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

**1**answer

198 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

245 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

81 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

94 views

### Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...

**3**

votes

**0**answers

129 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

**0**answers

376 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

**5**answers

295 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

**2**answers

184 views

### Maximal minimum for a sum of two (or more) cosines

Please prove (or disprove, and give the correct answer):
$$2 =\mathrm{argmax}_{r\geq 1}\min_{x\in \mathbb{R}}\left[\cos\left(x\right)+\cos\left(rx\right)\right]
$$
In other words, find $r \geq 1$, ...

**2**

votes

**3**answers

163 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

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