Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
0answers
10 views

What is the partial derivative for the L2,1 norm?

I have 2 matrices that I'm wanting to optimize separately. I'd like to take the derivative of each but am getting stuck at the $L_{2,1}$ norm. The $L_{2,1}$ norm is simply $$ G = ||XS||_{2,1} $$ I'm ...
0
votes
0answers
12 views

Solving the quadratic optimization problem with quadratic inequality constraint

I have a quadratic optimization problem which which both objective function and constraint are convex. As the problem is very big, I used decomposition technique and divide the problem to smaller ones ...
0
votes
0answers
23 views

Solving constrained linear programming problem

I have variables $t$ and trying to find best multipliers $k$ which minimizes my objective function. Time: $t_1$, $t_2$, $t_3$,... given in input Multiplier $k_1$, $k_2$, $k_3$,... (These are ...
0
votes
2answers
22 views

Minimize multi-variable function one variable at a time

I am wondering if I can minimize a multi-variable function one variable at a time. In other words, is it true that: $min_{x_1,x_2} f(x_1,x_2)=min_{x_1} min_{x_2} f(x_1,x_2)$
2
votes
0answers
44 views

Functional Maximization

So how do we solve a problem like this: Find the function $s(x)$ such that $s(x)$ maximizes $$\int_0^{s^{-1}(k)} s(x) dx $$ where $x\in[0,10]$, $s(x)\in[0,1]$, and $k\in[0,1]$ ($k$ is a constant). ...
0
votes
1answer
25 views

Critical point - relative minimum

Checking the function $f:\mathbb{R}^2 \rightarrow \mathbb{R}, (x, y) \rightarrow (y-3x^2)(y-x^2)$ we can take an idea for the difficulty of finding conditions that ensure that a critical point is a ...
4
votes
1answer
57 views

Solution to an apparently simple Optimization Problem

I'm stuck at a proof of a property that is stated in a paper. Imagine we have a diagonal matrix $$\Sigma=\begin{pmatrix}\lambda_1& &0\\ &\ddots&\\0&&\lambda_n\end{pmatrix}$$ ...
0
votes
0answers
7 views

I want to find a maximum of a function by Maple. How to restrict the variables to be integers?

For example, I want to find the maximum of $x^2+y^2$ with $0\le x,y\le 10$ in Maple. I can type $$maximize(x^2+y^2,x=0..10,y=0..10).$$ But if I restrict $x$ and $y$ to be both integers, then how can ...
2
votes
3answers
51 views

Finding Extrema of $f(x,y)=x^4+y^4-4xy$

Let $f(x,y)=x^4+y^4-4xy$ How do I find all the relative extrema and saddle points of $f$ which lie within the open square ${(x,y) | -2<x<2,-2<y<2}$. And also if $f$ was in the closed ...
1
vote
0answers
6 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
0
votes
1answer
36 views

How can we continue to get the critical points?

A service requires the dimensions of a rectangle box are such that the length plus twice the width plus twice the height do not exceed $274cm$ ($l+2w+2h \leq 274$). What is the maximum volume of the ...
4
votes
4answers
91 views

Casino turns 50% of your losses into “free play”, are odds in your favor?

As a limited-time promotion, if you gamble during your first week at this casino, and you suffer a net loss of money, the casino will give you half of your losses (up to a certain amount) as "free ...
1
vote
1answer
11 views

Is there a way to find a good lower bound on $\Vert p_n \Vert_\infty$ without finding the extrema?

Let $$p_n(x):=x^n+c_{n-1}x^{n-1}+ \cdots + c_0$$ be defined over some interval $[a,b]$. Is there a way to find a good lower bound on $\max_{x\in [a,b]} | p_n (x) |$ without actually finding the ...
0
votes
4answers
41 views

Which function do we want to minimize?

A ray of light travels from the point $A$ to the point $B$ across the border between two materials. At the first material the speed is $v_1$ and at the second it is $v_2$. Show that the journey is ...
-1
votes
1answer
30 views

Do we have to use the Lagrange multipliers method? [on hold]

Draw a cylindrical container (with a lid), so as to contain $1$ liter of water, using a minimal amount of metal. Could you give me some hints how we could do that?? Do we have to use the Lagrange ...
3
votes
1answer
24 views

Lagrange multipliers method - absolute maximum and minimum

Using the Lagrange multipliers method I have to find the absolute maximum and minimum value of $f(x, y)=x^2+y^2-x-y+1$ in the unit disc. So, I have to find the extremas of $f(x, y)=x^2+y^2-x-y+1$ ...
1
vote
1answer
28 views

Combinatorial optimization problem

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem. If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can ...
2
votes
1answer
21 views

Find numerical minimum of a function with many parameters

I have a function $$f(\vec{r}_1\dots,\vec{r}_N)=\mathrm{The \ sum\ of\ square roots\ of\ the \ eigenvalues\ of\ }\Omega(\vec{r}_1\dots,\vec{r}_N)$$ And I want to find one of its local minima with ...
0
votes
0answers
16 views

Sum of abs of negative eigenvalues divided by sum of abs of all eigen values.If the result is convex?

Let $\lambda_1 (X)\geq \lambda_2 (X)\geq\ldots\geq\lambda_n (X)$ denote the eigenvalues of a matrix $X\in S^n$. Let $f(X)= \sum_{i\colon λ_i<0}|\lambda_i(X)|$ and $g(X)= \sum_i|\lambda_i (X)|$. ...
0
votes
1answer
11 views

Maximization of a statistical property of a subset of random numbers

I have encountered a maximization problem which could be formulated as a discrete mathematics problem arising from statistics, but I don't know where to start or which techniques could be applied to ...
1
vote
0answers
22 views

Hungarian algorithm , Kuhn paper, definition of transfer and theorem 1 proof

http://tom.host.cs.st-andrews.ac.uk/CS3052-CC/Practicals/Kuhn.pdf Is the paper. I am looking at the definition of transfer, essential, inessential and the proof of theorem 1. Consider qualification ...
2
votes
1answer
45 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
0
votes
2answers
24 views

Maximization problem with constraint: no differentiation

$$\max \ \min[\alpha x_1, \beta x_2, \gamma x_3] \ \ \text{s.t.} \ \lambda_1 x_1 + \lambda_2x_2 + \lambda_3x_3 = c, \\\ \alpha, \beta, \gamma, \lambda_i, c \ \text{are constants}$$ Well, that ...
0
votes
0answers
6 views

Sorting signals to achieve highest possible similarty

I am currently trying to develop an algorithm in Matlab that sorts signals, which I have as columns of a matrix, to achieve the highest possible similarity of the signal with its neighbors. My first ...
0
votes
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [on hold]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
4
votes
2answers
197 views

Why do Lagrange Multipliers work?

I know that the Lagrange multiplier method helps us evaluate critical points of $f$ on the closed boundary of the restriction. In other words we solve:$$\nabla f=\lambda \nabla g$$ But why does ...
1
vote
1answer
24 views

Which points in the interior of a parallelogram are as far as possible from the corners?

Question 1: Given a parallelogram $P=ABCD$, how does one construct/determine the points $X \in P$ which are as far as possible from the corners? That is, the points $X$ for which $$ ...
0
votes
1answer
26 views

Gradient in mirror descent

Mirror descent can be in general written as \begin{equation*} \nabla\Phi(x_{t+1})=\nabla\Phi(x_t)-\lambda_t\nabla f(x_t), \end{equation*} where $f$ is the objective function and $\Phi$ is a convex ...
1
vote
1answer
22 views

Dual residual for linearized ADMM

I am using linearized ADMM for a problem with a (non-smooth) convex loss function $f(x)$, and a hard constraint $x \in E$, where $E$ is an ellipsoid in $R^d$. I have encoded the hard constraint as $A ...
1
vote
1answer
35 views

To show that $f(y)$ has only one maximum in $y\in[0,1]$

I have function $$f(y)=\frac{1}{2} y \log \left(\frac{a^2 b \left(\frac{2}{y}-2\right)}{a b \left(\frac{2}{y}-2\right)+a+1}+1\right)$$ where $a,b>0$ and $y\in[0,1]$. I want to show that $f(y)$ ...
2
votes
0answers
28 views

What honeycomb has the highest volume to edge length ratio?

This question is analagous to the Kelvin Problem where the solution, the Weaire-Phelan Structure, has the highest volume to surface area ratio; however, the cell volume is compared to edge length ...
0
votes
1answer
19 views

Proving the existence of multiple maxima

Given a function of two variables, say f(x,y), what are some known techniques to prove that it has multiple maxima? I can see via simulation that this is the case, but trying to figure out a formal ...
0
votes
0answers
20 views

joint optimization problem with somewhat symmetric function

I have just brief question that the method that I use to solve optimization problem is legit. I have function $\max_{x,y}F(x,y)$, and first order condition gives me following equation. ...
1
vote
2answers
43 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
0
votes
1answer
46 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
1
vote
0answers
26 views

Optimization involving convex-concave function

Let $f(x,y)$ be a function defined on $[0,1]^2$ and define \begin{align} g(a,b) = f\left(\frac{a+b}{2}, \frac{a-b}{2}\right) \end{align} where $a$ and $b$ are such that $\frac{a+b}{2} ...
0
votes
1answer
35 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
0
votes
0answers
16 views

Optimization methods to find valleys in a map

I have a map of some size say $1000\times1000$ pixels that is in a equivalent sized array. Instead of searching the map for a global minimum what I'd like to do is find a cluster of connected minimums ...
1
vote
0answers
39 views

Can I clamp singular values of $3\times3$ matrix without effectively computing SVD?

I have a $3\times3$ matrix $A$, and compute its SVD $U \Sigma V^\star = A$. I clamp the singular values in $\Sigma$ to some small range (e.g. $[0.5, 1.5]$ ) and reconstruct matrix $\widetilde{A}=U ...
1
vote
2answers
52 views

proving that $(\text{aff}\,C-\text{aff}\,C)\subset\text{aff}(C-C)$

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
0
votes
1answer
41 views

solving Non-liner optimization with non-liner constraint using fmincon in Matlab [on hold]

I'm trying to solve a non-liner optimization problem with a non-liner constraint by applying fmincon function in matlab. However, I got the following error: "Failure in initial user-supplied nonlinear ...
0
votes
1answer
25 views

How to analysis the global and local maxima of $h(x) = (1-f(x))(1-g(x))$

I want to maximize $h(x) = (1-f(x))(1-g(x))$, where $f(x)=exp(-u(x))$ and $g(x)=exp(-v(x))$ and $u,v \ge 0 $. $h'(x) = -f'(x)(1-g(x))-g'(x)(1-f(x)) = 0$ results to that the points with the ...
1
vote
0answers
12 views

Non linear programming problem using Kuhn-Tucker method

Solve using Kuhn-Tucker method $ z=x_1^2+x_2^2 $subject to i) $ x_1+x_2\le 4$ ii)$ 2x_1+x_2\le 5$ where $ x_1\ge 0 ,x_2\ge 0$
0
votes
0answers
19 views

