Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

1
vote
0answers
23 views

Converting a norm-computation SemiDefinite program to standard SDP form.

I'm trying to express this norm-computation semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$ $$\gamma_{2}^{\epsilon}(A):= \min\,t\,\, subject\, to\, \left( ...
1
vote
0answers
20 views

Boyd & Vandenberghe's proof that all simplexes are polyhedra.

On page 33 of B&V's convex optimization book, during the proof that any simplex can be represented as a polyhedron, they discuss a $n \times k$ matrix $B$ with full column rank and conclude that: ...
0
votes
0answers
52 views

matrix optimization in diagonal and orthonormality constraint

I'd like to solve the following optimization problem. Y is a CxN matrix A is a CxC and diagonal matrix Q is a CxC and orthonormal matrix X is a CxN matrix $$ min_{A,Q} {|| Y − AQX ||}^2_F $$ The ...
0
votes
0answers
15 views

Convexity of Maximum Inscribed Ellipsoid Problem

I am confused about the problem of finding the ellipsoid of maximum volume inscribed in a polyhedron as discussed in section 8.4.2 of Convex Optimization by Boyd and Vandenberghe. I've followed the ...
1
vote
0answers
33 views

Logarithmic Function Behaivour

I have read about Logarithmic function. We can use the second-order condition to show that the $f(x)=\log_2(1+x), x \geq 0$ is a concave function. Now, is $g(x)$ a concave function? How can I prove ...
1
vote
0answers
45 views

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in ...
0
votes
0answers
11 views

Two way partitioning problem's lower bound

In the two-way partitioning problem (as laid out in Slide 7 here), as an example, one possible value for $\nu$ is $-\lambda_{min}(W)1$ which gives the bound as $p^* \ge n\lambda_{min}(W)$. My ...
14
votes
6answers
5k views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: ...
3
votes
3answers
81 views

How to find a counter example for non convexity?

Consider a simple function $f(x,y)=\frac{x}{y}, x,y \in (0,1]$, the Hessian is not positive semi definite and hence it is a non convex function. However, when we plot the function using Matlab/Maxima, ...
0
votes
0answers
24 views

Optimization related to reduced SVD

The reduced SVD of $B_{m\times n}$ is $USV^T$ and we know the columns of $U$ and $V$ are orthonormal. $e_i$ is the $i$th standard basis vector. I want to know the range of the following optimization ...
0
votes
1answer
29 views

Combinatorial Convex Optimization: Russian paper

I'm looking for an electronic version of the paper: David Yudin and Arkadi Nemirovski. Informational complexity and effective methods of solution of convex extremal problems. Economics and ...
2
votes
1answer
39 views

Convolution of convex function and Gaussian is convex

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, i. e., for all $x_1, x_2 \in \mathbb{R}$ and $t \in [0, 1]$, $$ \qquad f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2).$$ I want to prove that the ...
1
vote
0answers
14 views

Condition on linearly separable datasets

I am trying to understand linear classification with hyperplanes. So far I understood that for a binary classifier with labels $y_i \in \lbrace -1, 1\rbrace$ points $(x_i, y_i)$ are separable if ...
3
votes
1answer
81 views

Climbing a hill with increasing & concave marginals. As you climb, do all coordinates go to $\infty$?

