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

learn more… | top users | synonyms

1
vote
2answers
108 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
175 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
474 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
277 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
126 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
222 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
140 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
208 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
265 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
481 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
2k 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
322 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
243 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
247 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
136 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
134 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 ...
28
votes
1answer
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
1answer
233 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
171 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
197 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
160 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
242 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
228 views

Constrained Optimization: Matrix Inverse in Objective/Constraints?

Made a crucial mistake in the problem formulation; please delete.
7
votes
2answers
401 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
1answer
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
1answer
229 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
2answers
376 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
3answers
894 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
2answers
350 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
0answers
148 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
1answer
134 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
1answer
335 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
0answers
221 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
5answers
3k 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
1answer
230 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
1answer
278 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
1answer
378 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
1answer
143 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?
6
votes
5answers
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
1answer
200 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
1answer
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
2answers
658 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
0answers
126 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
1answer
131 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
2answers
322 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
1answer
276 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
1answer
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
4answers
871 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 ...