0
votes
0answers
16 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
10 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
0
votes
1answer
24 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
0
votes
0answers
16 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
0
votes
1answer
30 views

Minimizing a non-convex rational function of two variables

I need to minimize the following function $$f(x,y)= \frac{a}{x}+\frac{bx}{y}+\frac{cy}{x}+dy+\frac{e}{y}$$ where $a,b,c,d$, and $e$ are positive constants, and $x$ and $y$ are both strictly positive. ...
0
votes
1answer
27 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
3
votes
3answers
133 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
1
vote
1answer
107 views

Knuth's Sandwich Theorem: requesting proof clarification

The question is about F6 of Section 8 ("Elementary facts about cones") in Donald Knuth's Sandwich Theorem (http://arxiv.org/pdf/math/9312214.pdf). He claims to prove $(A \cap B)^* = A^* + B^*$ when ...
0
votes
1answer
36 views

Strong convexity of a function with cases

Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function \begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align} ...
1
vote
1answer
57 views

New variable in a convex optimization problem

Consider the convex optimization program $$ \min_{x \in X } x^\top P x + p^\top x \quad \text{ sub. to: } Ax = b $$ where $X \subset \mathbb{R}^n$ is compact, $P \succ 0$, $A \in \mathbb{R}^{m \times ...
0
votes
0answers
30 views

Proof of sufficient condition of existence of Lagrange multipliers

Consider the optimization problem $$ (P) \quad \inf\{ f(x) : g_i(x) \le 0, i = 1,\ldots, m, x \in \mathbb R^m \} $$ where $f, g_i : \mathbb R^n \to (-\infty, \infty]$ are convex and $0 \ne ...
0
votes
1answer
37 views

Sufficient condition on convex function such that $f(x) > -\infty$ for all $x$.

Let $f : \mathbb R^n \to [-\infty, \infty]$ convex and let $f(\overline x) > -\infty$ for $\overline x \in \mbox{int}(\mbox{dom}(f)$. Show that $f(x) > -\infty$ for all $x \in \mathbb R$. ...
0
votes
1answer
34 views

The convexity of convex function's range

Given a convex function $f\colon X \to \mathbb R$ with convex domain $X \subseteq \mathbb R^n$, is the range of $f$ a convex set also?
2
votes
1answer
58 views

Solving $ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$

Let $\phi \in \mathcal ( [0,1]^2)$ symetric , can we find a solution to the following minimisation problem? $$ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$$ with $$ ...
0
votes
1answer
31 views

Dual norm equivalence?

$\|\|$ is a norm in $R^n$, its dual norm is defined as $\|s\|^*=max_{\|x\|=1}s^Tx$. We denote $s^\#$ as any vector in the following set: [Arg $max_x: \ \ s^Tx-\frac{1}{2}\|x\|^2$] How to verify ...
2
votes
2answers
42 views

function induced by optimization

Consider the following optimization $\displaystyle\max_{x_1, \ldots, x_n}\sum_{i=1}^n x_i y_i -\sum_{i=1}^n x_i\log(x_i)$ subject to $a_i\leq x_i\leq b_i$ and $\sum_{i=1}^n x_i =c$ ...
1
vote
1answer
24 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where ...
0
votes
2answers
56 views

Regularization vs. Inequality Constraint

For what values of a regularization parameter $\alpha$, there is an equivalent inequality constraint in convex optimization? In particular, in the convex optimization problems below $$ \text{ Problem ...
0
votes
1answer
35 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
84 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} \\ ...
0
votes
2answers
48 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} ...
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
41 views

Minimization of product function subject to constraints

I want to minimize the following function: $\prod_{i=1}^{n}{x_i}$ Subject to the following constraints: $\sum_{i=1}^{n}{x_i}=1.1+(n-1)(0.1)$ and $0.1 \leq x_i \leq 1.1$ How should I go about it? ...
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
64 views

Convexity of LASSO

I would like to know if some variables in design matrix are correlated then LASSO is convex or not. If you give me a proof for convexity of LASSO and ADAPTIVE lasso, I will be thankful. LASSO is ...
3
votes
2answers
170 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 ...
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. ...
2
votes
1answer
59 views

Existence of global minimum

Could someone help me with this problem? Let $C$, $D$ convex and closed sets such that the intersection is empty. I want to show that the function $f: \mathbb{R^n} \to \mathbb{R}$ defined by $f(x) = ...
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\}$$
1
vote
0answers
41 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
1
vote
0answers
35 views

