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

learn more… | top users | synonyms

2
votes
1answer
606 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
386 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
907 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 ...
3
votes
3answers
603 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
318 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
601 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
250 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
264 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
362 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
235 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
273 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
476 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
425 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
228 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
490 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
354 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
409 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
728 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
455 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
345 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
602 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
382 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 ...
0
votes
2answers
132 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
5
votes
3answers
629 views

SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
1
vote
1answer
312 views

Has anybody ever seen something like this (optimization problem / variational calculus)

Hi all, I'm trying to minimize the following integral : $ \int_{0}^{\pi/2} \frac{\int_{0}^{x} \sqrt{r(\theta)^2 + r'(\theta)^2}d\theta}{\sin(x)} dx $ with boundary values r(0)=1 and r(pi/2)=0. As ...
2
votes
1answer
722 views

solving multiple linear programming problems with the same set of constraints

Hi, I need to solve a set of linear programs of the form: Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$. The $c_i$'s are different vectors so each problem has a different objective ...
1
vote
2answers
1k views

Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
-1
votes
2answers
556 views

Optimal tax Rate

Assume you have two countries A and B, with a tax rates $T_A$ and $T_B$. The tax is redistributed to each people equally. Hence if you live in A and you make $I$ as income then you will finally ...
2
votes
1answer
326 views

Feasible space of SDP

Typically the non-empty feasible space of a SDP has some curved boundary which is why the feasible space has infinitely many extreme points. Is it ever possible to have a SDP whose non-empty feasible ...
2
votes
2answers
453 views

cayley transform for non-square matrices

Hi, I am optimizing a function over a matrix $U$, where $U \in \mathbb{R}^{m \times n}$ and $U^TU = I$. I do not want to run a constrained maximization program, since employing the constraint $U^TU = ...
0
votes
0answers
79 views

interdependence of decision variables

Dear all, its quite clearly stated that independence of decision variables are necessary for solving optimization problems using the simplex method. Is this a requirement for all linear ...
1
vote
3answers
428 views

convergence in distribution of stochastic gradient descent.

The stochastic gradient descent algorithm where only a noisy gradient (zero mean noise) is used to update current estimate is known to converge almost surely to the minimizer. However, if one is ...
8
votes
2answers
337 views

An extension of Gaussian Isoperimetry

The Gaussian isoperimetric inequality (Tsirelson,Sudakov, Borell) states that among all sets of given Gaussian measure in the n-dimensional Euclidean space, half-spaces have the minimal Gaussian ...
6
votes
1answer
329 views

Nilpotent Lie algebras of vector fields

Let $L$ be a finite-dimensional nilpotent subalgebra of the Lie algebra $W_n$ of all vector fields in $n$ variables (I am interested both in polynomial and formal vector fields). Does there exist a ...
2
votes
1answer
208 views

Maximum distance of points in intersection of balls

Dear all, let $B_\delta(p):=\{x\in\mathbb{R}^d:||x-p||_2\leq \delta\}$ be a $d$-dimensional closed ball. Now I do not have one ball, but four: $B_{r_1}(p)$, $B_{r_2}(p)$, $B_{s_1}(q)$ and ...
1
vote
1answer
810 views

Prove two optimization problems are equivalent

Hello! Let $x_1\ge x_2\ge ... \ge x_n>0$. Here are two optimization problems: P1: Maximize $\Pi _{i=1}^n x_i$ subject to $\sum _{i=1}^n x_i =K$. P2: Minimize $\sum _{i=1}^n (x_i-K/n)^2$. As ...
2
votes
0answers
489 views

The marriage problem on NBC's “The Voice”

I'm a long time lurker here just never got around to registering so excuse the lack of reputation points. So most people here are aware of the marriage problem: You're given a known number of ...
0
votes
2answers
539 views

Converting (or approximating) a non-differentiable function to a differentiable function

Hello, I have the following function form as one of my constraints : f(x) = MIN(0, x) Because of the MIN, it is non-differentiable. As I would like to use an optimizer that uses derivative based ...
1
vote
0answers
229 views

The importance of weakly Pareto optimal points

In multicriteria optimization problems appart from the notion of Pareto optimality there is also the term weakly Pareto optimality. For that case, the definition is that A feasible solution $\hat{x} ...
1
vote
0answers
278 views

Timber sawing (maximum number of given rectangles in a circle) [closed]

Hello, I am trying to make a software for a sawmill. I have a list of boards that I will have to obtain and the diameter of the log that I have to cut. The algorithm is relatively simple. I try ...
3
votes
3answers
745 views

Minimum norm of convex hull

Dear all, I am currently stuck at a problem which seems too easy to be stuck at to me... Summary Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute ...
1
vote
1answer
2k views

Matrix optimization problem

This is (probably) an easy one: Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$. Looking for how to find X, ...
2
votes
3answers
561 views

Decomposing a discrete signal into a sum of rectangle functions

Hello mathoverflow community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
1
vote
1answer
110 views

constructing a positive definite basis

Hello, If I have a matrix A, is it possible to construct a positive definite matrix M with the same range as range(A')? I am trying to use the property x'Mx > 0 to remove an absolute value constraint ...
1
vote
1answer
476 views

Split sum into equal terms

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$. Find indices $1 < p_1 <...< p_h <...< p_{t-1} < l$ such that in sum ...
3
votes
1answer
618 views

An optimization problem in numerical linear algebra

Provided two diagonal real matrix which has positive entries, $V$ and $U$. Find a real matrix $A$, satisfying $A^TA=a^2I$ for some scalar $a$, to minimise $\left|A^TVA-U\right|\quad\quad(*)$ ...
3
votes
2answers
453 views

A lower bound of a particular convex function

Hello, I suspect this reduces to a homework problem, but I've been a bit hung up on it for the last few hours. I'm trying to minimize the (convex) function $f(x) = 1/x + ax + bx^2$ , where ...