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

**11**

votes

**2**answers

604 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

617 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

453 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

253 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

478 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

351 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

64 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

578 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

341 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

85 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

99 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

345 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

151 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

91 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

**2**answers

296 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

199 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

191 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

**0**answers

174 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

234 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

315 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

244 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

130 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

**1**answer

89 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

312 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

89 views

+100

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

117 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

38 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

155 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

688 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

73 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

252 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

184 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

**2**answers

162 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

231 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

180 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

197 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

234 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

80 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

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

**3**

votes

**1**answer

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

**3**

votes

**0**answers

87 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

121 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

349 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

271 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

160 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

314 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

**1**answer

71 views

### Better alternative to solve quadratic programming for large matrices

I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...

**2**

votes

**1**answer

72 views

### Fixed point iteration on symmetric biconvex function

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...

**2**

votes

**1**answer

168 views

### How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?