# Questions tagged [convex-optimization]

The tag has no usage guidance.

73 questions
Filter by
Sorted by
Tagged with
2k 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 (...
1k views

114 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$$...
149 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 ...
2k 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.)
128 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 ...
765 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,...
274 views

### Complexity of max problem

Consider the problem $\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$ where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem ...
148 views

78 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?
89 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 ...
185 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 ...
80 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 ...
1k 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 ...
265 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 ...
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let, \alpha = \max_{1 ... 1answer 132 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 ... 1answer 179 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 ... 1answer 722 views ### On the stopping criterion of coordinate descent method I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion. Consider the optimization problem \begin{equation} \min f(\... 1answer 275 views ### Linear programming, a non standard handling of absolute value This is really a basic (undergrad) question in LP but still i would like to clarify it for myself to be sure. I have a minimization problem from the sort \min \sum_i |x_i| s.t Ax \le b. I've seen ... 0answers 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, \... 0answers 63 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 ... 0answers 159 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}... 0answers 190 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 ... 0answers 156 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 ... 0answers 116 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 ... 1answer 250 views ### Greedy vs LP Approximation I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g.... 2answers 3k views ### Derive logitboost using the logistic loss function An additive model constructed using the exponential loss functionL(y, f (x)) = \exp(−yf (x)) gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ...
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$ ...