# Questions tagged [oc.optimization-and-control]

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

971
questions

**2**

votes

**0**answers

95 views

### Maximizing the distance sum of some points inside a circle

Consider $n$ points $\{p_i\}_{i=1}^n$ located inside or on a circle with radius $r$ in the plane. The question is: how to place the $n$ points so that the sum of inter-point distances,
$$J=\sum_{i=1}^...

**0**

votes

**1**answer

39 views

### Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...

**1**

vote

**0**answers

31 views

### Producing a minimiser for the Kantorovich problem from a minimiser of the Beckmann flow problem

Notation: We denote by $\mathcal M$ the set of vector valued measures on $\mathbb R^d$ whose divergence is a scalar measure (in the weak sense).
Definitions: Consider the Beckmann flow minimisation ...

**1**

vote

**1**answer

215 views

### Facility location on manifolds

Facility location studies optimal placement of a certain number $n$ of points (facilities) in some region $R$. (https://en.wikipedia.org/wiki/Facility_location_problem)
The minimax facility location ...

**0**

votes

**2**answers

353 views

### mathematics around ranking [closed]

Is there interesting mathematics around ranking? (I mean ranking as reputation points here at mathoverflow.)
It looks obvious that there is no way to make adequate ranking --- is it a theorem, at ...

**0**

votes

**0**answers

34 views

### maximize quadratic form with respect to cov matrix of multinomial and linear constraint

Given $x_{m,1}, T$, how to solve
$\max_{y} x^T(\mathop{\mathrm{diag}}(p)-pp^T)x$, s.t. $p = Ty, \textbf{1}^Ty=1$
The dimensions are $p_{m,1}, y_{n,1}, T_{m,n}$ and $T$ is a transition matrix ...

**1**

vote

**0**answers

17 views

### Are such assumptions of functions similar to strong convexity reasonable in convex optimization?

For $\mu$-strongly convex function $f:\mathbb{R}^d\to\mathbb{R}$, the following property holds: for any given $x,y\in\mathbb{R}^d$, we have
$$
(\nabla f(x) - \nabla f(y))^\top(x-y) \ge \mu \|x-y\|^2.$$...

**2**

votes

**1**answer

77 views

### Routh-Hurwitz criterion for matrices

The Routh-Hurwitz criterion explicitly specifies a finite set of inequalities on the coefficients of a polynomial, necessary and sufficient that all zeros lie in the unit circle or in the left half ...

**15**

votes

**2**answers

621 views

### n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...

**0**

votes

**1**answer

119 views

### Localizing the intersections of cubics

For Hermitian matrices $A,B \in \mathbb{C}^{n \times n}$, can one readily compute a set of cones that separate the maxima of $$\frac{x'Ax}{x'Bx}$$ among $x$ with unit-norm components?
i.e. where do ...

**5**

votes

**0**answers

150 views

### Optimal configurations on the flat torus

I'm studying (with my colleagues R.Piergallini and S.Isola) configurations of points on the flat torus which minimize an attractive or repulsive potential depending on the distance, in the flat metric ...

**1**

vote

**0**answers

24 views

### Identify input maps corresponding to control system ($A,B$), where $B = \delta_0$

The text I'm struggling with comes from "Observation and Control for Operator Semigroups" by Tucsnak and Weiss, page 119.
Take $X = L^2(0,\infty)$ and let $X_{-1}$ be the dual of the Sobolev ...

**2**

votes

**0**answers

92 views

### Condition under which the Clarke's subdifferential is locally Lipschitzian

Given a locally Lipschitz continuous function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ and closed set $$\Omega =\left\lbrace x \in\mathbb{R}^n \ |\ f(x) \leq 0 \right\rbrace$$ such that f is semi-...

**0**

votes

**1**answer

27 views

### What's the meaning of this in equality in the lot-sizing and scheduling problem

I learned about the MILP models proposed by Pochet and Wolsey. Here are the formulations of one of these models(MILP3).
So the decision variables and the primary formulation are as following:
Based ...

**0**

votes

**0**answers

49 views

### Bounds on the lengths of circuits in a metric space

Given a collection $V$ of $N$ points in a metric space $(M, d)$, I define a circuit as a sequence $w = (w_1, w_2, ..., w_N)$ which visits each point in $V$ and has a length given by
$$|w| = \sum_{i=1}^...

**0**

votes

**1**answer

70 views

### Is there a specific name for this optimization problem?

Let $A$ be an $n\times n$ symmetric positive definite matrix with eigenvalues and eigenvectors $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n>0$ and $v_1,v_2,\cdots,v_n$ respectively.
We know that the ...

**2**

votes

**0**answers

53 views

### Lagrangian multipliers and a variant of Newton's method

A variant of Newton's method for solving the equality constrained problem
\begin{equation}
\begin{array}{ll}
\min &f(x) \\
\text{s.t.} & h(x) = 0
\end{array}
\end{equation}
is as follows:
\...

**1**

vote

**0**answers

35 views

### Deployment and dispersion in triangular regions

Definitions (from C. Stanley Ogilvy's 'Tomorrow's Math'):
Deployment: To place a specified number $n$ of points (stations) in a region such that the maximum distance of any point in the region from ...

**0**

votes

**0**answers

30 views

### Karush-Kuhn-Tucker in discrete time dynamic optimization

I need to solve the following problem:
$\max_{p_t\in [\phi_1(s_t),\phi_2(s_t)]} \sum_{t=0}^\infty p_t\times(a+\alpha s_t-p_t)$, subject to $s_0$ given and $s_{t+1}=\beta(s_t+\eta(a+\alpha s_t-p_t))$.
...

**1**

vote

**0**answers

25 views

### Is there an efficient way to do semidefinite programming with a Lyapunov equation constraint?

I am trying to numerically solve semidefinite programs of the form
$$\begin{array}{ll} \underset{X,Y}{\text{minimize}} & \operatorname{tr}(AX)\\ \text{subject to} & BY + YB = X\\ & X, Y \...

**1**

vote

**1**answer

50 views

### Optimality gap between a joint linear program and decoupled sub programs

Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...

**1**

vote

**0**answers

64 views

### Algorithm for deciding feasibility of linear programs [closed]

Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...

**4**

votes

**1**answer

65 views

### Do Pareto critical points of a multicriteria optimization problem form an attractor of the dynamical system induced by a descent algorithm?

Let $d\in\mathbb N$, $k\in\mathbb N$ and $f:\mathbb R^d\to\mathbb R^k$ be differentiable. Say that $v\in\mathbb R^d$ is a descent direction at $x\in\mathbb R^d$ if ${\rm D}f(x)v<0$ (component-wise) ...

**3**

votes

**0**answers

89 views

### Best approximation of piecewise constant function by Lipschitz functions

Let $f=\sum_{n=1}^N k_n I_{E_n}$ where $E_n$ are Borel subsets of $\mathbb{R}^n$ and $k_n\in \mathbb{R}^m$ with non-negative entries, and let $\mu$ be a finite Borel measure on $\mathbb{R}^n$. What ...

**0**

votes

**0**answers

107 views

### Maximizing a piecewise-linear convex function

Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...

**1**

vote

**1**answer

34 views

### Relation of 1-trees to optimal tours

Question:
given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...

**0**

votes

**0**answers

25 views

### Norm of vector components optimization of linear matrix combination

Given complex matrices $A_1, A_2, \dots, A_k\in\mathbb{C}^{m \times n}$, $B \in\mathbb{R}^{m \times n}$, the objective is to find a vector $x \in \mathbb{C}^k$ such that:
$\max {||x_i||}$ , $i\in 1,2.....

**0**

votes

**1**answer

114 views

### What to call a function that is negative on a set

Let $Y$ be a nonempty region in $\mathbb{R}^n$. I am designing an algorithm which given a point $x_0$ outside $Y$ in a finite number of steps lead to a point $x_n∈ Y$. The way I do it is that I have a ...

**1**

vote

**0**answers

40 views

### Conjugate gradient and the eigenvectors corresponding to the large eigenvalues [closed]

I am working on an optimization problem (for example, conjugate gradient) to solve $Ax=b$, where $A$ is a symmetric positive definite matrix. I can understand that the CG (conjugate gradient) has ...

**0**

votes

**2**answers

100 views

### Matrix norm minimization and matrix inner product

One of the famous problem in SDP is the matrix norm minimization (see S. Boyd, Convex Optimization, p. 170).
Consider:
\begin{equation}\label{eq:Lasse}
\begin{aligned}
&\min_{\mathbf{x}}
& &...

**2**

votes

**1**answer

49 views

### Link between exact null controllability of two systems

Let $A: D(A) \subset H \rightarrow H$ generate a strongly continuous semigroup $T(t)$ on a Hilbert space $H$ and $B\in \mathcal{B}(H)$. Consider the two control systems:
$$(1)\; x'(t)=Ax(t)+ Bu(t) \...

**4**

votes

**0**answers

71 views

### Minimizing the largest eigenvalue of matrix product

Let $A\in\mathbb{C}^{m\times n}$, $B\in\mathbb{C}^{n\times k}$, $C\in\mathbb{C}^{k\times m}$ be given complex matrices. The objective of the optimization problem is
\begin{equation}
\mathop {\arg \min ...

**0**

votes

**1**answer

154 views

### Is the pointwise supremum of a continuous function continuous?

Suppose $f(x , y)$ is continuous in both variables. For any $\epsilon > 0$ and some $y_0$, let $h_{\epsilon}(x) = \max_{y^{'}: \| y^{'} - y_0 \| \leq \epsilon} f(x , y^{'})$. It seems to me that $...

**1**

vote

**0**answers

51 views

### Proximity operator of lower semi-continuous and convex functions pre-composed with norm

Let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a some-where finite, lower semi-continuous, increasing, and convex function. It is easy to verify that the function $\Phi:\mathbb{R}^n\...

**3**

votes

**0**answers

67 views

### Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...

**8**

votes

**0**answers

85 views

### Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...

**4**

votes

**1**answer

104 views

### Condition for existence of a continuous function realizing a partition

Let $\{U_i\}_{i=1}^{I}$ be a non-empty and finite collection of non-empty, disjoint, open, (and obviously bounded) subsets of $[0,1]^n$. Suppose also that $[0,1]^n=\cup_{i =1 }^{ I} \overline{U_i}$. ...

**0**

votes

**1**answer

69 views

### A question on graph partitioning

Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...

**0**

votes

**0**answers

34 views

### Examples of recursive TSP heuristics

Question:
What are examples of heuristics for the Traveling Salesman Problem, that are recursive in the sense that they can efficiently calculate the shortest Hamilton cycle in a graph if the optimal ...

**0**

votes

**1**answer

70 views

### Gradient-descent “type” Methods for non-convex and non-smooth functions

Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:
lower semi-...

**2**

votes

**2**answers

125 views

### Convex optimization closed-form solution

Consider the standard second order cone programming problem:
\begin{equation}
\begin{array}{ll}
\operatorname{maximize} & \bar{p}^{T} x \\
\text { subject to } & \bar{p}^{T} x+\Phi^{-1}(\beta)\...

**4**

votes

**2**answers

145 views

### Find the maximum trigonometric polynomial coefficient $A_{k}$

I posted this question on Math Stack Exchange but did not get any answer. I am trying my luck here.
Let $n,k$ be given positive integers and $n>k$. If for all real numbers $x$ we have $$A_{1}\cos{...

**-1**

votes

**1**answer

56 views

### Existence of continuous selection for metric projection

Let $(X,d)$ be a separable complete geodesic metric space and let $K$ be a compact (non-empty) subset of $X$. Without assuming things like linearity, the convexity of $K$, and locally convexity, ...

**0**

votes

**0**answers

88 views

### Reference for matrix Lyapunov function / matrix dynamic system / stability

We usually consider $\dot{x} = f(x)$, where $x$ is a vector.
Now, I want to consider $$\dot{X}=f(X,U),$$ where $X$ is a square matrix $\mathbb{R}^{n\times n}$ state, $U$ is a square matrix variable $\...

**3**

votes

**0**answers

83 views

### Bounds on minimum solutions to empirical and theoretical objective functions

Let $P$ and $Q$ be two probability distributions and let
$$S_0 = \min_{f,g} \left[ \int f(x)\, dP(x) + \int g(y)\, dQ(y) \right]$$ such that $f(x)+g(y) \geq \langle{x,y\rangle}$ where $f,g$ are ...

**0**

votes

**0**answers

92 views

### Strongly convex optimization error bounds

Suppose I want to minimize a function $G(f)$ using first order strongly convex methods and I get a solution $f^*$, where we restrict our solution set to strongly convex $f$. Now let $f_0$ be the ...

**0**

votes

**0**answers

100 views

### Barycenters on Hadamard Manifolds

Let $(M,g,m_0)$ be a pointed-Hadamard manifold with Riemmanian distance function $d_g$, $(X,\Sigma,\mu)$ be a finite measure space. We use $L^2(\mu;M,m_0)$ to denote the metric space consisting of ...

**1**

vote

**1**answer

29 views

### Complexity of calculating the optimal amalgamation of an optimal cycle-cover

Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...

**5**

votes

**1**answer

227 views

### Signed distance function and level set

For $\phi\in C^1(\mathbb{R}^N)$ with $$\omega_{\phi}=\{x\in\mathbb{R}^N\ |\ \phi(x)>0\}$$ being a bounded set with $\nabla\phi (x)\neq 0,\ \forall\ x\in\phi^{-1}(0)=\partial\omega_{\phi}\neq \...

**2**

votes

**1**answer

81 views

### Normal cones and KKT conditions

I'm trying to understand a statement from the book "Perturbation Analysis of Optimization Problems", by Bonnans and Shapiro. Let me start by providing some context. In page 148, the authors ...