**4**

votes

**2**answers

96 views

### Questions concerning convergence rate of Iterated Projections

Assume for simplicity $C_1,C_2,...,C_n\subset \mathbb{R}^m$ to be closed and convex subsets with $\underset{i=1}{\overset{n}{\bigcap{}}}C_i\neq\emptyset$.
Let $x^0\in\mathbb{R}^n$ and define the ...

**2**

votes

**0**answers

35 views

### Constrained absolute orientation of 3D point sets

Let us assume we have two 3D point sets, $P=\{p_i\}$ and $Q=\{q_i\}$, and that we need to recover the transformation that takes $P$ as close to $Q$ as possible. In particular, I am interested in roto-...

**0**

votes

**1**answer

56 views

### How to compute the direction of slowest ascent from the minimum of a strongly convex function?

Consider a twice differentiable strongly convex function $f:\mathbb{R}^n \rightarrow \mathbb{R^+}$ that attains its minimum value at the point $x^*$. I am wondering if one can compute a direction of ...

**2**

votes

**0**answers

80 views

### About optimizing a convex function on a hypercube

Given a real valued convex function $g$ on $[-1,1]^n$, let $f$ be the restriction of it on the hypercube $\{-1,1\}^n$. I want to find a vertex on the hypercube $\{-1,1\}^n$ on which either (1) $f$ ...

**5**

votes

**0**answers

76 views

### Basin of Attraction

I have a function $F$ which is defined as follows:
$$
F(x) = \sum_{i=1}^N f(z_i^T x)
$$
where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...

**2**

votes

**1**answer

123 views

### Minimizing a convex integral function

Consider the following constrained optimization with the integral objective function
$$
\min_{x_i\in D} \int_{t_1}^{t_2} \frac 1 {t - \sum\limits_{i = 1}^N x_i f_i (t)} \, dt
$$
where $t - \sum\...

**4**

votes

**0**answers

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

**2**

votes

**1**answer

58 views

### Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points

I am currently working on a problem where I have to minimize a $m$-strongly convex function
$$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$
over a bounded integer lattice,
$$L = \mathbb{Z}^n \cap [-...

**5**

votes

**2**answers

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

**0**

votes

**2**answers

134 views

### Estimating the shift in the $\lambda_{max}$ of a matrix under a diagonal perturbation

Given a matrix $A$ and a diagonal matrix $D$, what ways do we have to estimate, $\lambda_{max}(A+D) - \lambda_{max}(A)$? (Feel free to make other assumptions about the matrices that they are all ...

**4**

votes

**0**answers

104 views

### An inequality from the “Interlacing-1” paper

This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...

**3**

votes

**0**answers

35 views

### About the partial expectation polynomials in the Interlacing-I paper and perfect matchings

I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf
In the use of these ...

**0**

votes

**1**answer

122 views

### sum of fractional functions optimization problem

Consider the following sum of fractional functions optimization problem
$$
\begin{array}{l}
\mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1}{{{\bf{a}}_i^T{\bf{x}} + {b_i}}}} \\
...

**3**

votes

**2**answers

132 views

### Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...

**1**

vote

**0**answers

68 views

### Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...

**3**

votes

**0**answers

286 views

### Maximizing sum of matrices

Over the last few months, I've been trying to find the solution to a research-related problem I'm having. However, my research is not in mathematics, and my progress toward reaching a solution has ...

**1**

vote

**0**answers

60 views

### Finding optimal linear transformation for intersection of convex polytopes

I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue)...

**1**

vote

**1**answer

33 views

### Finding an unfrustrated set of local linear constraints with given minimal value

Let $ \{F_{i}\} $ be a finite set of linear functionals on a convex compact subset $B\subset\mathbb{R}^{n}$ such that each $F_i$ is $k$-local (acts on $k\ll n$ variables only).
Assume $F=\sum_{i}F_{i}$...

**0**

votes

**0**answers

40 views

### Distance minimization and submodular functions

I have a question about square distance minimization and submodular functions. Suppose I have a random variable $X = (X_1,...,X_n)$ over $\mathbb{R}^n$. Let $x$ be a realization of this random ...

**0**

votes

**0**answers

52 views

### Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix B)...

**0**

votes

**0**answers

66 views

### Can I use proximal algorithms on complex real-valued functions?

