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

learn more… | top users | synonyms

1
vote
1answer
60 views

Convexity of a rational function

I am attempting to (dis)prove that the function $$\frac{4x+3y+2}{x^2+xy+2x+y}$$ is convex for $x,y>0$. Attempting to differentiate the function does not seem like a good idea (or am I making a ...
0
votes
0answers
25 views

Prove that dual variables become free variables

Let P: $max\ c^T x$ subject to $Ax\leq b $ Say if we replace the latter part by $Ax=b$. Show the effect on dual problem is that the variables of dual become free variables. Can you break Ax=b ...
0
votes
1answer
32 views

regarding the concept of dual cone

When studying the covex analysis, I am not clear about the concept of dual cone. In the following graph, $\mathcal{K}*$ was the dual cone. I marked two points, the ...
0
votes
1answer
74 views

Convex optimization: affine equality constraints into inequality constraints

I have the following problem: \begin{equation} \begin{array}{cll} \displaystyle \min_{ \mathbf{x} } & & \displaystyle f(\mathbf{x}) \\ \mathrm{s.t.} & & \mathbf{x} \in \mathcal{C} \\ ...
2
votes
0answers
23 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
3
votes
1answer
65 views

Rank one plus diagonal matrix approximation

Given $A \in R^{n \times n}$, $A$ symmetric. I'm trying to solve the following minimization problem: $\underset{u \in R^n, d \in R^n} \min \, \frac{1}{2} \|X - A\|_F^2$ subject to $X = u u^T + ...
0
votes
0answers
31 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
0
votes
1answer
26 views

Can $\min f'x$ s.t. $(a'x - b)^2 \le d $ be written as a SOCP?

It does not appear to be significantly different from the form listed here: http://en.wikipedia.org/wiki/Second-order_cone_programming with (in article notation) $i = {1}$, $ A = a$, and $b$, $d$ as ...
0
votes
0answers
29 views

Prove the existing and uniqueness of a solution [duplicate]

Let function $f$ be differentiable and convex in $R^n$ . How can it be proved that $∀λ>0$ solution of system equations $f ′ (x)=−λx$ exists exclusively (∃and! ).
0
votes
2answers
46 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
1
vote
2answers
74 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 ...
0
votes
1answer
28 views

Is this following SDP problem Convex?

Is the following problem convex function? \begin{eqnarray} \begin{aligned} \underset{\mathbf{X}} {\text{minimize}}\,\,\,\, & \text{Trace}(\mathbf{RX}) \\ \text{subject to} &\\ & ...
0
votes
0answers
24 views

Dual convex pairs

I am currently trying to understand a certain proof. The author uses the term dual convex pair for a pair $(\phi,\psi)$ of convex functions defined on subsets $X,Y$ of $\mathbb R^n$ satisfying: $$ ...
0
votes
0answers
42 views

KKT Conditions and Convexity

min $x^2 -xy +y^2 -5x+6y$ subject to $1 \leq y$, $y^3 \leq 2x$, and $x \leq 8$ Write out the KKT conditions for this problem. Show that $(x,y) = (4,2)$ is a KKT point, and is therefore a global ...
0
votes
1answer
21 views

Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
7
votes
3answers
115 views

Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it. Is group theory useful in any way to ...
0
votes
1answer
69 views

Is there any method that convert a non-convex problem to a convex one?

I have an optimization problem of the form: minimize $\quad f_0(x)$ subject to $\;\;\;f_1(x)\leq0,\quad\quad\quad(C1)$ $\quad\;\quad\;\quad\quad\;f_2(x)\leq0,\quad\quad\quad(C2)$ where ...
0
votes
0answers
18 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
0
votes
0answers
22 views

Log barrier for SDP generalized inequality: positive semidefinite point appears infeasible

Given the optimization problem: minimize $\;\;$ tr$(GX) $ subject to $\;$ tr$(F_i X) = 0 \quad \forall i=1,...,p $ $\quad\quad\quad\quad\;\; X \succcurlyeq 0 $ I know the log barrier ...
1
vote
1answer
66 views

accomodating non-negativity constraint in the dual

Suppose the objective implicitly imposes non-negativity constraint, say, the objective is sum of square roots of the decision variables. Is it necessary to consider the inequality constraints imposing ...
0
votes
1answer
45 views

Homogeneous non-negative least-squares

I would like to least-squares-"solve" a set of linear equations ($\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2$). In my case, $\mathbf{b=0}$, e.g. the system is homogeneous. I also ...
0
votes
1answer
37 views

No free lunch theorems

In James Spall's book, when explaining NFL theorems (http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization}) an example is given. Suppose input space has $3$ elements and output space ...
0
votes
0answers
22 views

dual feasibility question in augmented Lagrangians and the method of multipliers

I am going through Boyd's tutorial on ADMM. My question is basically from Sec 2.3. Consider the optimization problem $$\min.~f(x)~~~~\text{s.t.}~~~Ax = b.$$ Then the Lagrangian is ...
0
votes
0answers
14 views

Linear Programming error bounds question

We have the LP problem: Maximize $P=3x+2y$ subject to $$-x+3y \leq 2+r_1$$ $$x+y \leq 8+r_2$$ $$2x-y \leq 10+r_3$$ What would be the formula for $P(r)$ in terms of $r=(r_1, r_2, r_3)$ for the ...
1
vote
2answers
57 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 ...
0
votes
1answer
27 views

Semi-Infinite Linear Programming: Why is the infimum attained?

