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

learn more… | top users | synonyms

1
vote
2answers
53 views

Finding Lagrange multiplier

Suppose I'm looking for $\mathbf{x} \in \mathbb{C^{M\times 1}}$ such that: $$\mathbf{x}=\text{arg}\min_\mathbf{x}\|\mathbf{a+Ax}\|_2^2+\lambda\|\mathbf{x}\|_2^2~,$$ where $\mathbf{a}\in ...
1
vote
2answers
45 views

What is the relation between these two definitions of an ellipsoid

There are two definitions of an ellipsoid in Boyd's book (Convex Optimization) $E = \{ x | (x-x_c)^T P (x-x_c) \leq 1 \}$ In the above, P is a positive semi definite matrix. $ E=\{ x_c+Au |\; ...
1
vote
4answers
81 views

Optimization of a quadratic function with qudratic constraints

I'm a Graduate student of Electrical Engineering. I have some basic knowledge on Convex Optimization. For my research, I cam across the following optimization program. With $\mu > 0$, find $\arg ...
1
vote
1answer
251 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
1
vote
3answers
59 views

Questions about coerciveness and convexity

I just have a few yes/no questions, and would really appreciate if you could correct me where I am wrong, and for what fundamental flaw I have. 1. Would the set of coercive functions a linear space? ...
1
vote
1answer
61 views

Proving convexity using the Hessian

Suppose I have $f: \mathbb{R}^n \to \mathbb{R}_\infty$ which is twice continuously differentiable, on some convex set C, which is open. How can I prove that $f$ is convex over C, iff the hessian ...
1
vote
1answer
475 views

Does every strongly convex function has a stationary point?

Say does every differentiable $\mu$-strongly convex function $f:\mathbb{R}^n\mapsto\mathbb{R}$, with $\mu>0$ have a point where its gradient is $0$? If not so which is the minimum you can impose ...
1
vote
2answers
98 views

Why is any subspace affine?

I am studying 'Convex Optimization' written by Stephen Boyd. I am confused by an assertion in the book(page 27). Any one can tell me why and give an explanation ? Any subspace is affine, and a ...
1
vote
2answers
93 views

How to check for convexity of function that is not everywhere differentiable?

I have a question. I have just been introduced to the subject of convex sets and convex functions. I read this in wikipedia that a practical test for convexity is - to check whether the 2nd ...
1
vote
2answers
79 views

How to solve this optimization problem? (may be gradient descent?)

I have the following optimization problem. $$\operatorname*{argmax}_{w} \|(1-w)\boldsymbol{X} -w\boldsymbol{Y}\|^2 \\ s.t. \quad 0<w<1 $$ How can I find the solution of this problem? May be ...
1
vote
2answers
73 views

multi-objective optimization

I am currently encounterring a optimization problem. The goal is optimize an objective function A and B at the same time. But the problem is that optmizing A will almost always tradoff with B, such ...
1
vote
2answers
70 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where ...
1
vote
1answer
52 views

Is $f(X) = \| Y - XX^T \|_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
1
vote
2answers
425 views

Maximization of a log det function

I want to solve the following optimization problem $$ \text{maximize } f(X) = - \log \mathrm{det}(X+Y) - a^T (X+Y)^{-1} a \\ \text{subject to } X \succeq W, $$ where the design variable $X$ is ...
1
vote
2answers
265 views

Composition of non-monotonic convex function

Given the following composition of functions: $h:\Bbb R^k\rightarrow\Bbb R$ $g:\Bbb R^n\rightarrow\Bbb R$ $f(x)=h(g_1(x),g_2(x),...,g_k(x))$ There are known rules which guarantee ...
1
vote
1answer
161 views

Free software or algorithm for Second-Order Cone Program

I need to solve the following optimization problem: $$ \mathbf{x}^\ast = \operatorname{argmin}_{\mathbf{x}} \Vert \mathbf{Rx} \Vert_2^2 \;\;\; \mathrm{s.t.} \;\;\; \mathbf{s}^\mathrm{H} \mathbf{x} = ...
1
vote
2answers
221 views

What is the motivation behind strong convexity

