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

learn more… | top users | synonyms

3
votes
0answers
219 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
250 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
305 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
618 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]$?
4
votes
1answer
439 views

An optimization problem involving sum of binomial coefficients upto some value

I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note ...
2
votes
1answer
393 views

minimizing functions over simple matrix inequalities

I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example: $min \Sigma x_i ln ...
4
votes
0answers
160 views

Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l \rangle −f_1(x)−f_2(x)$ via convex duality?

I am attempting to solve the argument maximization problem $$\arg\sup_x \{ \langle x,l \rangle − f_1(x)−f_2(x) \} \ \ \ \ \ \ \ \ \ \ (1)$$ where the functions $f_1$ and $f_2$ are concave but ...
4
votes
2answers
482 views

Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
1
vote
2answers
677 views

How to use DFT to solve this minimization problem?

This is a problem when I'm reading a paper. Equation: $min\{\sum_p(S_p-I_p)^2+\beta((\partial_xS_p-h_p)^2+(\partial_yS_p-v_p)^2) \} $ where $S,I,h,v$ are all $M*N$ matrices and p stands for every ...
10
votes
1answer
520 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
3
votes
1answer
227 views

Unique matrix satisfying a system of equations

Assume I have a $n\times n$ positive semidefinite matrix $G$ of rank $p$ satisfying a set of $np - p(p-1)/2$ equations $v^T_jGv_j = 1$, $j = 1 \ldots np - p(p-1)/2$ for some given vectors $v_j$. It is ...
0
votes
0answers
207 views

L1-regularized Least Squares on a matrix with Toeplitz Blocks (not block-Toeplitz)

I am trying to speed up a sparse signal recovery algorithms. My sensing matrix is a set of Toeplitz Blocks, M = [T1,T2,T3,...,Tk] The objective is min ||Mx - b||_2^2 + ||x||1 What I'm actually ...
4
votes
1answer
668 views

Maximize sum of largest eigenvalues

Consider the following optimization problem: $\max_{\lambda_j(X)}\sum_{j=1}^n d_j\lambda_j(X)$ subject to $v_j^TXv_j \leq 1, X \geq 0$. $d_j$ are such that $d_1 \geq d_2 \geq \ldots \geq d_k > ...
6
votes
1answer
268 views

Constructing a hypersurface with given outer normals

Pick a point on each of the positive half-axes in $\mathbb{R}^n$. Put a (unit-norm?) vector at each of the n points. (a) Is there a hypersurface in the orthant $\mathbb{R}^n_+$ going through these n ...
1
vote
0answers
117 views

Minimizing an entropylike expression with a quadratic constraint

Let '$\{X_i\}$' be a set of n positive integers, and fix k to be a positive integer. I am interested in finding the set of solutions to the pair of inequalities: '$\displaystyle \sum_{i=1}^n X_i ...
3
votes
1answer
317 views

Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ...
0
votes
1answer
318 views

Nonlinear constraint and product of variables

I have been asked to add to an existing linear programming model several constraints dealing with ratios among continuous decision variables. An example ratio constraint would be like: $x_1*x_2 - ...
1
vote
2answers
734 views

Quadratic problem solving with absolute value constraint

Hello, I have been trying to solve a problem of the form : $\max_x\quad -\tfrac{1}{2}x^TAx + b^Tx - C\sum_i |x_i|$ without the C term it is a simple quadratic problem, but I haven't been able to ...
2
votes
1answer
243 views

Linear and Isometric Automorphism Groups of the PSD Cone

Let $S_+$ be the cone of psd matrices ($n\times n$ real symmetric positive semidefinite matrices). This cone is a metric space induced from the inner product $\langle A,B\rangle = tr (AB)=tr(BA)$. ...
0
votes
0answers
406 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where ...
2
votes
1answer
702 views

How do I optimize over (or take derivative wrt) a square diagonal matrix?

Hello. I'd like to solve the following optimization problem. $P_i$ is a 6x6 matrix $X$, $Y$ is a 6xk matrix $w_i$ is a kx1 vector $diag(w_i)$ is a square diagonal matrix with diagonal entries equal ...
3
votes
2answers
408 views

Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions?

The cone of symmetric positive semidefinite $n\times n$ matrices is the convex hull of rank $1$ matrices. That is, every symmetric positive semidefinite matrix is a convex combination of rank 1 ...
13
votes
2answers
914 views

Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
4
votes
3answers
646 views

Schur complement and “negative definite”!

Hi I have the following problem. Let the symmetric matrix M of the form: \begin{bmatrix} A & B \newline B^T & C \newline \end{bmatrix} We have that $C$ is positive semidefinite. Is ...
1
vote
1answer
154 views

Max Absolute Difference of Expectations under Change of Measure

Given a sample space $\Omega=\{ 1,\cdots,N \}$, a random variable $x$ defined on $\Omega$ that takes value $x_1,\cdots,x_N$, and a set of strictly positive real numbers $w_1,\cdots,w_N$. Define for ...
5
votes
1answer
324 views

Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently

