Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
971
questions
2
votes
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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 ...
