Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
839 questions
7
votes
2
answers
178
views
Separating domains in $\mathbb{R}^{2n}$ by a real algebraic variety
Suppose $\Omega_1$ and $\Omega_2$ are two disjoint unbounded domains in $\mathbb{R}^{2n}$, $n \in \mathbb{N}$. Can there be conditions on $\Omega_1$ and $\Omega_2$ so that these two domains can be ...
- 171
0
votes
0
answers
116
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
6
votes
1
answer
234
views
Stopping criteria for damped Newton iterations with backtracking line search
Are there better criteria than the Armijo criterion for damped Newton iteration with backtracking line search, when the objective is standard self-concordant? (See Boyd and Vandenberghe.)
Let $F(x)$ ...
- 840
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 5,429
0
votes
0
answers
56
views
Convex optimization of the Lovász extension of a submodular function
I have a finite set of $n$ elements $A$, and a submodular function $f:2^A\rightarrow R$.
Let $g:[0,1]^n\rightarrow {R} $ be the Lovász extension of $f$.
I want to solve the following optimization ...
- 107
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
2
votes
2
answers
293
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
- 1,714
6
votes
0
answers
48
views
Strengthening the Kovner-Besicovich theorem: Does every unit-area convex set in the plane contain a centrally symmetric hexagon of area $2/3$?
The Kovner-Besicovich theorem states that every convex set $S$ in the plane contains a centrally symmetric subset $C$ of at least $2/3$ the area of $S$, and that this bound is sharp for triangular $S$....
- 3,068
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 ...
0
votes
0
answers
38
views
Approximate local minima for sum of inverse trigonometric functions
Let $\{a_1, a_2, ..., a_N\} \in [0, 1[^N$, I would like to approximate the minimum of the function
$$f(x) = x \sum_{i=1}^N \left(\sin(x)^2 - \sin(a_i x)^2 \right)^{-2} $$
in the domain $x \in {]0, \...
CommunityBot
- 1
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
0
votes
0
answers
40
views
Iterating partially-unconstrained optimization with projection
Let $f:H\to \mathbb{R}$ be a strictly convex Fréchet differentiable, coercive function on a separable Hilbert space $H$ and let $C_1,C_2\subseteq H$ be closed and convex.
I want to optimize
$$
\tag{(A)...
- 63.9k
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 ...
- 411
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 ...
- 128k
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 ...
- 3,065
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 \...
- 63.9k
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 \...
- 4,713
4
votes
1
answer
402
views
Linear convergence rate of proximal point algorithm
For $T : R^n \to P({R^n})$ maximally monotone, the proximal point algorithm (step size $c>0$)
$$
x^{k+1} = (I + c T)^{-1} x^k,
$$
converges linearly with rate $\kappa = \frac{1}{1 + c \sigma}$ if $...
CommunityBot
- 1
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 ...
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$ ...
- 6,367
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
13
votes
4
answers
3k
views
Is group theory useful in any way to optimization?
For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it.
Is group theory useful in any way to ...
- 2,388
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:
$\...
- 128k
1
vote
0
answers
121
views
John and Lowner ellipsoid
I am looking at a proof to show that Lowner ellipsoids are unique for centrally symmetric convex body $K$. I want to show basically that
$$
\DeclareMathOperator{\Vol}{Vol}\DeclareMathOperator{\Low}{...
- 6,367
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
4
votes
1
answer
163
views
Gap to fill in the Aubin–Ekeland proof of the mountain-pass theorem
Working through the proof of the mountain-pass theorem given in Applied Nonlinear Analysis by Aubin & Ekeland, at what seems to be a critical point of the proof (the top of page 274) they refer to ...
- 6,367
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
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}$ (...
14
votes
2
answers
743
views
Is there a class of optimization problems more general than semidefinite programming?
I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there ...
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
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 ...
- 63.9k
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
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(...
3
votes
1
answer
158
views
Numerical scheme for convex optimization
Given $(e_n)_{-N\le n\le N}\in\mathbb R^{2N+1}$ and $-1<x<1$, solve
\begin{eqnarray}
&&\max_{(q_n)_{-N\le n\le N}\in\mathbb R^{2N+1}_+}~ \sum_{n=-N}^N (e_n-\log(q_n))q_n \\
\mbox{s.t.} &...
CommunityBot
- 1
30
votes
5
answers
14k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
- 1,590
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 ...
- 2,670
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 ...
- 7,633
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,065
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)...
- 128k
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 ...
2
votes
0
answers
191
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
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.
...
- 35.5k
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 ...
- 128k
1
vote
1
answer
98
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 ...
- 128k
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}\...
- 128k