The convex-optimization tag has no wiki summary.
1
vote
0answers
23 views
Confusion related to minimization of a gaussian likelihood function
I have this confusion related to minimization of gaussian likelihood function. The negative of the log likelihood of gaussian distribution is
$-logdet(Q) + tr(SQ) + \lambda||Q||_{1}$ where Q is the ...
2
votes
0answers
163 views
Confusion related to L1 and L2 svm
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
70 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 ...
1
vote
0answers
76 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 ...
0
votes
0answers
120 views
l1-penalized regression with non-negativity constraints via the “shooting” algorithm
I was curious if anyone can point me at a paper (or some code, or both) about how one can go about enforcing non-negativity constraints when solving an l1-penalized regression problem (specifically ...
1
vote
0answers
120 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
154 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} = ...
2
votes
2answers
209 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 ...
13
votes
3answers
506 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 ...
10
votes
1answer
243 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 ...
1
vote
1answer
193 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 ...
2
votes
0answers
163 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 ...
3
votes
1answer
297 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 ...
8
votes
2answers
176 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 ...
0
votes
1answer
148 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 ...
1
vote
1answer
308 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 ...
6
votes
0answers
112 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 ...
-1
votes
1answer
206 views
Upper bound of an optimization problem
Please let me know whether there are closed-form optimal results (or upper bound) for the following optimization problem:
$$\max (\prod_{1\leq i\leq n}(x_i)^{y_i}-\prod_{1\leq i\leq ...
4
votes
1answer
149 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 ...
1
vote
1answer
284 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 ...
8
votes
1answer
406 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 ...
