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

learn more… | top users | synonyms

3
votes
0answers
75 views

existence of optimal control

I'm looking for an existential result in optimal control for the following class of problems: Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times ...
1
vote
0answers
24 views

Minimizing sum of functions, while keeping their values non-negative

Suppose we have data $\mathbf{x}_i$, $i\in \{1, \ldots, K\}$, and we're trying to find parameters $\hat{\mathbf{\theta}}$ such that $$\hat{\mathbf{\theta}} = \underset{\mathbf{\theta}} ...
0
votes
0answers
44 views

Dimension of a trajectory in $\mathfrak{su}(n)$

Consider $a,b \in \mathfrak{su}(n)$, a fixed positive real number $t$ and the equation: $\frac{d U(s,t)}{ds} = \left(a + \omega(s)b \right) U(s, t)$ (where $U(t,t)=I$) and the definition: $B(s) = ...
10
votes
0answers
104 views

Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
0
votes
1answer
189 views

A problem about a matrix norm on $\mathfrak{su}(4)$

Given a fixed $B \in \mathfrak{su}(4)$ is it possible to solve for $F$: $\sigma^{\text{max}}\left(\frac{A}{F(A)} + B \right) = 1$, $\forall A \in \mathfrak{su}(4)$. A theorem in ...
1
vote
0answers
62 views

Minimize Product of Sums of Squared Distances

