**10**

votes

**2**answers

244 views

### A generalization of Chebyshev polynomials

What is the monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$? The answer is the Chebyshev polynomial, and its largest value on $[-1,1]$ is $1/2^{n-1}$.
Now suppose ...

**0**

votes

**0**answers

48 views

### Nonlinear optimization problem with inequality constraints

Consider a real valued function $g(x_i)=\frac{1}{a_1+ \frac{a_2}{x_i}}, \forall i=\{1,2,3,...,n\}$.
The objective function $H$ is
$H=\sum_{i=1}^{n}\frac {1}{g(x_i)-a_3x_i}$
The optimization ...

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

**2**

votes

**1**answer

78 views

### Do the values of the differential of a function on a Lie group with a single maximum span the Lie algebra?

Consider: a vector field $X=\nabla \phi$ on a compact, semi-simple, connected matrix Lie group $G$ where $\phi$ as a smooth scalar field on $G$ possessing only a single maxima which topologically is a ...

**0**

votes

**0**answers

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

**5**

votes

**0**answers

167 views

### Is there a name for this quantity between two distributions?

Let $f$ be a probability density on a compact domain $D$, and say that $x_1,\dots,x_n$ are samples from $f$. If we wanted to compute the Wasserstein distance between $f$ and the empirical ...

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

**1**answer

108 views

### Gradient on $SU(n)$

I'm trying to calculate the gradient (wrt to the bi-invariant metric) of the following functions $F_1, F_2 : SU(n) \rightarrow \mathbb{R}$ defined by $F_1(U) = | Tr (G^{\dagger} U) |^2$, $F_2(U) = \Re ...

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

**1**answer

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

**4**

votes

**1**answer

126 views

### Basic result in semi-infinite linear programming

Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...

**0**

votes

**0**answers

41 views

### Questions about the definition of ``stabilization entropy" for dynamical systems

Let $\phi (t,x,u)$ be the solution to the differential equation, $\dot{x}(t) = f(x(t),u(t))$ where $x(t) \in \mathbb{R}^d$, $u : [0,\infty) \rightarrow \mathbb{R}^m$ and $f: \mathbb{R}^d \times ...

**4**

votes

**2**answers

106 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? ...

**0**

votes

**0**answers

107 views

### Duality results for quadratic equality constrained optimization problem

Consider the optimization problem
$$
\begin{align}
\min_{x\in\mathbb{R}^n}&\quad f(x) = x^TA_0x+b_0^Tx+c_0\tag{P1}\\
\nonumber \text{subject to } \quad & g_i(x) = x^TA_ix+b_i^Tx+c_i = ...

**14**

votes

**4**answers

477 views

### Maximum of the Vandermonde determinant / minimum of the logarithmic energy

The problem is to find the asymptotics (as $n\to\infty$) of the maximum (say $M_n$) of the Vandermonde determinant
$$V_n:=\prod_{0\le i<j\le n-1}(a_j-a_i)
$$
over all $a_0,\dots,a_{n-1}$ such ...

**6**

votes

**2**answers

239 views

### Do computational geometers use Lagrange multipliers?

