**0**

votes

**1**answer

242 views

### Is it known that every PDF continuous in all $R^n$ has a maximum? [closed]

I'm working with maximum a posteriori estimation and managed to show that every probability density function that is continuous in all $R^n$ always has at least one global maximum. I've search around ...

**10**

votes

**1**answer

241 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**1**

vote

**1**answer

135 views

### Nonlinearly constrained optimization (quadratic)

Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear ...

**2**

votes

**1**answer

133 views

### Proving that a constructed curve solves an optimization problem

Caveat up-front: I'm not a mathematician, so please excuse any stupidity/ignorance that follows. First, let me explain what I'm trying to do: I want to choose a function that maximizes the following ...

**27**

votes

**1**answer

1k views

### Optimization problem arising from the study of zeta zeros

Motivation: The following problem arose in [1] while studying the vertical distribution of the zeros of the Riemann zeta-function. At the time, my collaborators and I were unable to solve it and I ...

**4**

votes

**1**answer

231 views

### An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...

**1**

vote

**1**answer

168 views

### Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...

**2**

votes

**0**answers

195 views

### Copositive matrix?

I want to check under what conditions a matrix of the form $\alpha J -Q$ is copositive, where $J$ is the all-ones matrix and $Q$ is doubly nonegative (i.e. entrywise nonnegative and positive ...

**2**

votes

**1**answer

156 views

### Lipshitz Constant of the convex extension of a submodular function

The title says it all :)
Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function ...

**0**

votes

**0**answers

224 views

### A question regarding Danskin's theorem

Suppose $\phi({\bf x},{\bf z})$ is a continuous function of two arguments,
$\phi: {\mathbb R}^N \times Z \rightarrow {\mathbb R}$,
where $Z \subset {\mathbb R}^m$ is a (non-empty) compact convex ...

**0**

votes

**1**answer

226 views

### Constrained Optimization: Matrix Inverse in Objective/Constraints?

Made a crucial mistake in the problem formulation; please delete.

**7**

votes

**2**answers

398 views

### Eigencircles of n x n matrices?