Definition : A function is said to be $\beta$-strongly convex if, $f(\theta w + (1-\theta) w') \le \theta f(w) + (1-\theta) f(w') - \frac{\beta}{2}\theta(1-\theta)(w-w')^2$ What is the motivation ...
1
vote
2answers
100 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
1
vote
2answers
1k views

A question dealing with the convexity of functions involving the absolute value

Just beginning to learn convex analysis and optimization, I have some inquiries to make with regard to the absolute value function $f(x)= |x|$. This function is clearly convex, but since we know that ...
1
vote
1answer
159 views

Convex Sets Versus Convex Functions

Can we specify all convex sets, in terms of convex constraints (convex inequality functions) on a variable?
1
vote
2answers
779 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
2answers
42 views

Minimising a convex set. Is set of solutions convex?

We are minimising a convex function on a non-empty set defined by linear constraints (equalities and inequalities). $X^O$ is the set of all optimal solutions and we assume it is non-empty. Is it true ...
1
vote
1answer
70 views

Subderivative of $ ||Au||_{L^{\infty}} $ to compute proximal operator

I am looking for ways to compute the subderivative of $ ||Au||_{L^{\infty}} $, as I want to solve the minimization problem of \begin{equation} \min\limits_u \quad \lambda ||Au||_{L^{\infty}} + ...
1
vote
1answer
137 views

Optimization problem involving, $L_2$, $L_1$ norm and constraints.

Can somebody suggest me how to solve the following optimization problem? \begin{equation*} F(\mathbf{w},\xi)= \begin{aligned} & \underset{\mathbf{w,\xi}}{\text{minimize}} & & ...
1
vote
1answer
93 views

Arc length function of a helix/spiral is convex?

Given the arc-length of a parametric curve, $\int_a^b\|\gamma'(t)\|$ if the parametric curve was non-convex, can the arc length be a convex function?If the parametric curve was convex, will the arc ...
1
vote
2answers
67 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
1
vote
2answers
75 views

proving that $\text{aff}C-\text{aff}C\subset\text{aff}\,(C-C)$

In proof of Theorem 6.4.1 of Auslender's book about asymptotic cones, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that ...
1
vote
2answers
230 views

(Updated) Geometric Illustration of Monotone and Maximal Monotone Maps

I am writing a note about the Monotone and Maximal Monotone maps from the following book http://link.springer.com/book/10.1007%2Fb97594 In this book we read a map ...
1
vote
2answers
131 views

Proving Lipshitz continuous over a convex set with Projection Operator

Suppose a problem $$\min_{x \in \mathbb{R}^{n}} f(x)$$ subject to $x \in \Omega$ which is a closed and convex set. If $\nabla f(x)$ is Lipschitz continuous in $\Omega$, then prove that $$e(x) = x - ...
1
vote
1answer
32 views

Weighted Norm Minimization

I have a minimization problem of the form $min (w_1 \|x\|+w_2\|y\|)$ subject to constraints $A_1x=b_1$, $A_2y=b_2$, $0< l_1 \leq x \leq u_1$ and $0< l_2 \leq y \leq u_2$ where ...
1
vote
1answer
38 views

How does $\in$ behave with simple algebra dealing with sub gradients?

I was trying to understand the following optimization problem: $$argmin_{v \in H} {R(v) + \frac{1}{2}||v - w||^2}$$ Assume $R(v)$ is Convex, proper and semi-continuous with a unique minimizer. ...
1
vote
3answers
406 views

Compact set in R that is not convex?

Just need an example. For example, the I know the set [0,1] is compact because it is obviously closed and bounded. But I have no idea how to test for convexity
1
vote
1answer
98 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
1
vote
2answers
196 views

Free solvers in C/C++ for convex integer programming

I need to solve the following integer program: $\text{minimize } \sum_{i=1}^n(a_{i0} x_i + \sum_{k=1}^3 a_{ik}w_i^k + \sum_{j=1}^m d_{ij}y_{ij})$ $\text{subject to}$ $$ \sum_{i=1}^n y_{ij}=1, \quad ...
1
vote
2answers
42 views

When solving convex problem, why we don't just find the optimal of the cost function and project it back to the feasible set

I know that is wrong, because if it is right people would not develop so many algorithms. But why? Can I ask for some examples illustrating this does not guarantee optimal?
1
vote
1answer
68 views

Why is $L_0$ norm not convex? [closed]

I have this confusion in understanding the convexity of the $L_0$ norm. Why is $L_0$ norm not convex?
1
vote
2answers
130 views

Formulation and computation of “the” unique median of an even-sized list

Consider an even-sized set of numbers $X = \{x_k\}$, such as $X = \{1, 2, 7, 10\}$. The median $m$ is defined as: $$m = \mathrm{arg \min_x} \sum_k \lvert x_k - x\rvert^1$$ Any $m \in [2, 7]$ is a ...
1
vote
3answers
45 views

Constraint to unconstraint optimization problem by subsitution

Given the following convex optimization problem $\min_{x,p} ||x|| - p$ subject to $p > 0$ Can I change the above to an unconstrained convex optimization problem by substituting $c = ...
1
vote
2answers
188 views

formulating the dual for an instance of a SOCP with linear constraints

I have an optimization problem with second-order cone constraints and linear inequalities and inequalities (shown below). I want to formulate the dual, but have been having trouble. ...
1
vote
1answer
50 views

Optimization of several cost functions together

Say I want to minimize several functions together: $$\min \lVert f_1\rVert, \min \lVert f_2\rVert, \min \lVert f_1-f_2\rVert$$ where $\lVert f\rVert$ is the $L_2$ norm of $f$. I am wondering can I ...
1
vote
1answer
175 views

how to construct the Lagrangian dual problem?

The primal optimization problem is, \begin{align*}\min_x\;&f_0(x)\\ \text{s.t.}\;&f_i(x)\le0\\ &h_j(x)=0\end{align*}, to construct the dual problem, I form the Lagrangian, ...
1
vote
2answers
1k views

proximal operator of infinity norm

What is the proximal operator of $\|x\|_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
2answers
61 views

Minimize the function

Minimize the function $$f(x) = (ax+b)^2 \left(\frac{c}{x} + d\right),$$ where $a , b , c \text{ and } d$ are all positive constants and $x$ is the variable. Thanks and regards
1
vote
1answer
1k views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
1
vote
2answers
1k views

Carathéodory's theorem

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$" In every proof I found, it ...
1
vote
1answer
163 views

directional derivative sublinear of a convex function sublinearity problem to show

How to show the following: If $f:\mathbb R^d \rightarrow \mathbb R$ is convex then its directional derivative is sublinear? Thank you...
1
vote
2answers
160 views

Removing redundant half-spaces that bound a convex polytope

I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 ...
1
vote
1answer
202 views

How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
1
vote
2answers
970 views

Null space of a matrix

I was referring to this lecture http://www.stanford.edu/class/ee364a/videos/video05.html (about 0:38:10) related to convex optimization and for optimization it had a certain affine function equality ...
1
vote
1answer
294 views

Maximizing a function by finding derivative

I want to find the value of $\vec{p}$, $p_s$, $p_t$ each of which is a function of the form $f:\mathbb{R}^2 \to \mathbb{R}$ that maximize the following function : $$\begin{align} \int_\mathbb{R^2} ...