Questions tagged [oc.optimization-and-control]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
49 views

Pontryagin's maximum principle for discrete systems: reference request for general case [migrated]

I am reading the articles: Optimal control for systems described by difference systems, Hubert Halkin, Advances in Control Systems, Vol 1, Academic Press, New York-London, 1964, Pages 173-196, ...
ExpressionCoder's user avatar
0 votes
0 answers
38 views

Gradient-based optimization of $n$ functions

I appreciate the willingness of everyone to assist me in advance. I am faced with a set of $n$ distinct convex optimization problems, each defined as follows: \begin{equation} \max\limits_{x \in \...
raian's user avatar
  • 1
10 votes
1 answer
439 views

The drunken blind man’s walk

Consider a drunk, blind man starting in the middle of the two dimensional open unit ball. At each turn, the man chooses a direction to move a step of size $\delta > 0$ in. Unfortunately, he is very ...
Nate River's user avatar
  • 4,822
0 votes
0 answers
47 views

Concentration of bilinear forms

This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
Felix Goldberg's user avatar
2 votes
0 answers
31 views

0-1 knapsack problem with additional capacity

The 0-1 knapsack problem maximizes the profits of items under a capacity constraint (let's call this capacity $C$). I am interested in an augmented setting where the algorithm is permitted to use a ...
Titan's user avatar
  • 21
1 vote
0 answers
57 views

Under which condition, such that all second-order critical points satisfy $\sum_j\cos(\theta_i-\theta_j)>0$ for all $i\in[n]$?

Consider the following non-convex function $$E(\theta):=-\sum_{i,j}A_{ij}\cos(\theta_i-\theta_j)$$ where $A$ is a symmetric, diagonal-free matrix whose non-diagonal element are $\pm 1$. In other words,...
happyle's user avatar
  • 39
0 votes
0 answers
38 views

Max-flow modeling with unified vehicle and commodity variables

I am working on a network flow problem that involves routing through a time-space network. The network consists of: A single source node and a single demand node. A fleet of vehicles with specified ...
graphtheory123's user avatar
0 votes
0 answers
22 views

How to control the angles of Kuramoto model by controlling its order parameter?

Consider Homogenous Kuramoto model in this paper. In theorem 3.1, the author derive condition on $A$ such that all second-order critical points of $E(\theta)$ are in two opposite quadrants, by saying ...
happyle's user avatar
  • 39
1 vote
0 answers
43 views

Optimal orbital tranfers: reference for statements & proofs

I know that Pontryagin's contribution to optimal control in the 1950'ies was allegedly inspired by the then-nascent rocket industry and the question of how to get a rocket into orbit with minimum fuel....
5th decile's user avatar
  • 1,461
2 votes
0 answers
157 views

Hunting an invisible target

An invisible target on the integer line starts at $0$. On each round it either stays put, moves to the left or moves to the right by $1$ with probability $\frac{1}{3}$ each. You are then asked to ...
Nate River's user avatar
  • 4,822
20 votes
2 answers
3k views

How to optimally bet on a biased coin?

A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you. You start with a total ...
Nate River's user avatar
  • 4,822
2 votes
0 answers
136 views

Spectrum of an almost Hamiltonian matrix

I have a complex-valued block matrix $N=\begin{bmatrix} A & B \\ C & -A^* \end{bmatrix}$, where $A$ is diagonal, $B=B^*$, and $C$ is rank-1 but not Hermitian. If $C$ were Hermitian, $N$ would ...
mathamphetamine's user avatar
0 votes
0 answers
55 views

Existence of a measurable maximizer

Let $F$ be a continuous cdf with full support on $[0,1].$ Let $A$ be a compact subset of $\mathbb{R}$ and $\mathcal{M}$ be the set of measurable functions $\alpha:[0,1]\rightarrow A.$ Let $\bar \alpha ...
FeleMath's user avatar
0 votes
0 answers
30 views

Efficient algorithms to find the global minimum of a non-convex quadratically-constrained quadratic program

I am working on a problem involving a non-convex quadratically-constrained quadratic program and am seeking efficient algorithms to find its global minimum. The problem is structured as follows: Fix ...
Yu-Jia Wang's user avatar
0 votes
0 answers
35 views

Seeking help with a matrix optimization problem involving matrix exponentiation

I'm working on an optimization problem where I need to find matrices $P$, $Q$, and $C$ that minimize the norm of the difference between a given matrix $A$ and another matrix defined as $e^{P(Q + Q^T - ...
Shahriar Akbar's user avatar
0 votes
0 answers
41 views

Formulate LABS problem as QUBO

I'm trying to formulate the LABS (low autocorrelation binary sequences) as a QUBO (quadratic unconstrained binary optimisation). The LABS problem is as follows: Given a sequence $s_i \in \{-1,1\} $, ...
Maximilian's user avatar
0 votes
0 answers
19 views

Approximation with "quantile-constraints"

Question: given: $$\begin{align}&\phantom{=}\lbrace \left(x_i,y_i\right),\ x_i\in\mathbb{X}, y_i\in \mathbb{R}\rbrace_{i=1}^n\\ &\phantom{=}f: (x\in\mathbb{X},\,p_1,\dots,\, p_k\in\mathbb{R})\...
Manfred Weis's user avatar
  • 12.6k
0 votes
0 answers
79 views

Elliptic PDEs in BSDEs and in optimal control

This soft/reference question is related to this MO post of a similar nature. What are some examples of elliptic PDEs appearing in control and BSDEs?
ABIM's user avatar
  • 5,019
0 votes
0 answers
31 views

Convergence of numerical scheme for HJB equation

Convergence of numerical scheme for HJB equation has been widely studied, the key paper is the Barles's one. Essentially, the convergence is guarenteed if the scheme is: Consistent Stable Monotony ...
NancyBoy's user avatar
  • 175
1 vote
1 answer
73 views

Second order differentiability of solution operator to nonlinear boundary value problem

I am currently reading the paper [1]. The paper deals with the BVP: \begin{align*} \partial_t u - \Delta u + u(u-a) & = -qu \text{ in } ]0,T\mathclose[ \times \Omega \\[6pt] \partial_{n}u & = ...
Paul Joh's user avatar
  • 161
0 votes
0 answers
45 views

Numerically finding periodic solution to Riccati equation with a scalar unknown parameter

We have a Riccati equation with an unknown scalar parameter $a$. It is proven to have unique real solution pair $\{y(x), a\}$ exists so that $y$ is periodic: $$ y'=ap_{0}(x)+q_{0}(x)+q_{1}(x)y+q_{2}(x)...
That Frank Guy's user avatar
1 vote
1 answer
79 views

Norm bound in simultaneous stability to semidefinite program

In the context of robust control, I remember hearing that the two following problems are equivalent. Find $P \succ 0$, such that $A P + P A^{\top} \prec 0$ for all $A \in \mathscr{A}$ where $$\...
wsz_fantasy's user avatar
0 votes
0 answers
36 views

Generalized envelope theorems

I'm looking for references for two generalizations of Danskin/envelope-type theorems for convex optimization. The first is for when the parameters are functions on a space rather than numbers. A ...
Aaron Bergman's user avatar
2 votes
2 answers
312 views

Uniqueness of sum of squares representation

Given a polynomial $f(x) \in \mathbb{R}[x] = \mathbb{R}[x_{1},\dots,x_{n}]$. We say $f(x)$ is sum of squares(SOS) if there are polynomials, $p_{1},\dots,p_{k}$ such that $f = p_{1}^{2} + \dots+p_{k}^{...
wsz_fantasy's user avatar
0 votes
0 answers
50 views

Alternatives to McCormick Envelope

I have an optimization problem for which I have the optimal solution obtained by the ILP. However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
LyLa's user avatar
  • 3
2 votes
0 answers
112 views

Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$

Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
Diego Fonseca's user avatar
0 votes
0 answers
25 views

Which penalization works for this optimisation problem?

Let $m,n$ be given integers. Set $K:=[0,1]^{mn}$ and define the function $L:K\times\mathbb R_+^m\times\mathbb R_+^n\to\mathbb R$ as follows : for $z=(z_{i,j})\in K$, $a=(a_i)\in\mathbb R_+^m$, $b=(...
Fawen90's user avatar
  • 975
9 votes
2 answers
533 views

Book for matroid polytopes

I have made a study of polytopes with the books of Ziegler and "Integer Programming" of Conforti, my main goal is to study matroid polytopes; to study matroids I have thought about the book &...
Wrloord's user avatar
  • 201
3 votes
1 answer
236 views

Is this constraint convex?

I have an optimization problem where the following constraint causes DCP Rule Error. $$e^{x_n} \leq B \log _2\left(1+\frac{e^{\rho_n} g_n^2}{\sum_{i=1}^{n-1} e^{\...
Mojtaba's user avatar
  • 31
0 votes
0 answers
90 views

Primal optimal attained implies dual optimal attained

Given some optimization problem $$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$ we can find the dual problem $$\max_{\lambda\in\mathbb{R}^m} g(...
wsz_fantasy's user avatar
3 votes
1 answer
174 views

Convex optimization without Slater's condition

In nearly all convex optimization methods that I read about, it is assumed that the problem satisfies Slater's condition, that is, there is a point that strictly satisfies all constraints (the ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
126 views

Estimating $\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\rangle ^4\right]}{E\left[\langle u\cdot x\rangle ^2\right]}$

Suppose we have access to samples of $x$ distributed according to unknown multivariate Gaussian in $\mathbb{R}^d$. Estimate the following quantity: $$\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
Yaroslav Bulatov's user avatar
4 votes
2 answers
462 views

How to get this inequality in Santambrogio's book about optimal transport?

Let $\hat{\varrho}, \tilde{\varrho}$ be probability density functions on $\mathbb R^d$ where $\tilde{\varrho} \in L^{\infty} (\mathbb R^d)$. For $\varepsilon \in [0, 1]$, we define $\varrho_{\...
Akira's user avatar
  • 815
0 votes
0 answers
67 views

Computationally efficient solution for the measure of central tendency minimizing Lp loss for p > 1

We know that the measure of central tendency that minimizes the Lp loss is $\min_c \sum_{i=1}^n |x_i - c|^p$ For $p=1$ (L1 loss), this is the median. For $p=2$ (L2 loss), this is the mean. Both of ...
olivarb's user avatar
  • 109
2 votes
1 answer
146 views

Conic hull of a rectangle

I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...
wsz_fantasy's user avatar
2 votes
0 answers
169 views

Regularity of linear Bellman equation

Let $f(x,t):B_1 \times [0,1] \to \mathbb{R}$ be Lipschitz function on both $x$ and $t$, $\varphi$ be Lipschitz function on both $x$ and $t$ on the parabolic boundary of $B_1 \times [0,1]$. Let $A$ be ...
mnmn1993's user avatar
0 votes
0 answers
33 views

Solving optimization problem restricted to non-convex subset

I have two continuous random variables that have pdfs with respect to the Lebesgue measure $p_{-1}(x), p_1(x)$. Let $m(x) := \frac{p_{-1}(x)+p_1(x)}{2}$ be a mixture of these two distributions. Let $B(...
Mark Schultz-Wu's user avatar
0 votes
1 answer
127 views

Existence of cyclic subspace decompositions for pairs of commuting matrices

Let $\mathbb{K}$ be an arbitrary field (possibly finite). Let $V$ be a finite-dimensional vector space over $\mathbb{K}$, and let $A,B$ be two linear endomorphisms of $V$ which commute. For $v\in V$, ...
Abdelmalek Abdesselam's user avatar
2 votes
0 answers
119 views

Graph Laplacians, Riemannian manifolds, and object collisions

To preface this question, I am a part-time game developer and full-time optimization fiend. I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
HeyoItsMateo's user avatar
1 vote
0 answers
131 views

Optimal transport-like problem where the objective depends on conditional probability distribution

$\DeclareMathOperator\marg{marg}$I would like to know if the following problem can be studied as an optimal transport problem, possibly imposing additional assumptions on the data. Consider two sets $\...
Francesco Bilotta's user avatar
13 votes
2 answers
1k views

Optimal search puzzle

Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
jackisquizzical's user avatar
0 votes
0 answers
70 views

Error bound for stochastic gradient descent method

To solve an optimization problem $\min_x G(x)$ using standard stochastic gradient descent method, we let $x_0$ be the initial point and $x_k$ be the $k$-th point such that \begin{equation} x_k = x_{k-...
Hao Yu's user avatar
  • 771
1 vote
1 answer
81 views

optimization over moving domains

Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem: $$L(a)=\inf_{b\in B_a}\ell(b),$$ where $\ell(b)$ is a infinite-times ...
Jeff 's user avatar
  • 87
0 votes
1 answer
139 views

nonlinear equation problem

Can you please help me solve the following nonlinear equation to determine the value of the vector $z$ : $$ \boldsymbol{a}=\boldsymbol{z}^{2} \odot \boldsymbol{K}*\boldsymbol{z}^{-1}$$ Where: $\...
Iman Nodozi's user avatar
1 vote
0 answers
53 views

LICQ vs MFCQ who is stronger [closed]

I want to ask you which constraint is stronger: MFCQ or LICQ.
zak.Ryd's user avatar
  • 11
0 votes
0 answers
46 views

Approximation factor for TSP Algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
Mathematician....'s user avatar
0 votes
0 answers
19 views

Find condition of X such that I-XSA is nonsingular, where $S$ is skew-symmetric and $A$ is symmetric, nonsingular

Given $I_n$ is the identity matrix, $A \in \mathbb{R}^{n,n}$ is symmetric and nonsingular, and $B\in \mathbb{R}^{n,n}$ is skew-symmetric.\ a) For which condition of a matrix $X \in \mathbb{R}^{n,n}$, ...
IscoBerlin's user avatar
0 votes
0 answers
59 views

Optimal top-k column subset

Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
Eli Bixby's user avatar
  • 101
2 votes
0 answers
108 views

Controlling the adjoint variables in a stochastically perturbed control problem

Suppose we have a deterministic control problem $$dX_t = b(X_t, u_t) \, dt$$ on a finite timeframe with no terminal cost; i.e. the objective functional to be maximised is $$\mathbb E \left [\int_{0}^T ...
Nate River's user avatar
  • 4,822
2 votes
1 answer
149 views

Can we say this nonlinear integer programming problem is NP-hard?

I was wondering if the following nonlinear integer programming problem is NP-hard or not. $$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$ such that $\sum_{i=1}^{n}...
Anson's user avatar
  • 21

1
2 3 4 5
23