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

learn more… | top users | synonyms

0
votes
1answer
26 views

Does the non-expansion property of the projection operator hold for all definitions of norm?

For convex problem, of course. I vaguely remember this holds for weighted norm also. But I am curious if there are some general conclusions about what kinds of norm will fit in this framework?
1
vote
3answers
45 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
1
vote
0answers
39 views

Scaled proximal operator for proximal Newton method

The scaled proximal operator was introduced as an extension of the (regular) proximal operator: $prox^H_h(x) = \arg\min_y h(y) + \frac{1}{2}\|y-x\|^2_H$. (See ...
0
votes
1answer
60 views

Is $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ concave? [closed]

I want to maximize the capacity function $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ with respect to $F$, subject to the constraints: (1) $\operatorname{trace} F \le Pt$ (2) ...
0
votes
1answer
30 views

Is this a concave function?

Suppose $\gamma \in R^{1}$ and $\beta \in R^{k}$. Let $f(\gamma,\beta) = (y_{2} - \gamma y_{1}) - (y_{3} - \gamma y_{2}) \exp(x^{\prime}\beta)$. Then is $f$ a concave function of ...
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 ...
1
vote
0answers
33 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
1
vote
1answer
35 views

Is this convex minimizer a continuous function?

Consider the function $g: \mathbb R^n \rightarrow \mathbb R$ given by: $$ g(x) = \arg\min_{y\in\mathbb R} \sum_{i=1}^n f_i(|y - x_i|) $$ where $f_i$ are convex, strictly increasing and continuous. ...
3
votes
3answers
79 views

Is there an efficient way to evaluate the proximal operator of $f(x) = \|x\|_2 + I_{\geq 0}(x)$?

Is there an efficient way to evaluate the proximal operator of the function $f:\mathbb R^n \to \mathbb R \cup \{ \infty \}$ defined by \begin{equation} f(x) = \| x \|_2 + I_{\geq 0}(x), \end{equation} ...
1
vote
1answer
31 views

Proof convexity of Logarithmic function

Prove that: $\ln(e^{x+y} +1 )$ is a convex function. I have tried to used $F \circ G$, while $F = \ln (t+1)$ and $G = e^{x+y}$ $G$ is convex but I need to prove that $F$ is convex and growing, ...
0
votes
0answers
25 views

How to solve the following convex constrained optimization problem?

\begin{equation}\label{constrained optimization} \begin{aligned} \min\limits_{\mathbf{X}}&\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2 &\ \ s.t. X_{ijk}=M_{ijk}\ \ ...
1
vote
0answers
27 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
0
votes
0answers
43 views

Existence of steepest descent curves of convex functions

Preliminaries. Let $f:\mathbb{R}^n\to\mathbb{R}$ be a convex function. Then for any point $x\in\mathbb{R}^n$ and direction $v\in\mathbb{R}^n$ the directional derivative $\nabla_v f(x)$ of $f$ at $x$ ...
1
vote
0answers
41 views

Quasiconcavity of a product of ratios

Given $f(x_1\ldots x_k) = \dfrac{x_1x_2\cdots x_k}{(x_0+c_1)(x_0+c_2)\cdots(x_0+c_k)}$ where $x_i > 0$, the $c_i > 0$ are constants, and $$x_0 = \sum_{i=1}^k x_i$$ is it true that $f$ is ...
0
votes
0answers
60 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
0
votes
0answers
50 views

Different ways to calculate Lipschitz constant of the LASSO problem

The LASSO problem is well-known problem in ML community given by: \begin{equation} f(x) = \frac{1}{n}\|Ax-b\|^2_2 + \frac{\lambda}{n}\|x\|_1 \end{equation} This equation appears in paper1 on page 9 ...
0
votes
1answer
46 views

Quasiconvexity of linear-fractional composition

In Boyd and Vandenberghe Section 3.3.4, it is stated that compositon of a quasiconvex function with an affine-fractional transformation is quasiconvex. In specific, if $f(x)$ is quasiconvex, then ...
1
vote
2answers
37 views

Linear Functions on Symmetric Matrix Basis

I don't really understand this comment at the end of Boyd's Convex Optimization, Section 1.6. In the following, $S^k$ represents the space of $k \times k$ symmetric matrices. "We usually leave it to ...
0
votes
2answers
36 views

Is the logarithm of sum of multiple variables with the constraint on sum of them Concave?

I know that without any constraint $log \sum_{i=1:1:m} \alpha_i C_i $ is not Concave but I am wondering is this function Concave when we have the constraint that $ \sum_{i=1:1:m} \alpha_i =1 $ and ...
2
votes
0answers
23 views

Can a subgradient always be found in polynomial time?

Given a convex function, under what conditions can we find a subgradient in polynomial time? There are easy examples such as $f$ being an supremum of a finite number of differentiable functions, but ...
1
vote
0answers
24 views

Analytical algorithm to obtain solution to convex optimization problem.

Assume a vector $\vec{P}$ with N elements $\in \mathbb{R}^+$ and constants $T_P$ and $\epsilon$. The vector $\vec{P}$ is arranged in a column $(N\times 1)$. Consider the problem: $$ \begin{aligned} ...
0
votes
0answers
38 views

is this function an ill-shape convex function?

I have a function with parameter $\vec{{\alpha}}$ where it is formulated by the formula: $$ f(D|\alpha)=n_1{\alpha}_{1}+...+n_m \alpha_m -Nlog \sum_{i=1:m} exp(\alpha_{i}+g_i(D)) $$ where $g_i{(D)}$ ...
1
vote
1answer
32 views

Hessian matrix for convexity of multidimensional function

To prove that a one dimensional differentiable function $f(x)$ is convex, it is quite obvious to see why we would check whether or not its second derivative is $>0$ or $<0.$ What is the ...
0
votes
0answers
14 views

What is the moment matrix in converting polynomial optimization problem to a quadratic optimization problem

Happy new year, I have a function of the form below \begin{align} f(x,y,z)=\sum_i x_i y_i z_i + g(x)+h(z)\cr x,y,z \in R^n \end{align} where $h,g$ are quadratic functions. My difficulty lies in the ...
0
votes
1answer
47 views

Linear Optimization Problem with exponential variable

Hey Folks I've encountered an optimization problem which has a linear programming structure but it's coefficients are nonlinear function of another variable. here is the problem: $$\max ...
1
vote
2answers
44 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
0answers
60 views

How to find the tangent cone to a set in a point?

Let $S\in R^{n}$ is a set and $x\in S$. We define tangent cone of $S$ in $x$ as: $$T_{S}(x)=\{z\in R^{n}:\exists (x_{k}), x_{k}\in S, x_{k}\rightarrow x, \exists (y_{k}), y_{k}>0, ...
0
votes
2answers
69 views

How to efficently solve a convex optimization problem with positive semi-definite Hessian matrix?

Consider the following optimization: $$ f(x)= \min \sum_{i=1}^n \left(x_i-\sum_{j=1}^n x_j\right)^2 $$ Let $g_i(x)=x_i-\sum_{j=1}^n x_j$ , then $$ f(x)= \min \sum_{i=1}^n g_i(x)^2 $$ The ...
3
votes
1answer
75 views

Maximize $ 2^{(-x)} + 2^{(-y)}$ subjected to certain conditions

I am reading through convex optimization and I came across this following problem: \begin{align*} \max \text{ } & 2^{-x}+2^{-y}\\ \text{s.t. } & \frac{1}{1+x}+\frac{1}{1+y}\leq b\\ & ...
3
votes
1answer
53 views

minimize frobenius norm

My question is the following: Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...
3
votes
1answer
31 views

First order condition in constrained optimization: Alternative characterization via normal cones

Consider the following constrained optimization: Min $f(x)$, $x\in C\subset R^n$, where C is convex. We know that one characterization of a local minimum (necessary condition) is the following: ...
0
votes
0answers
43 views

LQR Problem Minimization Prove

Given J for an LQR Problem is $J = \frac{1}{2} \int {z_1}^T \hat Q z_1 + v^T Q_{22} v\,dt $ where $\hat Q$ above is given as $\hat Q = Q_{11} - Q_{12}{Q^{-1}}_{22}Q_{21}$ is minimized if we use ...
0
votes
1answer
21 views

Optimization problem: Find shortest distance between two vectors

$$\min (u-v)^T(u-v)$$ $$s.t. \space Ru=p, \space Sv=q$$ where $u$ and $v$ are in $R^4$ and $R$ and $S$ are $3x4$ matrices. When I expanded the expression I got this: $$u^Tu - 2u^Tv +v^Tv$$ Is this ...
0
votes
0answers
47 views

Maximizing Frobenius norm

I was wondering if anybody has any suggestions on the following problem: Let S be an $n \times n$ real symmetric matrix and $W$ is a real matrix of size $n\times d$; $1\leq d <n$. $$ \text{Find ...
0
votes
0answers
51 views

How to reshape a nonlinear inquality into a linear matrix inequality?

We have these two nonlinear inequalities (I): $$x^2+y^2>0$$ $$3x^2+3y^2-4y^6>0$$ We want to represent this problem as a Linear Matrix Inequality Problem, i.e, we want to derive a positive ...
0
votes
0answers
24 views

Definition for Quasiconvexity

I have been reading through Professor Boyd's book on Convex Optimization. I am pretty new to this field and have some questions regarding quasiconvexity. Based on the definition, a function is ...
0
votes
2answers
37 views

Second Order Cone Program

I am trying to solve the following optimization problem (Problem 9.2) which can be setup as an SOCP. $$ \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & ...
0
votes
1answer
36 views

Is $|x^3|$ convex?

Let $f(x)=|x^3|$ on I=$-\infty,+\infty$ Is this convex? How I did was f(x) = \begin{cases} x^3, & \text{if $x>=0$ } \\ -x^3, & \text{if $x<0$ } \end{cases} Then$ f '(x)$ = ...
0
votes
0answers
31 views

How to solve this convex optimization problem with inequalities constraint?

I am trying to understand how to solve the SVM optimization problem. It is usally written : $$\text{Minimize} $$ $$\|\textbf{w}\|$$ $$\text{Subject to}$$ $$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \geq ...
1
vote
2answers
43 views

Are these two optimization problems equal?

The first optimization model: $$ \begin{array}{cl} \arg \min \limits_{C} & \sum\limits_{i=1}^{3}\gamma_i\|{C_{(i)}}\|_*\\ \mathrm{s.t.} & \|A\mathbf{c}-\mathbf{b}\|_2^2+ ...
0
votes
0answers
21 views

Closed form solution to projection on interior of ellipsoid

This may be a silly question, but is there a closed form solution to the projection on the set $\{y | y^TA^{-1}y\leq d\}$? (Here $A$ is symmetric positive definite.) I got it down to an equivalent ...
2
votes
2answers
55 views

Convert any convex optimization problem to a linear objective

Wikipedia claims that: Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. Is there a ...
0
votes
0answers
20 views

General KKT problem

Consider the following problem, where $a_j,b$ and $c_j$ are positive constants: Minimize 􏰀$\sum_{j=1}^n \frac{c_j}{x_j}$, subject to $\sum_{j=1}^n a_j x_j = b, x_j ≥ 0$ for $j= 1,...,n$. Write ...
0
votes
1answer
60 views

Affine hull smallest affine space

I would like to prove the following statement: "The affine hull is the smallest affine space containing $S$, where $S$ is an arbitrary set". I think the proof is rather trivial, but I cannot find ...
2
votes
2answers
58 views

Convexity of exponential function [closed]

How to prove that the convexity of exponential function? It is not allowed to use second derivative of $e^x$.
1
vote
1answer
59 views

Projection of a real symmetric matrix to a cone (face)

Hi Here is my question: Suppose there is an $n \times n$ real symmetric matrix $X$. It is easy to project it onto the positive semidefinite cone $\mathcal{S}_n^+$. We can just apply the the ...
1
vote
1answer
43 views

Proof of convexity of in a quadratic function

Let $ X= \{(x_1,d_1),(x_2,d_2),...,(x_n,d_n)\}$ where $x_i$ for $i=1,...,n$ are variable and $d_i$ for $i=1,...,n$ have constant values, then we define: $$ F(X) = \min\sum_{i=1}^{n} ...
0
votes
1answer
31 views

Convex set - in $\mathbb{R}^3$

I need to prove $2$ sets, i hope you could help me: $x^2+y^2\leq z^2$ Is that a convex set? $S: 0\leq x_1\leq x_2\leq \cdots\leq x_n.$ I think about sum of convex sets - but not sure. So i woild say ...
0
votes
1answer
35 views

Prove in newton's method

I have to prove, that the direction in Newton's method is a descent direction if the Hessian is positive defnite. My idea: $ direction = -H(x)^{-1}*\nabla f(x)$ Put how can I prove ...
4
votes
1answer
42 views

Prove convexity of three similar sets

given the following 3 sets: $ \{ (x,y,z): x \ge y^2 + z^2, z>0 \} $ $ \{ (x,y,z): x^2 \ge y^2 + z^2, y>0 \} $ $ \{ (x,y,z): x^2 \ge y^2 + z^2, x>0 \} $ The first set is convex because it ...