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

learn more… | top users | synonyms

3
votes
0answers
53 views

Proving or disproving concavity of a function

I want to prove that the following function is concave (as a part of another proof). $$f(p) = \max_{\begin{matrix}x,y\\0\le x \le 1\\0\le y \le 1 \\ x * y = p\end{matrix}} \lambda h(x) + ...
0
votes
0answers
23 views

Proving that two problems are strongly dual when solutions are restricted to a space

Consider the following problems with solutions $\mathbf{w}\in\mathbb{R}_{++}^n$ \begin{align} (P) \hspace{.3in} \min_{\mathbf{w}} \hspace{.3cm} & \mathbf{p}^H\cdot\mathbf{w} \\ \text{s.t. } & ...
0
votes
0answers
38 views

Non-decreasing Convex function?

When my textbook states, "Non Decreasing Convex Function", does it mean that the function is convex and increases in y for every x from its minimum? That is if f(x) = y is convex. Please explain if ...
2
votes
0answers
101 views

Strong duality for nonconvex quadratic program (with multiple constraints)

Consider the following optimization \begin{eqnarray} P_1: \quad &\underset{x\in\mathbb{C}^N}{\mathrm{minimize}}&\; f_0(x) \\ &\mathrm{subject\;to}&\; f_i(x) \leq 0, i=1,\ldots,m \\ ...
1
vote
1answer
19 views

Conjectured characterization of a set relative to a convex cone

Let $X\subset \mathbb{R}^N$ be a convex cone (i.e., for all $x,y\in X$ and $\alpha,\beta\geq 0$ scalars, $\alpha x+\beta y\in X$). Define the set $$A(x)=\{a:x+a\in X \wedge x-a\in X\}.$$ Then, ...
3
votes
1answer
27 views

Global optimality of a convex but non-smooth function

I have a question. The answer may be too obvious but I cannot be sure about the right answer. Let say that we have a convex but non-smooth function which is defined as $f : \mathbb R^2 → \mathbb R$. ...
1
vote
1answer
30 views

Positive Semidefiniteness on off diagonal pertibation

If $X$ is a positive semi-definite matrix and $Y$ is symmetric satisfying $X_{i,i}=Y_{i,i}$ and $ |Y_{i,j}| \leq |X_{i,j}| $ for all $i,j$ , is $Y$ necessarily positive semi-definite?
1
vote
0answers
114 views

Dynamic programming problem for discrete linear time varying system

I'm working on a linear time varying discrete(LTV) multi input multi output(mimo) system. I formulate the problem description in the following way $$x_i(k+1) = x_i(k)\cdot A_i(k) + B_i(k)\cdot ...
1
vote
0answers
32 views

How nuclear norm is convex whereas weighted nuclaer norm is not?