There is a plethora of literature in proximal operators and proximal optimization algorithms specially for Compressive sensing. A proximal operator is defined as
\begin{equation}
\operatorname{prox}_f(...

**2**

votes

**1**answer

122 views

### Nuclear norm (convex) minimization with complex-valued matrices?

Rank minimization subject to some constraints can be accomplished in many cases through the nuclear norm.
\begin{align}
\min_{X}.\,\,& \left\|X\right\|_* \\
\text{s.t. }& X\in\mathcal{C}
\end{...

**4**

votes

**1**answer

75 views

### Self-concordant function for dual cone

I wonder if there is any existing result for self-concordant function in the literature about the following question.
Suppose $f$ is a self-concordant barrier function of a proper cone $K$ (pointed, ...

**3**

votes

**1**answer

407 views

### Find the minimum distance between two convex hulls

We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...

**4**

votes

**1**answer

163 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 \...

**0**

votes

**1**answer

96 views

### Constrained optimal control problem

I am trying to solve an optimization problem which is probably reminiscent of optimal control theory but all of this is not exactly my field of expertize and I am a little bit lost in translation. If ...

**0**

votes

**0**answers

47 views

### Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N \...

**2**

votes

**2**answers

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

**1**

vote

**2**answers

177 views

### Lower bound for $ \sum_{i=1}^n x_i f(x_i)$ when $\sum_{i=1}^{n}x_i = K$

Considering,
the set of all n dim. vectors $\{x_i\}_{i=1,...,n} $ such that $x_i \geq 0 $ and $\sum_{i=1}^{n}x_i = K$
Any continuous and strictly increasing function $f^+(x)$ : $ \mathbb R^+ \to \...

**5**

votes

**1**answer

102 views

### How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...

**4**

votes

**2**answers

110 views

### Convex optimization with full subdifferential information

Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? ...

**1**

vote

**0**answers

37 views

### Condition for maximizer of convex combination to be expansion mapping

I have $\Pi_n:\mathbb R^{n+1}\rightarrow \mathbb R$ and $F_n:\mathbb R^2\rightarrow \mathbb R$ with $$F_n(x,a)=\Pi_n(x,...,x,a)$$
$$f_n(x)=\operatorname{ArgMax}_{a\in\mathbb R}\{F_n(x,a)\} $$
such ...

**4**

votes

**1**answer

156 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 + \...

**2**

votes

**1**answer

171 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?

**2**

votes

**1**answer

294 views

### Is there any way to compare between diagonals of a resolvent and a Cauchy transform?

Say $A$ is a symmetric matrix of $n$ dimensions. Then let the ``resolvent" of $A$ be the matrix valued function $R_A(z) = \frac{1}{z-A}$ and its Cauchy transform be the real valued function $C_A(z) = ...

**0**

votes

**1**answer

113 views

### polynomial expression for counting number of integral points of a set

Let $v_i=a_ie_i\in\mathbb R^d$ and $w_i=b_ie_i\in\mathbb R^d$ for $i=1,\dots,d$ where $e_i$'s are unit vetcors and $a_i,b_i$ are positive integers. Let $$S=conv\{0,rv_i+sw_i:i=1,\dots,d\}.$$
Can we ...

**2**

votes

**2**answers

362 views

### Can one estimate the distribution of eigenvalues of a matrix by its Cauchy/Stieltje transform?

Given a real symmetric $n$ dimensional matrix $A$, with eigenvalues $\lambda_i$ I am defining its Cauchy transform as the function, $f_A(z) = \sum_i \frac{1}{z-\lambda_i}\,$
Is there any information ...

**2**

votes

**1**answer

173 views

### Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...

**3**

votes

**1**answer

162 views

### Condition number after preconditioning

Suppose $A$ and $P$ are symmetric, positive definite matrices and that we factor $P^{-1}=EE^\top.$ Is it true that the condition number of $PA$ is upper-bounded by the condition number of $E^{-1}AE^{-...

**6**

votes

**2**answers

217 views

### What methods do we have to understand the spectrum of matrices with restricted entries?

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $n \times n$ matrix ...

**5**

votes

**2**answers

332 views

### Minimum of squared sum minus sum of squares

I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...

**2**

votes

**1**answer

141 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

**1**answer

93 views

### smooth minimization of piecewise linear convex function

Is it possible to apply Nesterov's smooth minimization of non smooth function on a problem of the form
$$\mathop {\min }\limits_{\lambda \in {R^m}} \mathop {\max }\limits_{\sigma \in {{\left\{ {0,1}...

**2**

votes

**1**answer

58 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 $F(0)=a+b$....

**2**

votes

**0**answers

94 views

### l1 Quadratic Programming [closed]

Within a SQP- algorithm it can happen that the constraints of the quadratic sub- problems are infeasible. In order to overcome this infeasibilities, a l1 penalty method can be used according to ...

**2**

votes

**1**answer

96 views

### Functions that are easy to compare to a norm

Let $X$ be a subset of $\mathbb{R}^d$, let $\|\cdot \|_p$ be a norm with $1\leq p\leq\infty$, and let $f:\mathbb{R}^d\to\mathbb{R}$ be a function. I'm trying to find examples of $X$, $p$, and $f$ for ...

**1**

vote

**0**answers

59 views

### Characterization of the maximizer of a function based on a parameter's value

Consider a smooth, continuously differentiable, and jointly concave function $f(x,y,z;a)$, where $x,y$ and $z$ are decision variables and $a$ is a problem parameter.
I have two optimization problems. ...

**3**

votes

**1**answer

133 views

### generalized mean inequality extension

from generalized inequality, we now that for $p>q$, we have $M_p(\mathbf{x})\ge M_q(\mathbf{x})$. now I am curious to know if we can find a constant $\alpha(p,q)$ which is only function of $p,q$ ...

**3**

votes

**2**answers

163 views

### Constructing a quasiconvex function [closed]

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called
convex if
$$
f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, \...

**1**

vote

**1**answer

60 views

### monotonicity alike functions

assuming we have two smooth function ${f_1},{f_2}:{R^N} \to R$,
under what condition, we have
${f_1}\left( {{{\bf{x}}_1}} \right) \ge {f_1}\left( {{{\bf{x}}_2}} \right) \leftrightarrow {f_2}\...