# Questions tagged [convex-optimization]

The tag has no usage guidance.

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

115 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$$...
157 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.)
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 ...
858 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,...
278 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 ...
164 views

I am interested in a quadratic program of the form $$\min x^T Q x$$ $$s.t.$$ $$Ax \leq b$$ where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $... 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 ... 6 votes 3 answers 806 views ### Neural Networks: what's the point of learning features that don't linearly separate? Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input. In such cases, the input set is linearly inseparable, so the optimisation problem that ... 6 votes 1 answer 155 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 ... 6 votes 0 answers 99 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 ... 5 votes 1 answer 485 views ### Gradient descent-like optimization on a convex landscape with noisy sampling We have a strictly convex function$f(x,y)$with a global minimum at$p_{min}$. The goal is to approximate the minimum. E.g. $$f: [0,\pi]^2 \to \mathbb{R}$$ $$f(\theta,\phi) = t_1 \sin \theta + t_2 ... 4 votes 2 answers 190 views ### On facets of 01-polytope 0,1-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ... 4 votes 1 answer 179 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 ... 4 votes 1 answer 66 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, \... 4 votes 1 answer 200 views ### Active learning for inferring a convex optimization formulation I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation. As a specific example, I am thinking of ... 4 votes 0 answers 100 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, ... 3 votes 2 answers 3k views ### Minimizing the maximum dot product among k unit vectors in an n-dimensional space 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 ... 3 votes 1 answer 183 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$... 3 votes 1 answer 796 views ### Objective function for stochastic optimization Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective$\parallel Ax-b \parallel_2^2$, we ... 3 votes 1 answer 873 views ### Maximizing a convex function with linear constraints I have the following optimization problem: $$\arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\} \mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq 1,\... 3 votes 1 answer 229 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}\... 3 votes 1 answer 108 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 ... 3 votes 0 answers 59 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 ... 3 votes 0 answers 101 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(... 3 votes 0 answers 101 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,\... 3 votes 0 answers 75 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 \... 3 votes 0 answers 81 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? 3 votes 0 answers 98 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 ... 3 votes 0 answers 187 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 ... 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 ... 3 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 ... 3 votes 0 answers 270 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 ... 2 votes 1 answer 193 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 ... 2 votes 1 answer 229 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 ... 2 votes 1 answer 927 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(\... 2 votes 1 answer 281 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 ... 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,$\...
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$ ...
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}...