**2**

votes

**1**answer

387 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

**0**answers

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

**2**answers

479 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

**2**answers

665 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

**1**answer

514 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

**1**answer

226 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

**0**answers

205 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

**1**answer

649 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

**1**answer

263 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

**0**answers

116 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

**1**answer

316 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

**1**answer

290 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

**2**answers

701 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

**1**answer

239 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

**0**answers

403 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

**1**answer

661 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

**2**answers

400 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

**2**answers

913 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

**3**answers

630 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

**1**answer

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

**1**answer

322 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

**3**answers

644 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

**1**answer

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

**1**answer

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

**1**answer

267 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

**1**answer

401 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

**1**answer

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

**1**answer

274 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

**2**answers

481 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

**2**answers

427 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

**1**answer

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

**2**answers

499 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

**0**answers

365 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

**2**answers

414 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

**2**answers

779 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

**2**answers

504 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

**2**answers

349 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

**1**answer

615 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

**3**answers

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

**2**answers

383 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

**2**answers

135 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

**3**answers

643 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

**1**answer

315 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

**1**answer

747 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

**2**answers

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

**2**answers

585 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

**1**answer

331 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

**2**answers

460 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

**0**answers

83 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

**3**answers

431 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 ...