$f_1,\dots,f_N:\mathbb{R}^+\rightarrow\mathbb{R}^+$ are strictly increasing, bounded functions whose derivatives monotonically decrease to $0$ as their argument increases. (Picture the shape of the ...
0
votes
0answers
27 views

Is this objective function with exponentiated parameters convex?

I'm working on a function fitting problem. I have fixed basis functions $B_0, ..., B_M$ and parameters $t_0,...,t_M$ and I want to solve the least squares problem of minimizing $$\sum_i\left(y_i - ...
0
votes
2answers
34 views

Proving f cannot be convex

The following question I encountered in a convex optimization course and I can't seem to understand the solution.
1
vote
1answer
16 views

Non convex objective in SVM

In the formulation of svm.. The line underline says the norm of the vector w is a non convex constraint.. But how is this so.. Isn't norm a convex function.. Also aren't the other objectives ...
1
vote
1answer
23 views

Extension of co-coercivity in strongly convex functions

I am studying strongly convex functions and they mention if $f(x)$ is strongly convex with Lipschitz gradients $L$, which means $\parallel \nabla f(y) - \nabla f(x)\parallel \leq L\parallel x - y ...
0
votes
1answer
24 views

Monotonic optimal value function

Are there any theorems/sufficient conditions about when the optimal value function of a parametrized optimization problem is monotonic in the parameter? Specifically, are there simple conditions ...
2
votes
0answers
26 views

Is it possible to use regularization to minimize the (expected) number of non-zero digits in a number?

This question may be slightly related to this question on length of the representation of a number in a certain basis. Introduction / Background In image and video coding, particularly the ...
0
votes
2answers
42 views

Finding the optimal value in an optimization problem

Given the optimization problem $$\text{minimize}\ f_0(x_1,x_2)$$ $$\text{subject to}\ 2x_1+x_2 \ge 1$$ $$x_1+3x_2 \ge 1$$ $$x_1 \ge 0, x_2 \ge 0$$ Let the objective function be $f_0(x_1,x_2) = x_1^2 ...
1
vote
0answers
27 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
0
votes
0answers
19 views

convex optimization with multiple nonsmooth terms

Is there a general algorithm for solving $$ \min f(x) + g(x) + h(x) $$ where all three functions are convex and proximable, $f(x)$ is smooth, and $g(x)$ and $h(x)$ are both nonsmooth? Note that if ...
0
votes
1answer
25 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
1answer
30 views

Proximal operator to Huber function

I want to solve the following problem: $$ \arg\min_x |x|_\mu + \frac{1}{2\sigma} |x-x^k|^2 $$ , where $$|x|_\mu = \begin{cases} \frac{|x|^2}{2\mu}, & |x|<\mu \\ |x|-\frac \mu 2 & |x|\geq ...
2
votes
3answers
48 views

Convexity of a non linear optimization problem

I have a non linear optimization problem, namely: $$\min {\sqrt{(x-u)^2 + (y-v)^2 + (z-w)^2)}}$$ How can i show that the above function is convex. Doing via Hessian is a difficult task.
0
votes
1answer
12 views

Hessian of function regarding convexity

Consider the function $f(x,y) = xy$ for $x,y>0$. Isn't $f$ a convex function? I computed the Hessian to be a matrix with only off diagonal entries equal to one and others zero. For any vector $z$ ...
5
votes
2answers
393 views

Optimization problem using Reproducing Kernel Hilbert Spaces

I am encountering a problem concerning Reproducing Kernel Hilbert Spaces (RKHS) in the context of machine learning using Support Vector Machines (SVMs). With refernece to this paper [Olivier ...
0
votes
0answers
23 views

Nonlinear Optimization

I have a nonlinear optimization problem, but constraints are ODE. Cost function is $J= x1+x1*x2+x1^2$ while constraints are, $\underline{x_i} < x < \bar{x_i}$ (for i=1,2,3) ; ...
0
votes
2answers
30 views

SVD with Sparisty Penalties

I am trying to solve a problem like $$\min_{u,v} \Vert X-uv^T \Vert_F^2 + \beta \Vert v \Vert_1 \mbox{ s.t. } \Vert u \Vert_2 \le 1$$ where $X \in \mathbb{R}^{N\times N}$, $u, v \in ...
0
votes
0answers
27 views

Convex optimization of a fractional objective function involving matrix determinants

I am interested in convex representation of the following fractional optimization problem. I have also described my approach in the following. However, as I am new to convex optimization, I am not ...
0
votes
1answer
10 views

Weighted sum does not necessarily conserve convexity

Does anyone know a counterexample to show that a weighted sum of convex sets is not necessarily convex, unless our coefficients are positive? A weighted sum for me is defined as: $$\alpha C_1 + \beta ...
0
votes
0answers
11 views

Analytical or “simple” enough solution for the following probelm

Define: $$ B(y) = \rho \sum_{i=1}^n \left [ -\log(1-y_i) - \log(1+y_i) - y_i a_i \right ] $$ Where $\rho, a$ are parameters. I wish to solve the following optimization problem quickly, and I ...
0
votes
0answers
32 views

Understanding ADMM: how is it applied to this particular problem?

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
1
vote
1answer
41 views

Prove Jensen Inequality holds for a function

Given function $$f:\mathbb{R}^n_{+} \rightarrow \mathbb{R}, \ f(x) = \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}$$ Show that for any $x, y \in \text{dom} \ f, \theta \in [0,1]$, ...
1
vote
1answer
28 views