An eigenvalue of a 2 x 2 matrix satisfies the equation
$$ \left(\begin{array}{cc} a & b \\\\ c & d \end{array} \right)\left( \begin{array}{c} x \\\\ y \end{array}\right) = \lambda \left( ...

**1**

vote

**1**answer

202 views

### f_n(x,p) converge uniformly to nice f(x,p); do zeros of f_n(.,p) converge uniformly to zeros of f(.,p)?

Fix compact intervals $X, P \subseteq \mathbb{R}$.
Let $f_n : X \times P \to \mathbb{R}$ be a sequence of $C^2$ functions converging uniformly to a $C^2$ function $f$. The first and second ...

**1**

vote

**1**answer

225 views

### Solving a QCQP problem with sparse regularization

I want to solve the follong QCQP problem:
$$
\mbox{Minimize}\quad\beta^TA\beta+\mu\Omega(\beta)$$
$$
\mbox{s.t.}\quad\beta^TB\beta=1 \quad\mbox{and}\quad\beta\ge0
$$
where $A$ and $B$ are both ...

**1**

vote

**2**answers

351 views

### Sherali-Adams relaxation

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...

**0**

votes

**3**answers

843 views

### Solving a non-convex quadratically constrained quadratic program

I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is ...

**7**

votes

**2**answers

345 views

### More general form of inequality?

I have proved a simple Lemma that I need for a larger result, and I was wondering whether it is actually another more famous result in disguise.
The lemma says that for any set of vectors in ...

**3**

votes

**0**answers

147 views

### stochastic control / geometric mean

Consider the following problem:
Given $\Omega$ and $U$ two symmetric definite positive matrices, choose a matrix $K$ to minimize the expectation $x' \Omega x + x'K'UKx$ when $x$ follows the invariant ...

**2**

votes

**1**answer

132 views

### Maximizing positive definite quadratic using the eigendecompoisition

Consider the problem:
$\textrm{max}\;\; x^T Q x$
subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.
I believe this problem is NP-hard (although I have only found hardness ...

**1**

vote

**1**answer

308 views

### conjugate function for matrix mixed norm

I am familiar with the conjugate function of the vector norm, which uses the concept of dual norm and is defined as follows:
...

**1**

vote

**0**answers

220 views

### Matrix conditions under which spectral radius is smaller than 1?

Hello everyone,
I would like to find out which conditions are necessary so that the spectral radius $\rho(M)<1$ where $M$ represents the following matrix:
$M = \left( \begin{array}{ccc}
W & 0 ...

**6**

votes

**5**answers

2k views

### Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms

Just a new guy in optimization. Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms?

**2**

votes

**1**answer

224 views

### Generalized unique nearest point problem for a compact, convex set in a strictly convex Banach space.

If $X$ is a Real Banach space with strictly convex norm, it is known that for any non-empty compact, convex set $K$ and point $x_0\notin K$, there exists a unique point $z_0\in K$ minimizing the ...

**1**

vote

**1**answer

264 views

### Projection onto a quadratic cone?

Consider a constraint of the form
$$ f(x) := x^T A x = 0 $$
where $A \in \mathbb{R}^n$ is symmetric but may be singular and indefinite. The constraint set $C$ is a (nonconvex) cone, since for any ...

**2**

votes

**1**answer

369 views

### faces of a polytope

Let $a_1,a_2,..,a_n\in\mathbb{R}^m$, $n>m$ and the points are in general position meaning, no hyperplane contains more than $m$ points. Define a polyhedron $$P=\{x\in\mathbb{R}^m:a_1'x\leq0, ...

**1**

vote

**1**answer

138 views

### optimization related to sdp

I have the dual solution of an sdp problem and strong duality hold in this case, I have the dual feasible solutions . From the Dual feasible solutions can i get the primal feasible solution?

**5**

votes

**5**answers

1k views

### Application of polynomials with non-negative coefficients

Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...

**8**

votes

**1**answer

197 views

### Algorithm for matching in the power set lattice

Suppose that we have two probability distributions, $f$ and $g$ on the subsets of a finite set $X$, i.e. $f, g: P(X) \to [0,1]$, with
$$
\sum_{A \subseteq X} f(A) = \sum_{A \subseteq X} g(A) = 1.
$$
...

**2**

votes

**1**answer

1k views

### Sufficient conditions for gradient descent convergence

I have an unconstrained optimisation problem with convex objective function $f(x)$. Suppose I have access only to some function of the gradient $\hat{\nabla}= g(\nabla f)$, and I take gradient steps ...

**3**

votes

**2**answers

624 views

### Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...

**5**

votes

**0**answers

123 views

### Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ vertices. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles which vertices are some vertices of $P$. I ...

**2**

votes

**1**answer

127 views

### Relations between a set of inner products of vectors

Suppose we have n normalized vectors on an arbitrarily large Hilbert space $|A_1\rangle,\dots,|A_n\rangle$, $\langle A_i|A_i\rangle=1$ for every i. And there're $\frac{n(n-1)}{2}$ inner products ...

**7**

votes

**2**answers

317 views

### Entropy conjecture for distributions over $\mathbb{Z}_n$

Suppose we have two independent random variables $X$ (with distribution $p_X$) and $Y$ (with distribution $p_Y$) which take values in the cyclic group $\mathbb{Z}_n$. Let $Z = X +Y$, where the ...

**3**

votes

**1**answer

274 views

### Stronger bound for a modified Lyapunov Equation

In regard to the stability analysis and control properties of the linear system $\dot{x}=Ax$.
Consider the solution $P$ of the continuous Lyapunov equation $AP+PA^T+Q=0$, where $A,Q,P
\in
...

**2**

votes

**1**answer

202 views

### Nearest trio of neighbours for non-intersecting ellipses

Hi,
I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've ...

**2**

votes

**4**answers

839 views

### Fractals as solution to optimization problem?

What's the scientific reason for fractals being present in nature at such a large scale? Is it perhaps the solution of an optimization problem? For example, would the fractal based shape of certain ...

**3**

votes

**1**answer

335 views

### What is the minimum of the Frobenius norm in the intersection of positive semidefinite cones?

For scalar variables $x$, we have a simple solution for the following problem.
\begin{eqnarray}
\min_x&&\alpha(x-a)^2+\beta(x-b)^2 \\\
\mathrm{s.t. }&&x\leq a\\\
...

**0**

votes

**0**answers

274 views

### Mathematics of Rectangles

1/i m looking for all stuff relative to Rectangles Set (specialty rectangles with edges parallel to axes of orthonormal 2d space: lets note it $RS$.
i found this interesting article A new tractable ...

**3**

votes

**1**answer

185 views

### Integral of a quadratic on a polygon (variations of discrete surfaces)

This question is pretty simple to state: given two linear functions on a polygon, I'm looking for a formula for the integral of their product which depends only on the values at the (unlabelled) edges ...

**2**

votes

**3**answers

603 views

### An Optimization problem

The following unusual optimization problem came up and I don't know where to begin:
Maximize over the real variables $x_1, \dots, x_n$ the sum
$$
S = \sum_{r = 1}^n \frac{1}{x_1 + \dots + x_r}
$$
...

**3**

votes

**2**answers

252 views

### Optimal control problem with control derivative.

I faced to a bit weird control problem, that is minimize cost functional
\begin{equation}
J(u) = \int_0^Tg(t,x(t),u(t),\dot u(t))dt
\end{equation}
subject to
\begin{equation}
\dot x(t) = ...

**1**

vote

**0**answers

159 views

### Finding a curve of some approximate arc length (with uniform or zero curvature) with a specified distance to a set of points in 3-space

Imagine I define a set of $N$ points in 3-space, $P$, and I would like to define a straight-line or curve, $C$, with uniform or zero curvature, that has some desired distance, $M$, to each of these ...

**2**

votes

**1**answer

187 views

### Is the following function convex-\cap? How to maximize it?

This question got no answer or comments on Math Stackexchange:
http://math.stackexchange.com/questions/104114/is-the-following-function-convex-cap
Let $p=(p_1,\ldots,p_n)$ be a given nondegenerate ...

**4**

votes

**0**answers

87 views

### Applications of k-medians with moment constraints

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the ...

**3**

votes

**1**answer

330 views

### Solving for Hamiltonian path with constraints on allowable routes through vertices

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...

**2**

votes

**1**answer

242 views

### Optimization of a Specific Polynomial

I have a polynomial:
$$f(x_1 \dots x_n) = \prod_{i=1}^n (c_ix_i + 1) - \frac{1}{2}c_0\sum_{i=1}^nx_i^2$$
Given some values for $c_0 \dots c_n$, I'd like to choose the maximizing values for $x_1 ...

**3**

votes

**2**answers

236 views

### Analogue of PSD matrices for permanents?

Let's begin with a few observations. Suppose we consider the set of $N\times N$ matrices and consider the matrices with positive determinant. There are several connected components in this set; let ...

**0**

votes

**0**answers

123 views

### Conic fitting with pseudoinverse technique

I am trying to fit points of an ellipse to my model using pseudoinverse technique described in this paper (it's in section 4.1). I'm sure that my understanding is wrong, please, could you give me ...

**1**

vote

**1**answer

263 views

### A positive semidefinite programming problem

Dear all,
I've got a SDP problem as follows:
$\min_{{\bf H}\succeq0}\quad trace({\bf H}) - {\bf a}^{\top}{\bf H}{\bf b}$,
where ${\bf a}$ and ${\bf b}$ are two constant vectors. May somebody tell ...

**4**

votes

**2**answers

226 views

### Lagrangian duality

Suppose we have a primal problem
$
\min_x f(x), s.t. h_i(x)=0,
$
where $h_i$ are all affine, and $f$ is convex.
Then its Lagrangian is
$\min_x \max_{z_i} f(x) + \sum_i z_i h_i(x)$
and the dual ...