Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
800
questions
4
votes
0
answers
125
views
A convex function is "usually" subdifferentiable
Let $X$ be a locally convex topological vector space, and let $f:X\to\mathbb R\cup\{\infty\}$ be a proper, convex, lower semicontinuous function, whose effective domain $D:=f^{-1}(\mathbb R)$ is ...
- 450
4
votes
0
answers
207
views
Fréchet subdifferentiation on riemannian manifolds
Context. I'm looking for a "natural" definition of subdifferentials on riemannian manifolds.
Given a function $F:\mathbb R^m \to \mathbb R$, its Fréchet-subdifferential at a point $w \in \...
- 6,726
4
votes
0
answers
205
views
How to find the dimension of the polar cone of a convex cone generated by some given vectors
Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
- 461
4
votes
0
answers
252
views
Can this function be minimized?
Let $X$ be a locally convex TVS, and let $A$ and $B$ be convex and compact subsets of $X$ with $A \subset B$.
Let $f: A \times B \to [0,\infty]$ have the following properties:
(1) For all $b \in B$, $...
- 839
4
votes
1
answer
333
views
Minimization of a discrete valued function
$$
\min_{f} \sum_{i=1}^n \max \left( 0, 2f(i) - f(i-1) -f(i+1)\right),
$$
where the minimum is taken over all the functions $f$ from $\{0,1,2,\ldots,n+1\}$ to $[0,x]$, $x <1$, such that $f$ is non-...
user83947
4
votes
0
answers
483
views
analytic approximations of the min and max operators
Question:
What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here.
For any $\...
- 3,827
4
votes
0
answers
223
views
Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables
Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest:
$1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed;
$...
- 359
4
votes
0
answers
504
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 381
4
votes
0
answers
139
views
Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum - part II
Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...
- 876
4
votes
0
answers
299
views
Best Approximation in Operator/non-Frobenius Norm
Since the Frobenius norm on matrices is generated by an inner product, solving the optimization/approximation problem of approximating an operator $X$ with a scalar multiple of another operator $Y$
$$\...
- 143
4
votes
0
answers
296
views
Derivative of rank $r$ approximation of matrix
Let $Y \in \mathbb R^{n \times c}$ and $r$ be an integer with $1 \le r \le \operatorname{rank}(Y)$. Consider the problem
$$\text{minimize} \|Y-X\|_{\text{Fro}}^2\text{ over }X \in \mathbb R^{n \times ...
- 6,726
4
votes
0
answers
237
views
Stochastic subgradient descent almost sure convergence
I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
- 141
4
votes
0
answers
76
views
How well does an estimator perform on another dataset?
Suppose $X \sim N(0, \Sigma)$ is a $d$-dimensional Gaussian random vector. And we have $2n$ $i.i.d$ sample $X_1, \ldots, X_{n}, \ldots, X_{2n}$.
Let $\hat{\Sigma}_1 = \frac{1}{n}\sum_{i=1}^nX_i X_i^\...
- 505
4
votes
0
answers
130
views
Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)
I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program
\begin{align}
\max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~...
- 1,127
4
votes
0
answers
106
views
Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization
Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing.
For ...
- 909
4
votes
0
answers
195
views
Basin of Attraction
I have a function $F$ which is defined as follows:
$$
F(x) = \sum_{i=1}^N f(z_i^T x)
$$
where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...
- 291
4
votes
0
answers
124
views
An inequality from the "Interlacing-1" paper
This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...
4
votes
1
answer
223
views
Constructing a quasiconvex function [closed]
Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called
convex if
$$
f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, \...
- 41
4
votes
0
answers
164
views
Two quadratic programming problems always same answer? [closed]
Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal.
Problem 1:
Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$
Subject to $ A \mathbf{...
- 171
4
votes
0
answers
183
views
This function looks quasiconvex, can't understand why
Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
- 41
4
votes
0
answers
292
views
When is the sum of a weak-$*$ closed convex cone and a subspace also weak-$*$ closed?
Let $X$ be a Banach space. Suppose $C \subset X^*$ is a convex cone and $V \subset X^*$ is a subspace, and suppose both $C$ and $V$ are closed in the weak-$*$ topology. Are there any general ...
- 195
4
votes
1
answer
2k
views
Maximizing supermodular functions
I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...
3
votes
2
answers
3k
views
Complexity of convex quadratically constrained quadratic programming (QCQP)
Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP)? Any references?
- 145
3
votes
1
answer
4k
views
L-infinity-norm regularized proximity problem
I have a question:
$$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$
where $t, \lambda$ are given constant.
I think this may be a classic problem? However, I didn't find closed form of its ...
- 33
3
votes
2
answers
2k
views
Interior of a dual cone
Let $K$ be a closed convex cone in $\mathbb{R}^n$. Its dual cone (which is also closed and convex) is defined by $K' = \{ \phi\ |\ \phi(x) \geq 0,\ \ \forall x \in K\}$.
I know that the interior of $...
- 133
3
votes
2
answers
1k
views
Strict complementary slackness for semidefinite programs with strong duality
By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...
- 12.6k
3
votes
1
answer
240
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
3
votes
1
answer
201
views
it's convex sequence inequality
A sequence $a_0,a_1,\dots,a_n$ of real numbers is called concave if $a_{0}=0$, and for each $0<i<n$, we have $a_i\geq\dfrac{a_{i-1}+a_{i+1}}{2}$.
Find the largest $c(n)$ such that for every ...
- 4,230
3
votes
2
answers
624
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 ...
- 11.3k
3
votes
1
answer
236
views
Is the Binomial Expectation of a Multivariate Convex Function Convex in the Vector p?
Let $\mathbf{p}=(p_1,\dots,p_m)$ be a vector in $[0,1]^m$ and let $\mathbf{X}=(X_1,\dots,X_m)$ be a vector of independently-distributed binomial random variables such that $X_i\sim \text{Binom}(n,p_i)$...
- 103
3
votes
1
answer
167
views
On the convexity of certain set of random vectors
Let ${\cal X}$ be the set of pairs of random variables $(X,Y)$ with finite expectations. For constant $c\in[0,1]$, define set
$$
\{(X,Y)\in{\cal X}:\exists a\geq 0, \, b\geq 0 \text{ such that } E[\...
- 5,957
3
votes
2
answers
203
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 ...
- 30.3k
3
votes
2
answers
350
views
How to find a solution of a large system of linear diophantine inequalities?
I need to find a solution (all solutions, or at least upper and lower bounds) in positive integer numbers to the system $Ax \ge f$, where $A$ is an integer matrix.
With SageMath, I solved it with the ...
3
votes
1
answer
225
views
Measurable selection for argmin to distance
Let $Y$ be a Banach space and equip $Y$ with the weak topology. Now, let $X$ be a closed, bounded, and convex subset of $Y$ and suppose that the relative (weak) topology on $X$ is metrizable with ...
- 4,969
3
votes
1
answer
142
views
Duality problem of an infinite dimensional optimization problem
I am reading the paper "OPTIMAL INEQUALITIES IN PROBABILITY THEORY: A CONVEX OPTIMIZATION APPROACH" by BERTSIMAS and POPESCU. In the paper, the authors derived a duality problem for an ...
- 53
3
votes
1
answer
246
views
Polygon of convex arcs
Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists).
Assume ...
- 422
3
votes
1
answer
515
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 ...
- 133
3
votes
1
answer
251
views
Strong polynomial algorithm for linear programming
What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
- 771
3
votes
2
answers
374
views
Standard solution to semidefinite program [closed]
I have an optimization problem of the following form
$$\text{minimize} \,\|Qa-b\|_2 \quad \text{ subject to } Q \succeq 0$$
where $a,b \in \mathbb{R}^n$ are given and the $n \times n$ square matrix ...
- 153
3
votes
3
answers
337
views
Sensitivity analysis in conic optimization
I have a conic optimization of the form:
$$\min_x \langle c, x \rangle,\ \text{s.t.}\ Ax = b,\ x \in K.$$
where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a ...
- 143
3
votes
1
answer
145
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 ...
- 33
3
votes
1
answer
546
views
Strong convexity inequality w.r.t. infinity norm $\lVert\cdot\rVert_{\infty}$
Consider a twice differentiable 1-strongly convex function $f:\mathbb{R}^n \to \mathbb{R}$.
Is it true that there exists $\alpha>0$ independent of $n$ such that, for all $x \in \mathbb{R}^n$:
\...
- 33
3
votes
1
answer
240
views
What is a non-trivial example of an unbounded subdifferential?
Let $f: X \to [ -\infty, \infty]$ be some function,
Can someone provide a non-trivial example where the subdifferential evaluated at a point $x$,
$$\partial f(x)$$ is "unbounded"? (trivial examples ...
- 469
3
votes
2
answers
97
views
Optimal covering of line subsegments using a given set of disks
Is there a way of picking a minimal set of disks that's still covering the same line subsegments as all the disks together? Any help or references highly appreciated. Below is just an illustrative ...
3
votes
1
answer
1k
views
How to inference the dual form of perceptron?
The model of perceptron is a linear binary classifier, which is $f(x)=\mathbb{sign}(w^Tx+b)$. $x$ is the datapoint as $w$ as well as $b$ are the parameters.
The cost function of Primal Perceptron is $...
- 143
3
votes
1
answer
270
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 33
3
votes
1
answer
123
views
Finding a semigroup that maximizes the trace of a sum of matrices
Let $H$ be a finite semigroup containing $n$ elements from a compact group $G$. I am trying to solve
$$\max_{h_i,\ h_j\ \in\ H} \operatorname{tr} \sum_{i,\ j\ \leq\ n} \rho(h_i^{-1} h_j)(A_j A_i^T)$$...
- 121
3
votes
1
answer
281
views
Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points
I am currently working on a problem where I have to minimize a $m$-strongly convex function
$$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$
over a bounded integer lattice,
$$L = \mathbb{Z}^n \cap [-...
- 379
3
votes
2
answers
694
views
Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
- 131
3
votes
1
answer
301
views
generalized mean inequality extension
from generalized inequality, we now that for $p>q$, we have $M_p(\mathbf{x})\ge M_q(\mathbf{x})$. now I am curious to know if we can find a constant $\alpha(p,q)$ which is only function of $p,q$ ...
- 383