Operations research, linear programming, control theory, systems theory, optimal control, game theory

learn more… | top users | synonyms

3
votes
1answer
348 views

Difference between 'generalized gradient' and 'subgradient' ?

Hi, I am wondering what the difference between 'generalized gradient' and 'subgradient' of a (potentially non-differentiable) convex function 'f' is. The generalized gradient I am interested in is ...
2
votes
1answer
64 views

(A)periodicity and (In)dependence on the boundary condition for optimization problem related to ODE

The question is pair to MO117505 and translates some problem on error-correction codes to similar problem about differential operators. (See also If “force” is periodic does it imply “velocity” is ...
3
votes
2answers
259 views

Minimum eigenvalue of a Affine Combination of two Hermitian matrices

Consider two $N \times N$ hermitian indefinite matrices $A_1$ and $A_2$. Consider their affine combination \begin{align} M(t)=(1-t)A_1+tA_2 \end{align} I am interested in the minimum eigenvalue of ...
0
votes
0answers
98 views

maximum of the sum of polynomials

Hi I have $n$ polynomials, each one is positive over a certain range and the maximum value each can attain is 1. Also each polynomial has atmost one peak(maximum). Is there some way that I can show ...
3
votes
1answer
240 views

If “force” is periodic does it imply “velocity” is periodic ? (or decoding tail-bited conv. codes)

I'll try to translate certain problem about convolutional codes to more common language of ODE, hope my translation is correct, but welcome to criticize. Consider two given functions periodic ...
1
vote
1answer
74 views

Numerical optimisation for multivariate Gaussians

Hi, I want to calculate $ f_{\mathbf x}(x_1,\ldots,x_k)\, = \frac{1}{(2\pi)^{k/2}|\boldsymbol\Sigma|^{1/2}} \exp\left(-\frac{1}{2}({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf ...
5
votes
0answers
138 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
2
votes
1answer
115 views

Rayleight Ritz Ratio and smallest eigenvalue for a set of given matrices

I am familiar with Rayleigh Ritz Ratio for hermitian matrices. Let $A_1$ be a given $N \times N$ hermitian matrix. Then the smallest eigenvalue of $A_1$ is given by \begin{align} ...
2
votes
1answer
192 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
5
votes
1answer
293 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 ...
0
votes
1answer
214 views

Is unconstrained integer convex optimization problem NP-hard?

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard? Thank you in ...
2
votes
1answer
603 views

Choice of Lipschitz constant for proximal gradient optimization

I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function $f(B) = \frac{1}{2}|| XB - Y||_F^2 + \frac{\gamma}{2}||B C^T||_F^2$, where $X \in ...
3
votes
0answers
154 views

An S-lemma for polynomials of degree 4 in three variables

Might the following be true: Let $p,q\in\mathbb{R}[x,y,z]$ be homogeneous polynomials, with $\deg(p)\leq 4$ and $\deg(q)= 2$. Suppose $q(x,y,z)>0$ for some $x,y,z\in\mathbb{R}$. Then the ...
5
votes
2answers
240 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 ...
0
votes
0answers
141 views

Stochastic optimal control with no diffusion

Classical stochastic optimal control problem is to minimize functional $$ J(u) = \mathbf E \int_0^T f(t,x_t,u_t)dt, \tag{1} $$ subject to SDE $$ dx_t = b(t,x_t,u_t)dt + \sigma(t,x_t,u_t)dW_t, \quad ...
1
vote
1answer
235 views

Can you maximize the spectral norm of a matrix in a semidefinite program?

Consider the following optimization problem: Maximize $||X||$, subject to $X$ being Hermitian (or symmetric, if you prefer) and a bunch of semidefinite constraints on $X$. I want to know if this can ...
2
votes
0answers
142 views

Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram

Suppose I'd like to distribute a set of points $P=\lbrace p_1 ,\dots, p_n \rbrace$ in the unit square $S=[0,1]\times[0,1]$ to minimize a weighted sum of two things: 1) The average distance between a ...
5
votes
2answers
248 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
1
vote
2answers
688 views

When do maximum and expectation commute?

Hi, I'm looking for conditions on $G(t,x)$ such that $$ \sup\limits_{t\in [0,1]}E[G(t,X)]=E[\sup\limits_{t\in [0,1]}G(t,X)] $$ where $X$ is a random variable (it's easy to see that $\sup\limits_{t\in ...
2
votes
2answers
99 views

Worst-case nearest-neighbor distances between regions

Suppose that $S_1,\dots,S_n$ is a collection of disjoint shapes in the plane, and let $\mathcal{X}$ denote the set of all $n$-tuples of points $\lbrace x_1,\dots,x_n\rbrace$ such that $x_i\in S_i$ for ...
0
votes
0answers
96 views

Reference Request (semidefinite relaxation)

Considering the semidefinite relaxation technique where a quadratic program is relaxed by the full-rank semidefinite programming. This is, $x^TQx$ now reads as Tr$(XQ)$ without any rank constraint in ...
2
votes
1answer
198 views

Best constant in a convex polynomial inequality.

Let $\phi(x)$ be a convex polynomial of degree $m$ at least two. Note that for $x,q \in \mathbb{R}$ $$\phi(x) + \phi(q) - 2\phi(\frac{x+q}{2}) = ...
6
votes
4answers
525 views

solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
5
votes
2answers
506 views

Gandhi's quote formalized [closed]

Hello, I hope this question is appropriate for Mathoverflow. Gandhi said, "Be the change that you wish to see in the world". I don't understand anything in Game/optimization theory (I don't know ...
0
votes
1answer
154 views

(probably simple) optimization question

Suppose you have a concave function defined over a non-polyhedral convex cone and you are interested in the infimum. What would be standard approaches to tackle the question? (The cone is actually PSD ...
1
vote
2answers
107 views

LP/QP with not-so-constant linear constaints

I have an otherwise standard LP or PSD QP problem as below: $\min\limits_x {c}' x$ subject to $Ax\leq b$ or $\min\limits_x \frac{1}{2}{x}' Qx + {c}' x$ subject to $Ax\leq b$ the only exception ...
2
votes
1answer
174 views

A Function with Exactly $k$ Minima in a Bounded Space

Is it possible to have a function with the following properties? (i) The function maps a bounded $n$-dimensional space $\mathcal{X}$ (say $\left[0,1\right]^n$) onto a bounded interval $\mathcal{Y}$ ...
1
vote
1answer
456 views

Solutions to Heat Equations with Obstacles!

Consider a closed Riemannian manifold $(M,g)$ and a positive function $\psi: M \to R$. Fix a point $p \in M$, I have been struggling to construct a solution to the heat equation, $\partial_t u = ...
4
votes
1answer
220 views

Minimizing action squared versus action

I have a very basic question in the calculus of variations: Suppose I want to minimize the functional $$A[r, r'] = \int_\Omega L(r, r') dx $$ When is it possible to say that extremals of $A$ agree ...
9
votes
1answer
3k views

“You can't push a rope”

"You can't push a rope" is a wisdom saying that some engineering teachers pass along to their students. Since I'm not an engineer, I can only guess at what they mean, but it sounds to me like code ...
4
votes
1answer
273 views

Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. Now my ...
4
votes
0answers
119 views

Convexified threshold of a function

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set. It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when ...
5
votes
1answer
216 views

A Lagrangian problem with a countable family of local extrema ?

Dear MO contributors, let $r > 0, L > 0$. I am interested in maximizing the integral: $$ \int_0^{2\pi} \frac{f(\alpha)^2 f'(\alpha)^2}{\sqrt{f(\alpha)^2 + f'(\alpha)^2}} \ \mathrm{d} \alpha $$ ...
0
votes
0answers
139 views

Differentiability of minimax objective function with respect to a decision variable

I have the following optimization problem: $$\text{find } x= \min_{a} \max_{\lambda\in\Lambda} |R(h\lambda)|$$ where $\Lambda$ is some finite, fixed set of complex numbers and $R(z)$ is a ...
2
votes
2answers
204 views

Equitable division of a contiguous resource

I have come across the following result regarding equitable division of a resource, which is a simple and immediate consequence of linear programming complementarity (in the infinite-dimensional ...
5
votes
1answer
251 views

Geometric applications of Ekeland's variational principle

I'm looking for geometric applications of Ekeland's variational principle in order to see it at work in a context I'm familiar with. Let me recall the principle itself: Definition. Let $(X,d)$ be a ...
11
votes
3answers
472 views

finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...
1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2
votes
2answers
311 views

My overdetermined linear system gives both bad and good estimates. Why ?

Hello to everyone. What the question means is that different ways of expressing the same relation between the data and unknown variables produce really weird fit results: The problem: I have the ...
0
votes
1answer
241 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
1answer
240 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
1answer
132 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
1answer
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 ...
25
votes
1answer
993 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
1answer
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
1answer
167 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
0answers
194 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
1answer
155 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
0answers
218 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
1answer
224 views

Constrained Optimization: Matrix Inverse in Objective/Constraints?

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