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

learn more… | top users | synonyms

0
votes
1answer
20 views

Does optimal solution always occur at a vertex?

Is it true that if LP $ \text{max} \{c^Tx \ | \ Ax \leq b \}$ has an optimal solution, then $\exists$ a vertex which is simultaneously an optimal solution for LP? I know this works for LP of a ...
2
votes
0answers
34 views

Dual Decomposition with multiple coupling constraints

This is probably a a simple question, but have been stuck on this for a while and unable to figure out my issue from the standard Boyd/Vandhenbergen decomposition references. I am interested in dual ...
2
votes
2answers
49 views

Interpreting norm definition

Book: Convex Optimization (Author: Stephen Boyd), Appendix A, Topic: A.1.2 Norm,distance, and unit ball Can anyone please help me in understanding the following definition of "norm" $$ \| x \| ...
0
votes
0answers
35 views

LP in standard form

I don't know how to properly named this question but here it goes: Let $x, c \in \Bbb{R}^n$, $b \in\Bbb{R}^m$, $A \in \Bbb{R}^{m \times n}$. Consider LP in the form: min $\{c^tx : Ax = b, x \ge 0\}$ ...
0
votes
1answer
25 views

Proximal operators on Balls (Projection)

I was following this tutorial, In section 21 it is given Proximal operator over a ball $B_\epsilon$ of radius $\epsilon$ as $$\text{Proj}_{B_\epsilon(y)}(u) = y + (u-y) \max({1 , ...
1
vote
1answer
54 views

Showing convexity proof

Let $F: \mathbb{R}^n \rightarrow \mathbb{R}^m$ be an affine function, i.e., $F (x) = L(x) + b$, with $L : \mathbb{R}^n \rightarrow \mathbb{R}^m$ linear and $b \in \mathbb{R}^m$ Then for every convex ...
1
vote
0answers
14 views

Is epi(max(f,g)) the intersection of epi(f) and epi(g)?

On an exam, I found the question "is max($f(x),g(x))$" convex if $f,g$ are convex? This lead me to the question in the topic. Is the intersection of epi$(f)$ and epi$(g)$ = epi($\max(f,g)$)? If so, ...
0
votes
2answers
53 views

How to solve the function $\max \sum_{i=1}^n \log(x_i \cdot \mu)$ with $\sum _{j=1}^b \mu_j = 1$

$$ \max_{\mu} \sum_{i=1}^n \log(x_i \cdot \mu)\qquad\text{with}\qquad \sum _{j=1}^b \mu_j = 1,\qquad \mu_i \ge 0,\qquad x_{ij} \ge 0 $$ The function is shown as above, where $x_i$ and $\mu$ are ...
2
votes
0answers
98 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
1answer
28 views

Dual part of complementary slackness

The proof of the complementary slackness of P: min $c^Tx $ @ $Ax = b, x \geq 0$ D: max $b^Ty $ @ $A^Ty \leq c$ Goes something like $c^Tx = b^T y = y^TAx \Leftrightarrow c^Tx-y^TAx = 0 ...
3
votes
0answers
40 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
1
vote
0answers
37 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
0
votes
1answer
37 views

Model logical constraints without binary variables?

Is it possible to express "either $f(x) \leq 0$ or $g(x) \leq 0$" where $f,g$ are linear constraints by using a finite number of continuous constraints/new variables, WITHOUT breaking convexity or ...
0
votes
1answer
39 views

Optimization problem with an added quadratic inequality constraint

Consider the following (non-convex) optimization problem on the real variables $\lambda_\ell^\pm$ with $\ell=1,\ldots,n$ \begin{align} \mbox{maximize}&\quad ...
2
votes
1answer
61 views

What is the motivation behind the, convex and concave closures of submodular functions?

What is the motivation behind the , convex and concave closures of submodular functions? Also, my understanding is that the submodularity condition is somewhat like concavity which makes it counter ...
1
vote
1answer
119 views

Scale ellipsoid maximally within polyhedron

Given an ellipsoid around the origin with scaling parameter $e$ in the form $x^T E x \leq e$ and a polyhedron $P$ given by $A x \leq b$, how can we define an optimization problem that maximizes e such ...
1
vote
0answers
20 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
2
votes
1answer
51 views

Minimum Distance between a Triangle and a Distance Field 3D

I am looking for (possibly numerical) solution to this geometric problem: Given a filled 3D triangle $T = \text{conv}(p_1, p_2, p_3) \subseteq R^3$, and a distance field $D(x) : R^3 \to R$, what ...
3
votes
1answer
94 views

Closest point on a 3D triangle, is this algorithm correct?

Given a point $P$ and three triangle vertices $U$, $V$, $W$, all in $\mathbb{R}^3$, I need to find the point in the triangle $UVW$closest to $P$. Does the following algorithm work, or have I missed ...
2
votes
1answer
83 views

Solving L1 regularized Joint Least Squares and Logistic Regression

My objective function that is to be minimized is as follows: $f = -\sum_{n=1}^{N}log~p(y_{n}^{a}|x_{n},w) + \sum_{n=1}^{N}(y_{n}^{b}-w^{T}x_{n})^{2} +\lambda\|w\|_1$ The first term models the ...
1
vote
1answer
44 views

SOCP with a norm constraint

Is it possible to convert this optimization problem into a SOCP: \begin{eqnarray} \min && c^T x \\ s.t. && \|A_ix + b_i \|_2 \le c_i^T x + d_i \\ && \| Dx \|_2 = g ...
3
votes
1answer
135 views

Is $\text{Trace}(e^{XA+A^TX})$ a convex function of X?

Is $\text{Trace}(e^{XA+A^TX})$ a convex function of $X$? $X$ is diagonal and positive definite, $A$ is symmetric negative definite definite. And by the way, what is the best way to solve a problem of ...
1
vote
0answers
47 views

Compressed sensing: converse of a theorem

Theorem: Suppose that the signal length $N$ is a prime integer. Let $\Omega$ be a subset of $\{ 0, \ldots , N-1 \}$ and let $f$ be a vector supported on $T$ such that $|T| < \dfrac{1}{2}|\Omega|$ ...
3
votes
0answers
54 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
40 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
105 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
116 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
35 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
57 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
63 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
68 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
28 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
48 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
34 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
34 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
27 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
59 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
74 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 ?