All Questions
1,234 questions
1
vote
0
answers
95
views
Distance between two convex sets
Setting
If $A$ an $B$ are two symmetric matrices, we denote by $A >B$ when the matrice $A-B$ is definite positive.
In $\left(\mathbb{R}^{*}_{+} \right)^4$, consider the convex set $$ \Lambda = \...
- 125
0
votes
1
answer
59
views
Do separable cubic constraint and separable quartic constraint SOCP presentable?
I am an engineer who is doing some network modeling and optimization. During my work, I was running into a case that is quite strange. The problem that I am trying to solve seems to be convex and it ...
3
votes
0
answers
281
views
Interchange limit and supremum of functionals over a bounded convex set
Let $(H, \langle\cdot,\cdot\rangle)$ be a separable real Hilbert space and $B\subset H$ be (nonempty) convex and bounded, and suppose that $(\alpha_k)\subset H$ is a sequence for which the limit $\...
- 463
0
votes
1
answer
74
views
Clarification about this optimisation problem
Good morning everybody. First of all, I apologise to ask here the same question I asked on MSE three days ago, but I am in fact re-asking since I obtained no relevant advice. Perhaps I will hear some ...
- 149
1
vote
0
answers
37
views
When does an optimal input sequence for a discrete-time system exist?
Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
1
vote
0
answers
73
views
What is the closed form of a polyhedral cone's dual cone?
A polyhedral cone can be defined as
$$
\mathcal{K} = \{x~|~Ax\preceq 0\},
$$
where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to.
The ...
- 71
1
vote
0
answers
32
views
Variants of cutting plane method for convex optimization
The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
- 139
0
votes
0
answers
87
views
Comparison between the expected values of the inverse of the CDF of binomial-distributed random variables
Let us denote with $F(x;j,\mu)$ the cdf of a Binomial distributed random variable with $j$ trial with success probability $\mu$ considered in $x$, and let $f(x;j,\mu)$ be the pmf. Defining $0\leq \...
0
votes
0
answers
45
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 \...
- 1
4
votes
0
answers
46
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
0
votes
0
answers
26
views
The existence of convergent subsequences
Considering an optimization problem on an infinite-dimensional Euclidean space, the sequence of objective functions is $J_{n}(\theta_{n})=||f(X,\theta_{n})-Y||^{2} $, where X and Y are datas.
This can ...
0
votes
0
answers
39
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 ...
- 101
0
votes
1
answer
104
views
Optimality condition for strongly convex function under sparsity constraint
Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
- 399
1
vote
0
answers
41
views
How to extract 'top k' multiple solutions from a quadratic optimization problem?
Imagine we are interested in the following problem:
$$
\min_{w} \left( w^T V w + \lambda \|w\| \right) \\
\text{s.t. } w^T R \geq c
$$
Where 𝑤 is an $N \times 1$ vector, $V$ is an $N \times N$ ...
- 111
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
3
votes
2
answers
215
views
Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$
Is there a closed-form solution for
$$\max_D \operatorname{Tr}(ADBD)$$
where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
- 433
1
vote
1
answer
309
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
- 879
2
votes
1
answer
183
views
Convexity of a function
Let: $F_{j+1,y}(s)$ be the cumulative distribution function of a binomial distribution with mean $y$, $j+1$ independent trials considered for $s$ successes. Is it possible to show in any way that:
$\...
3
votes
0
answers
87
views
Instances of c-concavity outside of optimal transport?
Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \...
- 232
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
2
votes
1
answer
102
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 $$\...
- 275
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
0
votes
0
answers
45
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 ...
- 4,217
4
votes
0
answers
255
views
Economic equilibrium and tropical geometry
There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
- 123
0
votes
0
answers
64
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 ...
- 3
2
votes
0
answers
119
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}$ (...
2
votes
1
answer
423
views
Simple proof for convexity of a real valued matrix function
I am looking for a simple and short proof showing that $X \to \|X X^\top\|_F^2$ is a convex function where $\|\cdot\|_F$ is the Frobenius norm. I have one proof by showing that the derivative is ...
- 407
2
votes
0
answers
95
views
Self adjoint operators from energy functionals
It is known that the equation
$$
\Delta f = 0
$$
on some bounded domain $\Omega$ on $\mathbb{R}^n$ subjected to certain boundary conditions can be derived through the minimization of the Dirichlet ...
- 115
3
votes
1
answer
255
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^{\...
- 31
0
votes
0
answers
129
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(...
- 275
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
3
votes
1
answer
370
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 ...
- 3,549
1
vote
1
answer
156
views
On the additive property of the subdifferential of lower semicontinuous functions
Let $f:\mathbb R\to\mathbb R$ be a lower semicontinuous function, we define the Fréchet subdifferential of $f$ at $x\in\mathbb R$ by
$$\partial^F f(x):=\left\{L\in\mathbb R: \liminf_{v\to0}\frac{f(x+v)...
- 299
2
votes
0
answers
189
views
Max-cut from Laplacian
(This question seems like very standard material for those well-versed in the subject. I thought I would get a quick answer from Math stackexchange, but to no avail.)
Given a weighted graph with $n$ ...
- 511
1
vote
1
answer
176
views
Maximization of $\ell^2$-norm
Consider for $r,c>0$ the set
$$X_{r,c}=\{x \in \ell^1(\mathbb{N}) \mid \|x\|_1=r,\, \forall i \in \mathbb{N}: |x_i|<c\}.$$
Then I can show that $\inf_{x \in X_{r,c}} \|x\|_2 = 0.$
But is it ...
- 11
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
2
votes
0
answers
97
views
Lower & upper bound on the maximal component given the system of power sums
Given a non-negative vector $x=(x_1,x_2,\dots,x_n)\in\mathbb{R_{>0}^n}$ and $m\in\mathbb{N}$, construct a system of power sum symmetric polynomials (or norms, if you like)
$$
\begin{cases}
x_1+x_2+\...
- 21
2
votes
1
answer
159
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 ...
- 275
1
vote
1
answer
96
views
If $|P|<\infty$ and $C=P\cap\partial(\textrm{Conv}(P))$, then $P\subset\textrm{Conv}(C)$?
That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$?
It seems true intuitively. In ...
1
vote
1
answer
65
views
Boundedness of maximisers of parametric strictly concave functions
Let $L:[0,1]\times \mathbb R^m\times \mathbb R^n\to \mathbb R$ be defined by
$$L(\lambda, x,y):=\sum_{1\le i\le m}\alpha_i x_i + \sum_{1\le j\le n}\beta_j y_j -\sum_{1\le i\le m, 1\le j\le n} p_{i,j}\...
- 1,389
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 13.2k
1
vote
0
answers
109
views
Can the ideas of convex optimization be used to prove a bound?
If we define $\lambda(n)=\lfloor \log_2(n) \rfloor$ and $v(n)$ as the binary digit sum of positive integer $n$ we can make a toy example of what I think is the most important conjecture in addition ...
- 97
1
vote
1
answer
187
views
Bound the distance between two vectors on the probability simplex
Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$
$$\sup_{x>0} \...
- 135
2
votes
1
answer
225
views
Boundary points in $\overline{\operatorname{conv}\{z_i\}_{i\in I}}$
Let $X$ be an infinitely-dimensional Banach space and $\{z_i\}_{i\in I}$ be a set of linearly independent points in $X_{\leq 1}$, the closed unit ball of $X$. $I$ the index set is not necessarily ...
- 307
1
vote
1
answer
84
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 ...
- 87
1
vote
0
answers
94
views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program
$\min c.x$
subject to $A.x \leq b ; x \geq 0.$
Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
1
vote
0
answers
70
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
- 11
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...