Can anyone point me to an example of a problem that (more or less) originated in computational geometry whose solution requires the use of Lagrange multipliers (or Kuhn-Tucker conditions, or dual ...

**2**

votes

**1**answer

211 views

### Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...

**0**

votes

**0**answers

120 views

### Maximizing Expected Utility

I am currently trying to solve a maximization problem given by
$\max_{f(x)} \int_0^1 \int_\mathbb{R} (c-y\cdot f(x)-d\cdot (x+f(x)-b)^2) \ h(x) \ dx \ dy$.
Or in other words, I have a utility ...

**0**

votes

**1**answer

189 views

### Prove that the following two optimization problems are equivalent

I am trying to solve the following optimization problem for the vector $ y $, where $ A_i $ are some given matrix (maybe low rank) and $ x_i $ are unconstrained
$$ \min_{y, x_i} \sum_{i=1}^J || y - ...

**3**

votes

**0**answers

153 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**9**

votes

**1**answer

353 views

### Sard's Theorem For Banach Spaces

Given a smooth map from $\phi: B \rightarrow M$ where $B$ is a Banach Space and $M$ is a finite dimensional smooth manifold (for example, the end point map for a control system), what is the strongest ...

**2**

votes

**2**answers

251 views

### constant rank theorem for banach spaces

Is there a similar statement to the constant rank theorem for finite dim real smooth manifolds which holds for a smooth map $F:B \rightarrow M$ where $B$ is an infinite (countable) dim Banach space ...

**1**

vote

**0**answers

71 views

### Optimization with random matrix

Consider $J$ a random matrix of size $n\times n$ with i.i.d. Gaussian entries $J_{ij} \sim \mathcal{N}(0,\sigma^2/n)$. Let $f(x)=tanh(x)$, and for $x\in\mathbb{R}^n$, $f(x)$ denotes the vector where ...

**2**

votes

**1**answer

180 views

### Stochastic differential equation associated with an optimal control problem

We know how to find the stochastic differential equation (Hamilton-Jacobi-Bellman equation, HJB) of the control problem where a process $X_t$ is controlled up until it is stopped at a stopping time ...

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

**2**

votes

**1**answer

125 views

### Largest subgroup of $SU(n)$ for which the adjoint action preserves specific inner product on $\mathfrak{su}(N)$

Given $A,B \in \mathfrak{su}(n)$ such that $K(A, B)=0$, I am looking for the largest subgroup $H$ of $SU(n)$ for which:
$K \left(A, Ad_{U}(B) \right) = 0, \ \ \forall U \in H$ where $K$ is the ...

**2**

votes

**0**answers

96 views

### LQR solution when there are linear terms in the cost function?

I am trying to solve the following Bellman Equation:
$V(s) =\max_u \left[a'u - (u-s)'Q(u-s) + V(u)\right]$
In the equation above, $s,u,a\in \mathbb R^n$, $Q\in \mathbb R^{n\times n}$ is positive ...

**0**

votes

**1**answer

155 views

### Existence of a Lie algebra element orthogonal to the adjoint orbit of another element

Consider a compact, semi-simple, connected Lie group $G$ and its Lie algebra $\mathfrak{g}$. Denote the Killing form by $K$.
Given a single $A \in \mathfrak{g}$ when (i.e. which groups and which $A$) ...

**1**

vote

**0**answers

32 views

### Minimizing sum of functions, while keeping their values non-negative

Suppose we have data $\mathbf{x}_i$, $i\in \{1, \ldots, K\}$, and we're trying to find parameters $\hat{\mathbf{\theta}}$ such that
$$\hat{\mathbf{\theta}} = \underset{\mathbf{\theta}} ...

**2**

votes

**1**answer

152 views

### Can the nonlinear matrix equation $Bx=p+sgn(x)$ have an explicit solution?

Given $n > 0$, $0 \leq i \leq n$ is an integer, $D = diag(d_1, \dots, d_n)$ is positive definite, $e_i$ is the $i$th column of a $n \times n$ identity matrix, $u \in R^n$ such that $B = D + u * ...

**3**

votes

**0**answers

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

**12**

votes

**0**answers

167 views

### Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...

**5**

votes

**0**answers

68 views

### Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...

**0**

votes

**0**answers

34 views

### Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...

**5**

votes

**1**answer

180 views

### The Maximal $\ell_2$ norm of a signed sum of vectors

Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors:
$$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$
where $s_j$'s can only take values of $+1$ or $-1.$ I ...

**4**

votes

**1**answer

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

**2**

votes

**0**answers

125 views

### Fixed area, largest mass — is there a name?

Let $x\in \mathbb{R}^n$ and let $s_k(x)$ denote the sum of the $k$ largest entries of $x$. The function $s_k(x)$ is well-known to be convex and is often used in optimization, such as
...

**0**

votes

**1**answer

110 views

### How to minimize this sparse quadratic function?

There is a problem when I'm reading a paper.
Equation:
$min_p|p-p^*|^2+\alpha |R(p)|^2 + \beta |D(p)-\delta|^2$,
where $p, p^*, R(p), D(p), \delta$ are all $M\times N$ matrices, and $p^*, R(), D(), ...

**2**

votes

**2**answers

355 views

### Why the 'S' in S-procedure/S-lemma?

The S-procedure (also called as S-lemma) is a technique from V. A. Yakubovich that is used to relax a system of quadratic inequalities to a linear matrix inequality problem. It is used largely in ...

**1**

vote

**0**answers

63 views

### Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...

**1**

vote

**1**answer

101 views

### What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely,
$X \in ...

**1**

vote

**0**answers

113 views

### Proximal mapping of composition with linear operator

Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by
$$
(I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x),
$$
as ...

**1**

vote

**0**answers

89 views

### Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that
$$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$
It is called a controlled Markov process.
Now, suppose there exist $\epsilon_0$, ...

**1**

vote

**1**answer

381 views

### finding permutation matrix I which minimizes TRACE( I* C*( I^T)* D) matrix

I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case...
thanks for your help in advance
I want to find permutation ...

**1**

vote

**1**answer

61 views

### characterization of a certain closed convex cone

Consider $x_1,\cdots,x_n \in \mathbb{R}^d$, and the closed convex cone in $\mathbb{R}^n$ defined by
$$\mathcal{K}(\underline{x}):=\{(\varphi(x_1),\cdots,\varphi(x_n)):\varphi \textrm{ convex on ...

**2**

votes

**1**answer

177 views

### Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...

**8**

votes

**2**answers

270 views

### Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...

**2**

votes

**1**answer

92 views

### Standard names and methods for this type of fitting minimization

In material science research, we have come across the following type of problem.
Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization
$$\eqalign{
...

**3**

votes

**0**answers

116 views

### This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by ...

**2**

votes

**0**answers

98 views

### Copositivity under tensor products

Is there any symmetric real matrix $A$ such that $A^{\otimes n}$ is copositive for all positive integers $n$, but such that A is neither positive semidefinite nor has just non-negative entries?
...