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
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
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 ...
- 16.4k
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
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 ...
- 128k
3
votes
2
answers
642
views
Simultaneous extensions of strongly convex functions
21/03/2017: I have decided to accept Denis Serre's answer, even though it does not exactly answer my question, however I like its simplicity and I'd say it is close enough to the desired claim. Of ...
- 28k
1
vote
0
answers
71
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
- 11
2
votes
1
answer
175
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
- 5,429
0
votes
0
answers
201
views
How expensive is a proximal operation?
In optimization, a proximal step is usually considered as cheap as a gradient step. I'm quite confused by this. Why are people taking this convention at all?
A typical proximal step indeed incurs a ...
- 31
2
votes
1
answer
151
views
Distance between convex hulls in a bounded closed convex set
Let $X$ be an infinite-dimensional Banach space and $C\subseteq X$ be a bounded closed convex subset. Let $\{z_i\}_{i\in\mathbb{N}}$ be a sequence of linearly independent points in $C$ and for each $n\...
- 128k
5
votes
3
answers
496
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 314
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 5,429
1
vote
1
answer
209
views
Does the value function of a quadratic program stay convex when adding constraints?
I am interested in the value function of a quadratic program of the form
$$
v(y)=\min_x \frac{1}{2} x^\top Q(y) x,
$$
subject to a linear equality constraint
$$
E(y)x=d(y),
$$
and a linear inequality ...
- 61.9k
1
vote
1
answer
55
views
From relative convexity to modulus of continuity estimates for the dual gradient mapping
Let $F: \mathbf{R}^d \to \mathbf{R}$ be a convex function, let $m > 0$, and define $Q_m: \mathbf{R}^d \to \mathbf{R}$ to be the mapping $x \mapsto \frac{m}{2} \| x \|_2^2$. One says that $F$ is $m$-...
CommunityBot
- 1
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
7
votes
2
answers
497
views
Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex
I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex.
I have managed to prove this by moving all ...
- 5,429
0
votes
2
answers
197
views
Convergence of the infima of convex functions on $\mathbb{R}^m$
Any thoughts on proving the following statement, which is a generalization of the result in convergence of the infima of convex functions from domain $\mathbb{R}$ to $\mathbb{R}^m$ and also Theorem 1 ...
- 12.7k
3
votes
1
answer
189
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 434
2
votes
1
answer
181
views
Matrix function as gradient
Let $S_n^{++}(\mathbb{R})$ be the space of $n \times n$ symmetric positive definite matrices. For $M \in S_n^{++}(\mathbb{R})$ consider the function $f: X \in S_n^{++}(\mathbb{R}) \mapsto M X^{-1} M$.
...
- 52.3k
3
votes
0
answers
109
views
Convex minorants to convex functions, given partial Taylor expansion and smoothness estimate
Let $V$ denote a strictly convex function (in arbitrary dimension) whose Hessian is $L$-Lipschitz. Given only this knowledge, and the values of $\left\{ V \left( x \right), \nabla V \left( x \right), \...
- 801
0
votes
2
answers
319
views
Representation of continuous, monotone, concave functions
Is there a characterization of all continuous functions $f:\mathbb{R}\rightarrow \mathbb{R}$ satisfying:
$f(0)=0$
$f$ is monotonically increasing
$f$ is concave
My intuition is that $f$ should admit ...
- 128k
2
votes
1
answer
106
views
Submodularity of a particular function derived from a convex function?
Consider a convex function $f : \mathbb{R}^d \to \mathbb{R}$. Define now the set-input function $g_f : 2^{[d]} \to \mathbb{R}$ as follows,
\begin{align}
g_f(S) = \min \left\{ f(x) : x \in \mathbb{R}^d ...
- 3,042
1
vote
1
answer
69
views
Characterization of the behavior of the residuals in conjugate gradient
In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...
- 128k
1
vote
1
answer
208
views
Has the following generalization of monotropic programming been studied in the literature?
I am interested in problems of the form
$$\min_{x \in C} \sum_{i=1}^n\sum_{j=1}^n f(x_i,x_j)$$
where $C$ is a convex subset of $\mathbb{R}^{n}$, and $f \colon \mathbb{R}^{2} \to \mathbb{R}$ is convex.
...
CommunityBot
- 1
6
votes
1
answer
2k
views
SDP formulation of noisy low-rank matrix completion
Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
2
votes
1
answer
594
views
Tangent cone of a closed convex cone
Let $K \subset \mathbb{R}^n$ be a closed convex set. Given a point $u \in K$, the tangent cone of $K$ at $u$ is defined as (or characterized by)
$$
T_K(u) := \mathrm{cl}(\left\{ t (v - u) \mid v \in K,...
- 128k
2
votes
1
answer
106
views
Is $f^{-a}$ locally integrable if $f\geq 0$ has a unique stationary point ( a minimum) at which the Hessian is positive definite, $0<a<d/2$
Let $0<a<d/2$, let $B$ be the unit ball in $\mathbb{R}^{d}$ centered at the origin, and let $f:B \to [0,\infty[$ be a a smooth function such that
(1) $f(x)\geq f(0).$
(2) $\nabla f(x)\neq 0,\...
- 852
0
votes
0
answers
57
views
optimization of mixed linear and infinity norm
I have the following optimization problem:
Given a complex sequence $H_i$, $1 \leq i\leq N$. Find a complex sequence $G_i$ that minimizes:
$$ \lambda\cdot\max_i { |H_i\cdot G_i - 1|^2 } + \sum_i |G_i|^...
- 101
0
votes
0
answers
177
views
Given optimality of L1 norm, prove that absolute value of sum of a vector with proper sign is less than 1?
Problem:
Given a domain $\mathcal{D}\subset\mathbb{R}^{l}$, we can find $l$
points $\boldsymbol{v}_{i}\in\mathcal{D}$, $i=1,\cdots,l$. Each
point is a column vector with dimension $l\times1$. They ...
- 1
4
votes
2
answers
353
views
An upper bound of gradient norm for convex functions near minimizer
Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function. Denote $X^*$ as the set of minimizers of $f$ and assume $X^*$ is unbounded. Is it possible that $\|g_x\|$ is unbounded when $d(x,X^*)$ ...
- 34.7k
0
votes
0
answers
60
views
Trying to transform a minimization problem to a saddle point problem for the primal–dual algorithm
I’m reading about a problem, and the author goes from a classical minimization problem to a saddle point problem in order to perform a primal–dual algorithm on it [1].
However, It’s my first problem ...
- 12.9k
1
vote
1
answer
66
views
Estimate of minimum of the Poisson integrals corresponding to a convergent Hausdorff sequence of smooth bounded domains from below
Let $\{\Omega_{j}\}_{j\in\mathbb{N}}$ be a sequence of smooth bounded domains in $\mathbb{C}^{n}$ such that $\Omega_{j}$ converges to a smooth bounded domain $\Omega$ in the sense that the defining ...
- 63
1
vote
2
answers
125
views
Establishing quasiconcavity
Let $f:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be twice differentiable quasi-concave function satisfying $f(x)>0,\forall x \in \mathbb{R}_+$. Let $g:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be a positive, ...
- 67
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
2
votes
0
answers
178
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at Computational Science SE
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
...
4
votes
2
answers
561
views
Is it possible to use the Laplace Transform to calculate eigenvalues?
The relationship of Eigenvalues with Gradient Descent
Let $A$ be a symmetric (and thus diagonalizable) matrix, with diagonalization
$$A=VDV^T.$$
Let us define the quadratic function
$$f(x) = x^T A x.$$...
- 2,442
1
vote
0
answers
61
views
Fitting a convex polytope with 𝑛 facets between two nested spheres
This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 141
4
votes
1
answer
567
views
Advantages of hyperbolic programming over semidefinite programming?
What are the advantages of a hyperbolic program over a semi definite program? SDPs can be used to represent a wide variety of algebraic constraints. Are there constraints that can be represented in a ...
- 1,590
8
votes
0
answers
460
views
Are there any characterizations of $C^2$ convex functions?
There are several characterizations of convex functions with the Lipschitz continuous gradient. If we already know that the function is of class $C^1$, then we have the following equivalent conditions:...
- 28k
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
0
votes
1
answer
44
views
Identify maxima for 2-Dimensional Function without knowing cross-derivative
I am trying to proof the uniqueness of a maximum for a two-dimensional function (well behaved, twice differentiable, domain $R^2$, etc.), yet cannot compute the exact derivatives or the Hessian.
I ...
- 128k
1
vote
0
answers
83
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
1
vote
2
answers
603
views
Maximizing a sum of Gaussians
Let $\mathbf{x}_1, \dots, \mathbf{x}_n \in \mathbb{R}^d$ be $n$ given vectors. Define the function
$$ \mathcal{K}(\mathbf{x},\mathbf{y}) := \alpha\exp\left(-\frac{\|\mathbf{x}-\mathbf{y}\|^2}{2\sigma^...
CommunityBot
- 1
11
votes
2
answers
559
views
Convex hull of the Stiefel manifold with non-negativity constraints
Consider the Stiefel manifold
$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$
where $I_k$ is the $k$-dimensional identity matrix. It is well known that
$$\mathrm{conv} \left( ...
0
votes
1
answer
160
views
Prove zero slope point is global maximum for constrained function with binomials. Without restriction, objective function is non-concave
How to prove the zero slope point is a global maximum in this non-concave program for a function with binomials?
I need to find the (global) maximum of the following constrained problem:
$$\max_{CAP} \...
CommunityBot
- 1
0
votes
1
answer
134
views
Strict inclusion for recession cone of closure of a convex set
Let $C$ be a nonempty closed convex subset of $\mathbb{R}^n$. The recession cone of $C$ is given by
$$R_C=\left\lbrace d\in\mathbb{R}^n:x+td\in C, \forall t>0, \forall x\in C\right\rbrace.$$
It is ...
2
votes
0
answers
56
views
Whether $d_x(t) := \|P_t(x)-x\|_H$ is increasing in $t$ where $P_t:H \to H$ is the proximal operator of a convex function
Let $H$ be a Hilbert space (e.g Euclidean $\mathbb R^n$), and fix a proper convex function $f:H \to (-\infty,+\infty]$. Given any $t \ge 0$, let $P_t:H \to H$ be the proximal operator of $f$ at level $...
- 6,853
3
votes
2
answers
207
views
Generalizing Pythagorean Theorem: equations defining edges of a (convex) $n$-gon with $n-2$ prescribed angles?
Let $n\geq 3$ be an integer and $0<\alpha_1, \dots ,\alpha_{n-2}<1$. Let's say a tuple of positive numbers $(e_1,\dots, e_n)$ is nice if there is a convex $n$-gon $A_1\dots A_n$ such that $\hat ...
- 6,337
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 4,219
6
votes
0
answers
136
views
Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...
- 401