Questions tagged [convex-optimization]
The convex-optimization tag has no usage guidance.
91
questions
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
0
votes
1
answer
67
views
Solving non-linear programming with large number of variables
Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem:
$$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$
$$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
- 226
2
votes
2
answers
114
views
Linear Programming Sensitivity to Matrix
Consider a linear program in the following standard form:
\begin{align*}
&\max c^T x &\\
&\mbox{subject to:}\\
&A x \preceq b\\
&x \succeq 0
\end{align*}
Its dual is
\begin{align*}...
- 226
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
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 ...
- 83
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
3
votes
1
answer
210
views
Can the ellipsoid method be used with a randomized separation oracle?
Suppose we are trying to solve the following optimization problem:
$$
\text{maximize } ~~ c\cdot y
\\
\text{subject to } ~~ y\in S
$$
where the region $S$ is described by an exponential number of ...
- 91
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
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
3
votes
1
answer
109
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 6,979
4
votes
1
answer
188
views
Restriction of a convex function to {0, 1}^n
Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
- 6,979
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
22
votes
1
answer
3k
views
Solving semidefinite programs in polynomial time
We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
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
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
3
votes
1
answer
234
views
An optimization problem
I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
- 136
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
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
3
votes
1
answer
115
views
Parametrized complexity of sparse optimization
Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
- 4,011
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 ...
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
3
votes
0
answers
135
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
-1
votes
1
answer
74
views
Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$
Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
- 551
2
votes
1
answer
237
views
Is the Chi-square divergence a Bregman divergence?
Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as
$\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$?
If so, what is the potential ...
- 5,840
8
votes
2
answers
4k
views
A Question on Convex Conjugate Duality for KL Divergence
The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
- 41
10
votes
3
answers
742
views
When is the duality gap of semidefinite programming (SDP) zero?
I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?
For example, when one goes back and forth ...
- 18.1k
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
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, ...
10
votes
1
answer
1k
views
Is convex optimisation in P?
Consider a convex optimisation problem in the form
$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$
where $f_0, f_1, \...
CommunityBot
- 1
4
votes
1
answer
67
views
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \...
- 5,772
1
vote
2
answers
3k
views
Derive logitboost using the logistic loss function
An additive model constructed using the exponential loss function
$$L(y, f (x)) = \exp(−yf (x))$$
gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ...
CommunityBot
- 1
6
votes
1
answer
163
views
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
- 9,595
1
vote
1
answer
419
views
Optimal value of a semidefinite program
Is a local optimum value of a SDP always the global one?
If not, what are the conditions for that?
- 9,595
6
votes
1
answer
917
views
Analytic solutions in semidefinite programming (SDP)
From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
10
votes
2
answers
587
views
What can be solved with semidefinite programming that can't be solved with linear programming?
I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I ...
8
votes
1
answer
583
views
Is the feasible region of this SDP polyhedral?
We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral?
We believe this to ...
3
votes
1
answer
207
views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
- 5,772
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
-3
votes
1
answer
126
views
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
Consider the feasibility quadratic program with constraint
$$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$
$$\vdots$$
$$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$
$$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
- 101
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
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
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
1
answer
96
views
Properties of convex polytope of 0-1 matrices
Problem setting
Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$.
Consider a $k\times k$ matrix $M$ ...
- 1,429
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
1
vote
0
answers
88
views
Do nested convex bodies have increasing "Volume/Surface Area" ratios? [closed]
Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$. Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$?
It's true in all ...
- 19
6
votes
1
answer
1k
views
The Average-case Complexity of Simplex Algorithm
I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
CommunityBot
- 1
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}...
1
vote
1
answer
192
views
Poly-time Algorithm for Non-Linear Optimization
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this notion....
- 161
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
2
votes
1
answer
258
views
When can a convex function induce submodularity?
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
- 644