The tag has no usage guidance.

learn more… | top users | synonyms

14
votes
2answers
1k views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
13
votes
1answer
815 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 (...
8
votes
2answers
189 views

Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
8
votes
1answer
468 views

Convexity and efficient algorithms.

[Edit 21 July 2011: I edited the question to ask for more examples] This question is asking for documented discussion of or more examples of a heuristic observation. Some mathematical problems that ...
7
votes
1answer
294 views

Information theory and convex optimization

I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
6
votes
1answer
265 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 ...
6
votes
1answer
126 views

Bounds on the size of the solution of a quadratic program

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
3answers
314 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
0answers
87 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 ...
6
votes
0answers
119 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 ...
5
votes
1answer
268 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 ...
5
votes
1answer
200 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 ...
5
votes
0answers
558 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.)
4
votes
1answer
185 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 ...
4
votes
0answers
38 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 ...
3
votes
2answers
145 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 ...
3
votes
1answer
347 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
1answer
475 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
0answers
121 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}...
3
votes
0answers
45 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
0answers
70 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
0answers
175 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
0answers
77 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
0answers
530 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 ...
2
votes
2answers
1k 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 ...
2
votes
1answer
113 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
1answer
411 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 ...
2
votes
1answer
238 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
1answer
268 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
0answers
85 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 ...
2
votes
0answers
215 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 ...
1
vote
1answer
132 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....
1
vote
2answers
1k 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 ...
1
vote
1answer
102 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
1
vote
1answer
117 views

Looking for algorithm (or at least name) for this optimization problem

Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$. Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$ The ...
1
vote
1answer
138 views

direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

Is there a direct conversion between gradient descent ([1], Alg 1 ) and any of the following algorithms? 1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm 2) ...
1
vote
1answer
172 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....
1
vote
1answer
684 views

Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
1
vote
1answer
293 views

why are the constraints in the following paper tight?

My question is about the following paper: http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf In section 2 they show Equation 3 (which is just an optimization problem), which ...
1
vote
0answers
80 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 ...
1
vote
0answers
68 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 ...
1
vote
0answers
122 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
0answers
270 views

Confusion related to L1 and L2 svm [closed]

I have this confusion related to L1 and L2 svm. It is given in this paper that The dual problem is given by $$ min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha $$ subject to $$ 0 <= \alpha_i &...
1
vote
0answers
176 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 ...
1
vote
0answers
172 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]...
0
votes
1answer
206 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
0
votes
0answers
13 views

Approximability of convex programming (convex optimization)

Apologies for multiple posting (also posted at cs.SE), but I think this question is more relevant here at cstheory: Convex optimization is defined here. The problem is NP-hard. But is anything known ...
0
votes
0answers
88 views

An approximate optimization algorithm

Let $f(n)$ be the number of bits for representing natural number $n$: $f(n) = \lfloor \lg n + 1 \rfloor$. I am looking for an efficient algorithm for the following problem: Input: $w_1, w_2, \cdots, ...
0
votes
0answers
63 views

Approximate $\gamma_2$ norm of a matrix in standard SDP form

The $\gamma_{2}$ norm of a matrix $A\in\mathbb R^{m\times n}$, a well-known measure of matrix complexity, is defined in its matrix-factorization form as $$\gamma_{2}(A):=\min_{XY^{T}=A}\|X\|_{2\...
0
votes
0answers
68 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 ...