What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$? Do we have to calculate $A^{-1}b$, or is this not necessary? edit: I forgot to mention that A is symmetric and ...
2
votes
3answers
666 views

Maximizing the minimum of piecewise linear functions in high dimensional space

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + \|x - b_i\|_\infty$. where $a_i,\ldots, a_n \in \mathbb R$ and $b_1,\ldots,b_n \in [0,1]^{21}$ are fixed, $x \in [0,1]^{21}$, ...
3
votes
1answer
2k views

Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$. where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$. Can this be solved with a linear ...
2
votes
1answer
251 views

Maximum-bend TSP

I've seen minimum-bend TSP studied, has anyone looked at max-bend TSP? As a special case, I'm interested in the maximum number of turns a hamiltonian path can take in an $n \times n$ square grid. I ...
2
votes
1answer
270 views

Point-wise error estimate in polynomial regression

In our application we wish to estimate the actual path of objects. We have a set of samples of object locations $(t_i, x_i, y_i, P_i)$ where $t_i$ is the sample time, $(x_i, y_i)$ is the 2D location, ...
6
votes
1answer
413 views

Eigenspace of Euclidean distance matrix.

What is the necessary and sufficient condition (if there is any) that $n$ orthonormal vectors $v_1,v_2,\cdots,v_n$ are eigenvectors of a Euclidean distance matrix. When $n=2$, the orthonormal ...
0
votes
1answer
238 views

Is this a Karusch-Kuhn-Tucker method or something else? [closed]

This is a question that originated with World of Warcraft. I have a solution, but I don't know where to look up other problems of the same kind for a better explanation. There is a plane with p axis ...
0
votes
1answer
276 views

Infinite dimensional optimization

Assume that we optimize a convex problem (convex objective and linear constraint) over a set of functions (say $L2$). Consider now the same optimization problem (same objective and same linear ...
3
votes
2answers
486 views

Cubic graphs which are “difficult to navigate”

Suppose I am inside a finite, weighted cubic graph without loops, with no information regarding its layout, including the number of vertices or distances to the adjacent vertices. I want to reach a ...
2
votes
2answers
430 views

How can I simplify this quadratic optimization?

I have no experience in the field of optimization, so I have no idea how hard or naive it is. I got no response on math.stackexchange so I am posting it here, though I doubt it is research-level. ...
1
vote
1answer
232 views

How to get constraint qualifications conditions for optimization on banach spaces

From the book of bertesekas(1999),borwein(2006), we learned some constraint qualifications on R^n spaces,such as: Linear independence constraint qualification(1951) Mangasarian–Fromovitz constraint ...
5
votes
2answers
501 views

Is there a name for this type of matrix? (Reference Request)

I am working on a problem were I encounter matrices of the form $X = \begin{bmatrix}\frac{1}{1 - a_ib_j}\end{bmatrix}_{ij}$ I am aware of Cauchy matrices, which have the form $X = ...
0
votes
0answers
382 views

Combining Convex and Concave in CVX

Hello, I have an unconstrained optimization in which I need to minimize a sum of convex functions and maximize a concave function together. I combined both the problem by adding a minus sign to the ...
5
votes
2answers
416 views

Maximize the intersection of a n-dimensional sphere and an ellipsoid.

I have the conjecture that the volume of the intersection between an $n$-dim sphere (of radius $r$) and an ellipsoid (with one semi-axis larger than $r$) is maximized when the two are concentric, but ...
6
votes
2answers
806 views

Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
1
vote
2answers
517 views

Problems finding feasible points with respect to linear matrix inequalty constraints

Hi! I'm a trying to learn the basics of semidefinite programming and how to solve problems with linear matrix inequalities. Inspired by the book "Convex Optimization" by Boyd and Vandenberghe (can be ...
6
votes
2answers
352 views

The odd power of copositive matrix

If $A$ is copositive, what about $A^3$? Is it also copositive? More generally, my question is whether the odd power of a copositive matrix is still copositive. Any reference is appreciated
3
votes
1answer
620 views

maximization of a quadratic function with a quadratic constraint

I have the following quadratic maximization problem $\max_{\mathbf X} \quad tr(\mathbf A\mathbf X\mathbf B\mathbf X^H)+tr(\mathbf C\mathbf X)+tr(\mathbf C^H\mathbf X^H)$ subject to the quadratic ...
4
votes
3answers
2k views

Minimize trace of inverse of convex combination of matrices.

Hello! (First question--please forgive me if its unclear.) I am interested in efficient/approximate optimization techniques for minimizing a norm of a convex combination of symmetric, positive ...
1
vote
2answers
389 views

Optimizing directly on the eigenspectrum of a matrix

I have an application where I want to the eigenvalues of the graph to be involved in the objective and constraints in a flexible way (moreso than just the nuclear or frobenius norm). Whats a good ...