Find $\alpha$ from equation $F(\alpha)=\int \left (\frac {I(x)}{\alpha^TG(x)}-1\right)^2 \, dx+\lambda\|\alpha\|^2$

I have a function such as $$F(\alpha)=\int \left (\frac {I(x)}{\alpha^TG(x)}-1\right)^2 \, dx + \lambda \|\alpha\|^2$$ where $I,\lambda,G$ are given. In which $G(x)$ is a vector; $G=[G_1(x), G_2(x), ...
0
votes
0answers
15 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
0
votes
1answer
24 views

How to solve Standard minimization problem of a function

I have a minimization problem here: minimize the cost function C= 12x + 40y +30z subject to x + 2y +2z >= 2 -x - y - 3z >= -1 -x +2y + z >= -2 x >=0 ,y >=0 ,z >=0 So i made the matrix out of ...
1
vote
1answer
110 views

proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

In Proposition 6.4.1 we want to prove that if $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone, then $\text{cl rge}\,A$ and $\text{ri rge}\,A$ are convex. In proof we arrive to the ...
-3
votes
0answers
10 views

How to get attribute weights from a tradeoff? [closed]

Assume that we are getting oranges and apples from a fruit basket, getting apples is seen more important than oranges, and the outcome of x=(0 apple, 25 oranges) is equally preferred as x=(10 apples,0 ...
0
votes
0answers
10 views

Gradient descent derivativ of max function

I need to minimize the function: Sum over all x != t [ max( 0 , C - f(t) + f(x) ) ]; C = constant So you have a set of x-es and one of them is t. I have computed the derivative of the f ...
0
votes
0answers
28 views

Range of feasibility, feasibility interval, allowable increase and allowable decrease.

Can someone please explain how the values (allowable decrease, allowable increase, for constraints) within the blue box (under "Range of Feasibility") are determined? I understand how they determined ...