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

learn more… | top users | synonyms

0
votes
0answers
27 views

Number of optimas of product of convex functions

I am dealing with a function, which is a product of two strongly convex functions, and trying to determine the number of its local minimum. For example, I have $$H=f(x)\cdot g(x)$$, in which both $f$ ...
1
vote
1answer
29 views

Is closed convex set with finite number of extreme points convex polyhedron

I have this simple question related to convex set and convex polyhedron. As the content in the title, it's basically my question: Is closed convex set with finite number of extreme points convex ...
0
votes
1answer
17 views

How to interpret the regular condition in this theorem about cones in convex analysis?

Theorem:Let $K_1,\dots, K_m$ be convex cones in $R^n$ and let $K = K_1 \cap K_2 \cap \dots K_m$. If $K_1 \cap int(K_2) \cap \dots \cap int(K_m) \neq \emptyset$(regularity assumption), then $K^\circ = ...
0
votes
0answers
17 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
1
vote
1answer
47 views

Is $-\ln(1+e^x)$ a convex function?

Is $-\ln(1+e^x)$ a convex function? My answer book says no because its second derivative is $-\dfrac{e^{2x}}{(1+e^x)^2}$ but I am sure that it is incorrect. I have that the second derivative is ...
0
votes
0answers
11 views

uniform lower bound for convex combination of a sequence of positive semidefinite matrices

Assume: a sequence of positive semidefinite matrices $A_k^i\in M_{m,n}, m<n$, $i\in\mathcal{N}$, and they have the following property: $$\underline{a}I \leq A_k^i(A_k^i)^T\leq \overline{a}I.$$ ...
0
votes
1answer
25 views

Solving SVM classifier with two weight vectors

I am trying to implement a paper that basically proposes the following way to train two classifiers on some data with two types of labels. I do not know how to tweak existing solvers for SVM to do the ...
0
votes
1answer
20 views

Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal ...
0
votes
0answers
15 views

Slater point and Ideal Slater point

How do we show that an ideal slater point lies in the relative interior of the Feasible set (of a convex optimisation problem)?
0
votes
1answer
22 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
35 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
35 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
55 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
24 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
19 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
32 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
32 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
2answers
60 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
26 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
22 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
35 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
34 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
28 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
34 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
36 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
32 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
35 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
22 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
20 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
37 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)}$ ...
0
votes
1answer
22 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
13 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
32 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
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
0answers
46 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
63 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
72 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
44 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
29 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
41 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
36 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
49 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
23 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
33 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
34 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
26 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
36 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
15 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 ...