Questions tagged [oc.optimization-and-control]

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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
20