**1**

vote

**0**answers

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

**0**

votes

**1**answer

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

**1**

vote

**0**answers

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

**4**

votes

**0**answers

64 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

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

**4**

votes

**0**answers

34 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

37 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

71 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

115 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

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

**1**

vote

**0**answers

29 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

67 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

92 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

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

**3**

votes

**0**answers

251 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

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

**1**

vote

**1**answer

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

**0**

votes

**0**answers

28 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

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

**0**

votes

**0**answers

35 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}
...

**1**

vote

**1**answer

61 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}
...

**4**

votes

**1**answer

53 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

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

**3**

votes

**1**answer

68 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

75 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

45 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

**1**answer

67 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

159 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

96 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

81 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

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

**1**

vote

**1**answer

89 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

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

**1**

vote

**1**answer

180 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

112 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

309 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

139 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

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

**6**

votes

**2**answers

210 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

297 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

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

**0**

votes

**0**answers

26 views

### Practical bundle methods

What is the most widely applied bundle method currently available? I am trying to solve a large convex optimization as accurate as possible with dimension being roughly 5000+.... Thank you.

**2**

votes

**1**answer

76 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\{ ...

**2**

votes

**1**answer

53 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

**0**answers

71 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

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

**0**

votes

**0**answers

51 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

98 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

149 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

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