Questions tagged [convex-optimization]
The convex-optimization tag has no usage guidance.
40
questions with no upvoted or accepted answers
7
votes
0
answers
116
views
Has compressed sensing been generalized to convex optimization problems?
Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type
$$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$...
- 71
7
votes
0
answers
158
views
SVM - running time for detecting if data is linearly separable?
If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
- 71
7
votes
0
answers
3k
views
Time complexity of standard semidefinite programming solvers
I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.
(I am not interested in algorithms like multiplicative weights updates method.)
- 121
7
votes
0
answers
129
views
What's the state of the art for matrix nuclear/trace norm optimization
I am interested in simple matrix optimizations with nuclear/trace norm:
$\min_X \left(f(X) + \|X\|_*\right)$
where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
- 71
6
votes
0
answers
101
views
Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization
In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
- 1,443
4
votes
0
answers
129
views
Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?
In Nemirovxki's lecture notes on interior point methods, I found the following.
He defines an approximate solution as satisfying the following, for any given $\epsilon>0$:
that is: the ...
- 2,078
4
votes
0
answers
132
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 91
4
votes
0
answers
106
views
Bounding a Solution of an SDP
It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, ...
- 41
4
votes
0
answers
102
views
Software that generates and solves a Lasserre hierarchy
Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
- 1,945
4
votes
0
answers
2k
views
Linear programming optimization problems using parallel algorithms
I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches ...
- 386
3
votes
0
answers
111
views
SVM perturbation bounds
Let $B$ be the unit ball of $\mathbb{R}^d$. Suppose that $x_1,\ldots,x_n$ are vectors in $B$ with labels $y_i\in\{-1,1\}$. We say that $w\in B$ separates this labeled set with margin $\gamma$ if $y_i(...
- 10.4k
3
votes
0
answers
162
views
Hessian of non differentiable convex function
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
- 265
3
votes
0
answers
134
views
Gradient descent step size for strongly convex functions
Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \...
- 141
3
votes
0
answers
88
views
First-order methods for solving SDP with geometric convergence or better
Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
- 832
3
votes
0
answers
188
views
Computing the convex hull of several polyhedra
Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an ...
- 1,224
3
votes
0
answers
82
views
What is the state-of-the-art asymptotics for convex optimization?
I've got a convex program of the form:
Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$). $A$ is a square binary matrix.
What algorithm gives ...
- 2,393
3
votes
0
answers
272
views
Maximizing a convex function where the objective function is separable but the search space is not
The problem statement is
Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$
Does this kind of problem structure allow one to use specific strategies to solve the ...
- 261
3
votes
1
answer
95
views
Extremal Ellipsoids
I'm considering the following problem.
Given a collection of $m$ ellipsoids in $R^n$, compute the maximum volume ellipsoid inscribed in their intersection.
In Boyd & Vandenberghe, Convex ...
- 199
2
votes
0
answers
54
views
program search with optimization methods for (resource bounded) Kolmogorov complexity
Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
- 31
2
votes
0
answers
30
views
Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
- 121
2
votes
0
answers
69
views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.8k
2
votes
0
answers
161
views
Non-Linear Programming with \min operator in the constraint
Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1.
\begin{align}
\text{maximize } &\sum_{i,j=1}^{m,n} c_{ij}...
2
votes
0
answers
205
views
Convergence of online convex optimization methods
I am new to this subject so this question might seem a bit trivial
Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
- 21
2
votes
0
answers
202
views
Runtime of Gomory's Cutting Plane Algorithm
I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
- 369
2
votes
0
answers
125
views
KKT-like conditions for values close to optimal solution
The KKT conditions are necessary and sufficient conditions for problems where we maximize over a convex function subject to linear inequality and equality constraints. That is $x^*$ is an optimal ...
- 161
1
vote
0
answers
42
views
What is the meaning of loss in online convex optimization?
I am studying online convex optimization, and it is stated that when we make a decision, we observe loss corresponding to our decision. In some problems like multi-armed bandit problems, we know the ...
- 61
1
vote
0
answers
91
views
How to solve the following continuous optimization problem?
Consider a function $f: X\times Y\times N$, where $X, Y \subseteq \mathbb{R}^m$ are convex sets, and $N = \{1,2,\dots,n\}$. We additionally know that
$f(\cdot,y,S)$ is convex for fixed $y,S$
$f(x,\...
- 25
1
vote
0
answers
32
views
Reference showing global optimality of local minima for matrix factorization
Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized.
I have heard it ...
- 111
1
vote
0
answers
57
views
Tight estimates on the Lovász and Multilinear extensions of a submodular function
I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear).
Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For ...
1
vote
0
answers
67
views
Average case or beyond worse case analysis for non-convex optimization procedures?
I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature.
It is known that global optimization of non-convex functions is NP-...
- 161
1
vote
0
answers
35
views
How does one know what is not in a certain class of pseudo-distributions?
We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis.
Now say one has found a degree $...
- 1,443
1
vote
0
answers
474
views
Optimization as LP on the convex hull of its solution space
I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem (...
1
vote
0
answers
222
views
Properties of the subgradient method
The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule
$$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and
$\alpha(t)$ is a ...
- 775
1
vote
0
answers
186
views
Maximizing a convex function with linear constraint
The problem is
$$\max f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$
where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$,
$\mathbf{x} = [x_1,x_2,...,x_N]...
- 111
0
votes
0
answers
95
views
How to prove that a given class of convex programs cannot be solved by linear programming?
Given the following program, where $f, g$ are convex functions:
$$
\text{minimize}~~ f(x)
\\
\text{subject to}~~ g(x)\leq 0
$$
the problem can be solved by convex programming algorithms, but it would ...
- 2,078
0
votes
0
answers
72
views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
- 265
0
votes
0
answers
81
views
When can convex optimization be considered to be exactly solvable?
If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of ...
- 1,443
0
votes
0
answers
125
views
LP solver for sparse, PSD and strictly diagonally dominant matrix
I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for ...
- 386
0
votes
0
answers
145
views
Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe
Boyd and Vandenberghe say that a convex optimization problem is one of the form:
minimize $f_0(x)$ subject to
$$f_i(x)\le 0, i=1,\ldots m$$
$$a_i^\top x=b_i, i=1,\ldots p$$
...
- 87
0
votes
0
answers
127
views
Extended Formulaiton and Integer Programming
An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints
$Ex + Fy = g, y\geq 0$
in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices ...
- 549