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

learn more… | top users | synonyms

0
votes
1answer
224 views

Constrained Optimization: Matrix Inverse in Objective/Constraints?

Made a crucial mistake in the problem formulation; please delete.
7
votes
2answers
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
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
222 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
332 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
810 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
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
0answers
145 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
123 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
298 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
216 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 ...
5
votes
5answers
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
1answer
217 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
255 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
364 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
136 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
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
193 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
598 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
122 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
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
2answers
315 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
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
1answer
199 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
818 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
1answer
323 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
0answers
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
1answer
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
3answers
601 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
2answers
245 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
0answers
158 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
1answer
186 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
0answers
86 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
1answer
326 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
1answer
241 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
2answers
235 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
0answers
121 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
1answer
261 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
2answers
225 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 ...
1
vote
1answer
185 views

Proving a variational problem has no solutions

Consider the following integral $ \int_{0}^{\frac{\pi}{2}} \left( \sqrt{y(x)^2 + y'(x)^2} \left( \ln \left( \frac{\sin(x)}{1 -\cos(x)} \right) + \frac{\pi}{2} \right) + \frac{\pi}{2} y'(x) + 1 ...
3
votes
0answers
218 views

Maximise $L^q$ norm of a vector, for fixed $L^1$ and fixed $L^p$ norms [closed]

Consider a vector $x \in \mathbb R_+^n$ and $p,q \in \mathbb R$ such that $1 < p < q$ We fix $\sum \limits_{i=1}^{n}|x_i| = 1$ and $ \left(\sum \limits_{i=1}^{n}|x_i|^p \right)^\frac{1}{p} = ...
1
vote
1answer
249 views

Minimizing ellipsoid over intersection of ellipsoids

Let's say I want to minimize a quadratic form $\sum_{j=1}^n c_jx_j^2$ (all $c_j$ are positive constants), which corresponds to an $n$ dimensional ellipsoid, over the outer part of the intersection of ...
2
votes
0answers
297 views

Partial feedback linearization (Control theory)

Greetings, I'm trying to understand a theorem about partial feedback linearization from a paper "On the largest feedback linearizable subsystem" by R.Marino (you can find it here: ...
1
vote
1answer
93 views

Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?

Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming. A famous application of semidefinite ...
2
votes
0answers
79 views

Minimum time planar paths under a bound on magnitude of acceleration

On a plane, given initial position (x1,y1), initial velocity (u1,v1), final position (x2,y2), and final velocity (u2,v2), compute the solution to x''= cos(z), y''=sin(z) that has these endpoint ...
1
vote
2answers
165 views

Bound on expression from probability distributions

I came across this issue while trying to combine multiple probability distributions into a single distribution which approximates them all simultaneously. This boils down to maximizing this expression ...
0
votes
1answer
114 views

Conditions under which a given scheme converges

I'm sorry in advance for how long this question is. Suppose I have a continuous function $f:\mathbb{R}^n \rightarrow \Delta_{n-1}$, where we think of the simplex $\Delta_{n-1}$ as the set ...
2
votes
1answer
611 views

Projection exists => Uniformly convex?

Hello, I know that: Let X be a uniformly convex Banach-Space, $a\in X$ and $C\subset X$ closed and convex, then there is a unique $b\in C$ with $\left\Vert a-b\right\Vert=\inf_{x\in C}\left\Vert a-x ...
1
vote
1answer
162 views

Conditions ensuring extrema are twice continuously differentiable?

For a functional $J[y]=\int_{a}^{b}F(t,y,y')dt$, are there any conditions that ensure extrema over the class of piecewise continuously differentiable functions are all in $C^2[a,b]$?