Quickly checking if an inequality holds on a convex region

Let $C$ be a given convex polygon in $\mathbb{R}^2$ containing the origin and let $a$, $\mathbf{b}$, and $Q\succeq0$ be a given scalar, vector, and matrix respectively. Is there a fast way to verify ...
0
votes
2answers
80 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
0
votes
0answers
64 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
0
votes
1answer
48 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
0
votes
0answers
36 views

Total Variation minimization problem

Thanks for reading this thread. I have a object function, with constraints, I am trying to minimize. The object function is the Total Variation of an image. The Total Variation is defined as: ...
2
votes
1answer
102 views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le ...
1
vote
2answers
51 views

Minimizing a convex cost function

I'm reviewing basic techniques in optimization and I'm stuck on the following. We aim to minimize the cost function $$f(x_1,x_2) = \frac{1}{2n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 ...
0
votes
1answer
12 views

Conic hull of a proper function

Suppose $f$ is a proper function pn $\mathbb{R}^{n}$with $f(0)>0$.Now consider $$ g(x) = \text{inf}\{t: (t,x) \in \text{cl(cone(epi(}f)))\} $$ Can I always say that $\exists y \in \mathbb{R}^{n} : ...
0
votes
1answer
76 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
0
votes
1answer
56 views

Relax equality into inequality in convex problem

Let $\mathbf{x}, \mathbf{z}, \underline{\mathbf{x}}, \overline{\mathbf{x}} \in \mathbb{R}^{I}$, where the first two are variables and the last two are given data. I have the following problem: ...
1
vote
1answer
43 views

Minimizing difference and individual variables in convex problem

Let's say I have the following optimization problem: $$ \begin{align*} \min_{\mathbf{x},\mathbf{y}} & \sum_i x_i-y_i \\ \mathrm{s.t.} & \{\mathbf{x},\mathbf{y}\} \in ...
0
votes
1answer
34 views

Prove that the intersection of convex sets is convex using the following three points…

I want to prove each point, then, use points (1) and (2) to prove (3). $C_{1} = \lbrace x \in \mathbb{R}^{n} \mid h(x) = 0 \rbrace $ is convex iff $h(x)$ is affine in $C_{1}$ $C_{2} = \lbrace x ...
1
vote
2answers
192 views

Why is this weighted least squares cost function a function of weights?

Here is a picture from my book regarding weighted least squares: Totally lost here, so I extracted the main nested issues confusing me: First Question: I know that in any LSE we want to minimize ...
0
votes
1answer
82 views

Largest eigenvalue of symmetric matrix

I am trying to understand why the $\lambda_{\max}$ function is convex given an $n\,x\,n$ symmetric matrix, let's call it $A$. I know from elementary property of eigenvalues that all the eigenvalues of ...
2
votes
1answer
62 views

“Support function of a set” and supremum question.

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly. As an example, my ...
0
votes
2answers
60 views

Inequality involving max is confusing me.

I am trying to understand one line in a derivation here. Simply put, the statement is that: $$ max\{\theta \ f_1(x) + (1-\theta) \ f_1(y) \ , \ \theta \ f_2(x) + (1-\theta) \ f_2(y)\} \leq \theta \ ...
1
vote
1answer
53 views

Examples of affine functions and convex sets

I'm just learning about convexity and affineness, and I've read over some similar questions asked here, but those were more about general properties. I need some help applying those properties to a ...
0
votes
2answers
78 views

Is the geometric-to-arithmetic function convex or concave?

Consider a vector $\mathbf{x} \in \mathbb{R}_{++}^N$. Also consider two functions, $g(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, and $a(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, ...
0
votes
3answers
145 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...