I have an optimization problem of the following form: $$\min c^T \lambda\\ \text{s.t. } f(x)^T \lambda \ge g(x) \text{ for all } x \in E,$$ where $E$ is an arbitrary set, $c \in \mathbb{R}^n, f ...
1
vote
1answer
49 views

Projection onto a convex closed set

H, If $K$ is a non-empty convex and closed subset of a uniformly convex Banach space $X$ (Hilbert for example) and $v \notin K$, we know that there exists a unique $k_0\in K$ such that ...
0
votes
1answer
24 views

Decreasing Function Projected onto Simplex

Consider $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$, defined as $f(x) := a x + b$, where $a<0$ and $b \in \mathbb{R}_{\leq 0}^{n}$. Note that $f$ is decreasing: $$ x \geq y \Longrightarrow f(x) ...
0
votes
1answer
53 views

Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?

Consider the assignment problem: $$ Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} $$ s.t. $$ \sum_i x_{ij} = 1 \quad\forall j $$ $$ a \leq \sum_j x_{ij} \leq b \quad\forall i $$ $$ ...
1
vote
2answers
52 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
1
vote
0answers
31 views

Infinity norm minimization

I am wondering how to minimize an objective function of the following form: $$\min_{\mathbf{x}\in\mathcal{R}^{MN}} \|\mathbf{x}-\mathbf{y}\|_\infty + \lambda\mathrm{TV}(\mathbf{x})$$ Here, ...
1
vote
1answer
63 views

Showing a function is concave

Given $F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2))$ on $S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\}$ with $A,B,a\in\mathbb{R}$, show that $F$ is concave on $S$. Since we have ...
1
vote
3answers
45 views

How to find a counter example for non convexity?

Consider a simple function $f(x) = \frac{x}{y}, x,y \in (0,1]$, the Hessian is not positive semi definite and hence it is a non convex function. However, when we plot the function using Matlab/Maxima, ...
0
votes
0answers
56 views

Lagrange dual method and KKT condition

Consider the following optimization problem \begin{equation}\notag \begin{split} \max & x^2+y^2 \\ \mathrm{s.t.} & x^2 \leq 1 \\ & 0\leq y\leq 2 \end{split} \end{equation} Obviously, the ...
0
votes
0answers
14 views

Objective Value of LP as a function of RHS of Constraints

I saw the following statement in a paper, but am having trouble finding a reference for it. Consider the optimization problem $y = \max_x c^\top x$ subject to $Ax = b$ and $x \ge 0$. Then, written as ...
0
votes
0answers
26 views

Convex set of polynomial coefficients

Assume we have an infinite order polynomial $f(L)=1-L\theta_1-L^2\theta_2-L^3\theta_3-...$. and we know all roots of this polynomial cite outside the unite circle. It is obvious that latter condition ...
0
votes
0answers
15 views

Effect of proximal projection using a divergence measure, on the maximizer of the function

Suppose we have a probability distribution $p(\mathbf{x})$ and we know : $$ \mathbf{x}^* = \arg\max_{\mathbf{x}} p(\mathbf{x}) $$ Suppose we do a projection of this distribution onto another family ...
0
votes
1answer
30 views

Transform unconstrained optimization problems into constrained ones?

I want to formally show that the following minimization problem $$ \min_\theta||\max(0,f_1(\theta)),...,\max(0,f_n(\theta))||^2 $$ is equivalent to $$ \min_{\beta, \{w_i \}^{n}_{i=1}} ...
0
votes
1answer
21 views

Convex min proof.

Suppose $f$ is convex and $x^*$ is a minimizer, and $x^* \in [a,b]$, and let $c,d$ be values such that $a < c < d < b$. Then i) $f(c) \leq f(d) \implies x^* \in [a,d]$ ii) $f(c) ...
1
vote
1answer
29 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
3
votes
2answers
164 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
0
votes
1answer
20 views

On the Composition of simple Projections

Consider the compact convex set $X = \{ x \in \mathbb{R}^n \mid x \geq 0, \ \underline{1}^\top x = 1 \}$. I am wondering if the projection onto $X$ is the composition of the projection on $[0,1]^n$ ...
1
vote
1answer
38 views

Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$ x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b $$ where $X \subset \mathbb{R}^n $ is a non-empty, convex, bounded polyhedron. ...
1
vote
1answer
34 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
0
votes
1answer
201 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
2
votes
1answer
54 views

Got stuck with this $L^2(-1, 1)$ optimization problem. Any ideas where it comes from?

Statement Let $u(x) \in L^2(-1, 1)$. Solve the following optimization problem: $$ \begin{cases} J(u) = 4 \int_{-1}^{1} \sqrt{|x| (1 - |x|)} u(x) dx + \left(\int_{-1}^1 \sin(3\pi x) u(x) dx\right)^2 ...
1
vote
0answers
25 views

Interpreting constraints in an optimization problem

I am working on an optimization-based image denoising project in which I have three "flavors" of an optimization problem, one constrained and two unconstrained. They are given as follows: ...
1
vote
1answer
32 views

Is a constrained optimization problem equalivant to its Lagrangian form?

For the following problem: $\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$ Is the above problem equalivant to the following problem? $\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$ where $t$ and ...
0
votes
1answer
44 views

What's the solution for $\max_{x\in(0,1]}: \{-1-x\}$

What's the solution for the following optimization problem? Is the constraint set convex? $$\max_{x\in(0,1]}:\{-1-x\}$$
0
votes
1answer
27 views

Convex Subset Projection

Suppose that C is a closed convex subset of $\mathbb R^n$ and $x \in \mathbb R^n$. The projection of $\mathbf x$ onto C is the closest point $\mathbf y \in C : \mathbf z = \mathbf y$ minimizes ...