In (http://nuit-blanche.blogspot.in/2014/05/wnnm-weighted-nuclear-norm-minimization.html), it is stated that nuclear norm of a matrix $\mathbf{X}$, given as $||\mathbf{X}||_{*}=\sum_{i} ...
0
votes
1answer
51 views

Convex conjugate of a function of sum of norms

I am trying to find the conjugate of function $f(x) = \|x\|_2 + \frac{1}{2} \|x\|_2^2$ i.e., $f^*(v) = \sup_x (v^Tx - f(x))$ where $x \in\mathbb R^n$ Although $f(x)$ is convex, I am stuck as the ...
2
votes
1answer
62 views

Formulation of convex constrained optimization problem (SVR)

I'm trying to figure out where I'm going wrong with my formulation of a certain problem, as all other instances of it were formulated slightly differently. The problem (SVR problem, If you're ...
0
votes
0answers
25 views

What is the complexity of Simplex Method's Phase 1?

What are the average and worst-case complexities of the Phase 1 of the Simplex Algorithm? Is it respectively polynomial and exponential as well? Google search did not yield any results unfortunately. ...
2
votes
1answer
66 views

Normal Cone of $\mathbb{R}^n_+$ and $S^n$?

I'm trying to solve the problem $\min_x \{f(x) + \delta_X(x)\}$ where $f$ is a differentiable function and $\delta$ is the indicator function $\delta_X(x) = \begin{array}{l}0, x \in X \\ ...
1
vote
0answers
30 views

Entropy proerty

Let $a,b,c>0$ be distinct postive reals. Define four different probability distributions: $$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$ ...
1
vote
0answers
27 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
0
votes
1answer
15 views

Convexity preservation and global optimality

This is a question I've had a tough time getting a good answer to. Consider the problem to minimize $f(x)$. Assume $f$ is differentiable and nice in every way, but we do not know if $f$ is convex. A ...
1
vote
2answers
44 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 - ...
0
votes
0answers
33 views

What does coordinate descent actually do?

We've done a bunch of theoretical stuff in my optimization class, but basically no time for the actual implementation details. I'm trying to get an understanding of coordinate descent, which if I'm ...
0
votes
0answers
30 views

Convex optimization with groups

I am relatively new to convex optimization and am looking to solve a resource allocation problem. I understand, that if my utility function is concave the following problem constitutes "an ...
0
votes
0answers
33 views

Is the ratio trace problem convex?

I have a ratio trace problem described as follows: $\arg\max_{w} trace((w^tAw)*inv(w^tBw))$, where A and B are full rank matrices. This problem can be solved via generalized eigenvalue problem. ...
1
vote
1answer
38 views

Efficient solution for a quadratic + norm objective.

I want to minimize an objective function of the following form: $$ \begin{split} \text{Minimize} \quad & x^T D_x x + y^T D_y y + z^T D_z z + q_x^T x + q_y^T y + ...
2
votes
0answers
21 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
1
vote
1answer
26 views

KKT for not convex problems

In my optimization course we learned something about KKT for not konvex problems: $$min \; f(x)$$ $$s.t. \; c(x)=0$$ $$d(x)\geq 0$$ $$f(x): \mathbb{R}^n\rightarrow \mathbb{R}$$ $$c(x): ...
1
vote
0answers
32 views

Minimization using logarithmic barrier function

I'm thinking of the quadratic problem(QP) \begin{align} &\underset{x\in \mathrm{R}^n}{\mathrm{Minimize}}\ \ \ \frac{1}{2}x^\top{}Qx + f^\top{}x\\ &\mathrm{subject\ to}\ \ \ \ a_ix \leq b_i\ ...
0
votes
0answers
54 views

How does this optimization problem satisfy Karush-Kuhn-Tucker Conditions?

I am following Andrew Ng's course notes on Support Vector Machines at: http://cs229.stanford.edu/notes/cs229-notes3.pdf There is something in these notes which I do not understand. SVM's basic ...
3
votes
2answers
71 views

Intuition about gradient

https://en.wikipedia.org/wiki/Gradient Gradient is a vector which we can obtain from any differentable function taking its partial derivatives. From Wiki: "...the gradient points in the direction of ...
0
votes
1answer
42 views

How to prove that a cone is closed?

How to prove a cone $K$ is closed ? I know that $K$ is a set, for a set, if it is not open, then it is closed. But how to prove that it is closed directly ?
1
vote
2answers
110 views

Prove this function is convex

we have $ g: R^n \rightarrow R$ is a concave function and $S$={$x :g(x)> 0$} and $f:S \rightarrow R$ and $f(x)$=$1/g(x)$ so we must show that $f$ is a convex function
0
votes
0answers
37 views

Minimization of a weighted least-squares problem by Lagrange multiplier method

Problem: Let $Y = (y_1, y_2, \dots, y_m) \in \mathbb{R}^{m \times n}$ and $k \in \mathbb{R}^{m}$ satisfy $\sum_{i=1}^{m} k_i =1$ and $k \geq 0$. Show that $x=Yk$ is a minimizer for $h(x) = ...
0
votes
2answers
59 views

Parameter optimization using a regression model.

I am working on an optimization problem. I build a regression model to understand the behavior of a system which depends on two variables which are functions of another two variables. My regression ...
0
votes
0answers
15 views

Polar cones' property [duplicate]

I am trying to prove: $A \subseteq B \implies B^\circ \subseteq A^\circ$ where $A^\circ$ is polar cone of $A$ ($A$ convex cone) and $B^\circ$ is polar cone of $B$ ($B$ convex cone)
1
vote
0answers
51 views

Conic hull of outer products

Consider the set of rank-k outer products, defined as $\{XX^T | X \in R^{n\times k}, rankX = k \}$. Describe its connic hull in simple terms. I have found the solution of this exercise but I have ...
1
vote
1answer
36 views

What does 'the level set is bounded' exactly want to tell?

'The level set is bounded.' occurs in many theorems and other places. I think I can understand the definition of 'level set' but I don't know what does 'it's bounded' want to tell me exactly in ...
0
votes
0answers
26 views

Are these functions convex functions?

$f_i(z) = f_i(x,y) = y_i^\alpha - x_i$, where $x,y \in R^n$, $z = (x, y)$, $\alpha \in R$ and $\alpha > 1$, $i = 1, \dots, n$. Are these functions convex functions ? For $f_i$, the gradient is $ ...
0
votes
1answer
47 views

How to show these two problems have equivalent solutions

I have two problems, where $A$ is positive definite: $$\inf \{ x^TAx + b^Tx : 1-x^Tx \ge 0,\ x \in \mathbb R^n\} \ (1)$$ and $$ max_\lambda \ q(\lambda) = -0.25b^T(A+\lambda I)^{-1}b - \lambda : ...
0
votes
0answers
26 views

Property of monotone operator (Positive definite)

I would like to prove this statement: "$F$ is monotone if and only if $\nabla F$ is positive semidefinte." I only know $F$ is monotone with respect to $\Omega$ if and only if ...
1
vote
2answers
67 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
0
votes
1answer
41 views

Find those values 'a' which belongs to the Convex Hull

Find those values of 'a' for which (1,a,1) belongs to the convex hull of $$\{(0,0,0), (1,1,2),(2,4,-6), (1,3,8)\}$$ Give me hints as much as you can, I would like to understand the mindset rather ...
2
votes
1answer
131 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
0
votes
1answer
50 views

Conditions for unique solution of a maximization problem?

Let $S\subseteq \mathbb{R}^2$, $d:=(d_1,d_2) \in S$, and $s:=(s_1,s_2)$ a generic point of $S$. Assume that there exists $s \in S$ such that $s_1>d_1$ and $s_2 >d_2$. Consider the following ...
2
votes
1answer
42 views

Is there Lipschitz property for subdifferential?

I'm trying to bound the quantity $\langle \nabla \Psi(x),\bar{x}-x \rangle$ above, with the bound depending on $\|x-\bar{x}\|$ and perhaps also of $\|x-y\|$ for fixed (but not varying) points $y$. ...
0
votes
0answers
15 views

How to work with difference-of-elements penalty in optimization

I am trying to solve the optimization problem $$\min_{H,S>0} \|W(H+S)-X\|^2_F+Q(H)+\eta\|S G\|_F^2$$ where $X\in\mathbf{R}_+^{m\times T}$, $W\in\mathbf{R}_+^{m\times k}$, ...
2
votes
2answers
88 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...
2
votes
1answer
31 views

What is the solution for this quadratic program?

Given scalars $p_1\geq p_2\geq \cdots \geq p_r > 0$, can we find a solution for following problem? \begin{align} \text{minimize} & & & \sum_{j=1}^{r} p_j (1-t_j)^2 \\ \text{s.t.} \\ ...
2
votes
0answers
47 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
1
vote
1answer
30 views

Show that scalar-valued function of a matrix is convex

Consider the mapping $$f(X) = g\left(\frac{b}{a^TXa}\right),$$ where $g$ is a convex function, $b$ is a strictly positive scalar, $a$ is a real vector, and $X$ is restricted to be symmetric and ...
1
vote
1answer
28 views

What is the definition of “convex” and “relaxation” concepts in clustering?

I have following text from a paper i am trying to understand: I don't understand what does below sentence refers to as being convex/non-convex The problem is that even though the objectives ...
0
votes
0answers
17 views

reference request for solution to SDP is an extreme point

I'm looking for a reference which establishes that the optimal value for a standard SDP is attained at an extreme point. For instance, this is noted below Theorem 1.2 of ...
0
votes
0answers
26 views

convexity of function built from piecewise linear convex function?

Let $B(x):[0,1] \rightarrow [0,1]$ be piecewise linear increasing convex function with $B(0)=0$ and $B(1)=1$. (Think of the power of the neyman-persron test). Let $E(x)=-log(B(1-e^{-x}))$ a logaritmic ...
0
votes
1answer
38 views

Quadratic Program reformulation

I have the quadratic program $$\max\quad \mu^Tx+r_fx_0-\gamma \sum\limits_{i=1}^n |x_i-y_i|-\frac{\lambda}{2}x^TVx$$ $$\text{s.t. }\quad \mathbb{1}^Tx+x_0=1$$ where $\mu$, $r_f$, $\gamma$, $\lambda$, ...