The Question Given two sets of vectors $S_1$ and $S_2$,we want to find a unit vector $s$ such that $$\{\sum_{u\in S_1}(\|u\|^2-\langle u, s \rangle^2)\} \cdot \{\sum_{v\in S_2}(\|v\|^2 - \langle v, ...
34
votes
1answer
2k 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 ...
0
votes
1answer
238 views

Supremum in a Markov chain model

A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach ...
4
votes
3answers
532 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 ...
5
votes
0answers
51 views

Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...
0
votes
0answers
17 views

Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
5
votes
1answer
152 views

The Maximal $\ell_2$ norm of a signed sum of vectors

Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors: $$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$ where $s_j$'s can only take values of $+1$ or $-1.$ I ...
3
votes
1answer
61 views

Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...
11
votes
8answers
2k views

How do I approach Optimal Control?

Other than learning basic calculus, I don't really have an advanced background. I was curious to learn about Optimal Control (the theory that involves, bang-bang, Potryagin's Maximum Principle etc.) ...
6
votes
3answers
613 views

Some questions about Invexity

Recently, I am looking into a non-convex optimization problem whose points satisfying KKT conditions can be obtained. Then the problem becomes how to decide whether the KKT conditions are sufficient ...
2
votes
0answers
117 views

Fixed area, largest mass — is there a name?

Let $x\in \mathbb{R}^n$ and let $s_k(x)$ denote the sum of the $k$ largest entries of $x$. The function $s_k(x)$ is well-known to be convex and is often used in optimization, such as ...
0
votes
1answer
84 views

How to minimize this sparse quadratic function?

There is a problem when I'm reading a paper. Equation: $min_p|p-p^*|^2+\alpha |R(p)|^2 + \beta |D(p)-\delta|^2$, where $p, p^*, R(p), D(p), \delta$ are all $M\times N$ matrices, and $p^*, R(), D(), ...
1
vote
1answer
71 views

What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
2answers
98 views

Why the 'S' in S-procedure/S-lemma?

The S-procedure (also called as S-lemma) is a technique from V. A. Yakubovich that is used to relax a system of quadratic inequalities to a linear matrix inequality problem. It is used largely in ...
1
vote
1answer
45 views

characterization of a certain closed convex cone

Consider $x_1,\cdots,x_n \in \mathbb{R}^d$, and the closed convex cone in $\mathbb{R}^n$ defined by $$\mathcal{K}(\underline{x}):=\{(\varphi(x_1),\cdots,\varphi(x_n)):\varphi \textrm{ convex on ...
0
votes
0answers
39 views

Projected Alternating Minimization

Assume that $f(x,y)$ is a non-convex function for $x,y\in \mathbb{R}$. Assume that we want to minimize this function (even locally) with respect to $x$ and $y$ such that $x \in \mathcal{X}$ and $y \in ...
1
vote
0answers
31 views

Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...
2
votes
1answer
163 views

Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...
2
votes
2answers
257 views

Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation: $X=c \cdot AXA' - diag(c \cdot AXA')+ I$, where (1) $A \in R^{n \times n}$ is a given matrix whose element ...
1
vote
0answers
39 views

Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that $$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$ It is called a controlled Markov process. Now, suppose there exist $\epsilon_0$, ...
3
votes
3answers
3k views

Maximum flow with negative capacities?

I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
3
votes
1answer
407 views

Do upper-semicontinuous polyhedral multifunctions have Lipschitz continuous selections?

We are interested in the following question (definitions and references are given below): Main Question: Given an upper-semicontinuous polyhedral multifunction $F:R^n \rightarrow R^m$, is there ...
1
vote
1answer
770 views

Maximizing linear objective function with absolute values

This has be asked on other forums, though couldn't find authoritative answer. I have a linear program over the reals and don't want to introduce integer or binary variables. The objective function ...
0
votes
1answer
572 views

eigen-decomposition solution? is it unique?

Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
3
votes
0answers
101 views

Copositivity in matrix pencils

Given two square symmetric matrices $A,B$ of the same order, the matrix pencil $P(A,B)$ is the set of linear combinations of $A$ and $B$. Finsler's theorem gives an elegant criterion for $P(A,B)$ to ...
2
votes
1answer
974 views

Choice of Lipschitz constant for proximal gradient optimization

I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function $f(B) = \frac{1}{2}|| XB - Y||_F^2 + \frac{\gamma}{2}||B C^T||_F^2$, where $X \in ...
3
votes
1answer
108 views

A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
1
vote
1answer
158 views

finding permutation matrix I which minimizes TRACE( I* C*( I^T)* D) matrix

I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case... thanks for your help in advance I want to find permutation ...
3
votes
1answer
1k views

Matrix approximation

Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where ...
2
votes
2answers
2k views

Best fit for multiple shapes inside an area

Is there a forumla to come up with the best fit for multiple shapes inside a rectangular area, so that none of the shapes are overlapping?
1
vote
2answers
225 views

how to estimate a polyhedron(convex hull) classifier from data sample

Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron. $min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$ ...
4
votes
1answer
160 views

Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem. Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that $$ \| D_1 A ...
26
votes
3answers
1k views

What is the best way to peel fruit?

A mango made me wonder about this. (See also this question, which is in a similar spirit.) Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset ...
7
votes
2answers
200 views

Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...
2
votes
1answer
89 views

Standard names and methods for this type of fitting minimization

In material science research, we have come across the following type of problem. Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization $$\eqalign{ ...
3
votes
0answers
97 views

This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by ...
2
votes
0answers
88 views

Copositivity under tensor products

Is there any symmetric real matrix $A$ such that $A^{\otimes n}$ is copositive for all positive integers $n$, but such that A is neither positive semidefinite nor has just non-negative entries? ...
0
votes
1answer
73 views

Sufficient and necessary condition for BIBO stability

I am looking for a reference for the proof of the next claim: "BIBO—bounded input bounded output—stability. We claim that a necessary and sufficient condition for a system described by a linear, ...
23
votes
6answers
11k views

Is all non-convex optimization heuristic?

Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...
0
votes
0answers
46 views

numerical solver for stochastic optimal control problems

can any one recommend numerical solver (c/c++ library preferred) for stochastic optimal control problems? For deterministic optimal control I found something like that: ...
5
votes
2answers
640 views

Problem equivalent to “largest square in a cube”

The "largest square in a cube" problem, which asks for the largest square inside a cube, has a solution as can be seen on this page, which also says that the general problem in higher dimensions is ...
4
votes
2answers
232 views

Riemannian metric on a space of “not-quite-smooth” (hyper)surfaces?

Apologies if the title's a bit vague; I'll try to explain everything below, and please let me know if I should clarify anything. I've been looking for a while at variational problems on polytopes. ...
5
votes
2answers
340 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
7
votes
2answers
429 views

How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it. Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...
3
votes
0answers
82 views

Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...