Inequality with three unknowns

Consider: \begin{equation} \Big(e^x-1\Big)\mathbb{1}_{(x\geq0)} \leq \lambda_1+\lambda_2e^x + \lambda_3x^2 \end{equation} where $\lambda_1$, $\lambda_2$, $\lambda_3$ are three unknown constants. By ...
0
votes
0answers
20 views

Does Slater's condition for both primal and dual imply compactness of dual solution set?

Consider a convex optimization problem (P) and its dual problem (D). If the solution set for (P) is compact and Slater's condition holds for both (P) and (D). Is the solution set for (D) compact? My ...
4
votes
1answer
146 views

Gradient of the dual function for a nonlinear program

I'm attempting to find a proof for a property from Floudas' Nonlinear and Mixed-Integer Optimization book. Consider a nonlinear optimization problem of the form \begin{align} \min_{{\bf x}}&\quad ...
0
votes
1answer
27 views

Continuity of Parameterized Optimal Solution

Suppose for every $y$, $f(x,y)$ is strictly convex in $x$. Further, $f(x,y)$ is continuous in $y$. Let $\mathcal X$ be compact (in my problem, $\mathcal X$ is an interval). Can anyone suggest any ...
0
votes
1answer
19 views

What is the maximum of the following function?

Let $f(x,y) = \frac{xy^\alpha}{x+y},\alpha\in(0,\infty)$. How to compute $$\sup_{(x,y)\in[a,b]\times [0,c]}\frac{xy^\alpha}{x+y},$$ with $b>a>0$?
0
votes
1answer
38 views

Convex function (vector composition rule)

I'm looking at the Boyd & Vandenberghe slides on Convex Optimization. In slide 18, it applies the rules of vector composition on an example to say that it is convex. The example given is ...
0
votes
1answer
26 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
2
votes
1answer
46 views

Are posynomial functions convex?

I know that you can transform a posynomial function into an exponential function, which is convex. Does this imply that all posynomial functions are convex?
0
votes
0answers
11 views

Find the dual problem to a quadratic program

Consider the quadratic program: minimize $x_1^2 + 2x_2^2 - x_1x_2 - x_1$ subject to $x_1 + 2x_2 \leq u_1, x_1 - 4x_2 \leq u_2, 5x_1 + 5x_2 \leq 1$ Could anyone explain to me how to find the dual ...
1
vote
1answer
48 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
1
vote
0answers
39 views

How to prove that unnormalized neg entropy is strongly convex with respect to 1-norm?

the unnormalized negative entropy of $\mathbf{x} \in \mathbb{R}^n_+$ is $$ g(\mathbf{x}) = \sum_i (x_i \log(x_i) - x_i) $$ it is stated that $g(\mathbf{x})$ is strongly convex with respect to 1-norm, ...
0
votes
0answers
29 views

What non-convex functions be written as the $\min$ of multiple convex functions?

I am working on an optimization framework that can be used to optimize objective functions that can be written as the $\min$ of several convex functions. I was thinking about the generality of this ...
0
votes
0answers
14 views

Explain the dual problem to D-optimal design problem

Given the following D-optimal design problem $$ \text{minimize } \log \det (\sum_{i=1}^p x_i v_i v_i^T)^{-1}\\ \text{subject to } x \geq 0, {\bf{1}}^T x = 1 $$ Find the dual problem. I don't ...
0
votes
0answers
25 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
3
votes
1answer
50 views

About a definition of “rank” of a matrix.

I am familiar with the definition of rank of a matrix as either (1) the maximal number of linearly independent rows or columns or (2) as the dimension of the image of the matrix. Another ...