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
3answers
43 views

ADMM formalization

I found lots of examples of ADMM formalization of equality constraint problems (all with single constraint). I am wondering how to generalize it for multiple constraints with mix of equality and ...
0
votes
1answer
54 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 ...
0
votes
1answer
24 views

Trace minimization-Revised

The problem is as follows: $\displaystyle\min_{V}$ trace($V^TH^T\Phi HV$)$\\$ s.t. $V^TV=I_d$ in the case when $H$ is not known. When $H$ is known, the solution is given by the eigenvectors ...
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)$ ...
0
votes
0answers
31 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 ...
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 ...
1
vote
2answers
46 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
0answers
21 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. ...
0
votes
0answers
21 views

Linear Optimization - functions in constraints?

This is a real-world linear optimization problem. The model tries to minimize cost of hiring employees over a two month period, while providing a certain amount of service. Employees have a salary ...
0
votes
1answer
43 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 ...
1
vote
0answers
29 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
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 ...
0
votes
1answer
48 views

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

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
26 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 ...
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), ...
1
vote
1answer
371 views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
1
vote
0answers
16 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
1answer
25 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 ...
0
votes
1answer
91 views

Optimization of $f\left(x\right)=x^{2}\sin x^{3}$

Let $$f\left(x\right)=x^{2}\sin x^{3}$$ Set of critical points consists of isolated points. Set of critical points is compact $f(x)$ attains local extremum at any critical point ...
11
votes
2answers
301 views

Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES)

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
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
2answers
31 views

Find maximum and minimum of funсtion on set

I have the task: find maximum an minimum of $$f(x) = x_1(\pi - x_1)\sin x_2 + x_2 \cos x_1$$ on X where $$X = \{x\in R^2\ |\ x_1\in [0, \pi], x_2 \ge 0\}.$$ First thing i did was system : ...
0
votes
0answers
12 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
2answers
51 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
6
votes
1answer
71 views

Proving the existence of $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$

Let $n>0$ and $a_1,\ldots,a_n\in \mathbb R$. Prove there is some $b$ such that $\prod_{k=1}^n(1-\cos(a_k-b))=\frac{1}{2^n}$ This is motivated by this question Finding a point on the unit ...
4
votes
4answers
81 views

Minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$ on $[0,\pi]$

Find the minima and maxima of $\left({\frac{\sin 10x}{\sin x}}\right)^2$in the interval $\left [ 0,\pi \right ]$. This is a question from BdMO that still haunts me a lot. I would like to find an ...
0
votes
4answers
35 views

How to find maximum value of trig function?

How to find maximum value of this: $$y = 5\sin x - 12\cos x$$ And I am more intrested in solving process, rather than answer. I know the answer. I am familiar with derivatives, not so good, but as I ...
0
votes
0answers
29 views

Convert a nonconvex function to convex function

I have a image $I: \Omega \to \Bbb R$. It is separated into 2 non-overlapping region: $D$ and $\Omega \setminus D$ Each point $x$ in the image $I$, the $\phi$ function is defined as: $$\phi(x)= ...
0
votes
0answers
42 views
0
votes
0answers
18 views

Terminal Condition in Pontryagin Maximization

I'm doing a time dependent maximization problem using Pontryagin. Now the necessary terminal condition for a solution is only sufficient if my terminal function is concave. If my terminal function is ...
5
votes
4answers
99 views

Maximum value of the integral $\int_0^1e^{|t-x|}dt$ for $0 \leq x \leq 1$

Define $$f(x)=\int_0^1e^{|t-x|}dt$$ I have to find the maximum value of $f(x)$ when $0 \leq x \leq 1$. To remove the modulus, I wrote $$f(x)=\int_0^xe^{x-t}dt + \int_x^1e^{t-x}dt$$ ...
0
votes
0answers
16 views

Justifying the “Dual feasibility”, one of the Karush-Kuhn-Tucker conditions

I am having difficulty of interpreting the KKT conditions in a general setting where we have $M$ equality and $N$ inequality constraints defined as: Minimize $f(x)$ subject to $g_i(x) \leq 0 , h_j(x) ...
0
votes
0answers
18 views

Find the signs of elements in a list such that their sum is equal to zero

I have a set $X = \{x_1, x_2, \dots x_N\} \in [0;1]^N$ containing $N$ elements, initially all positive. My goal is to find a vector of signs $S = \{s_1, s_2, \dots s_N\} \in \{-1; 1\}^N$ such that: ...
0
votes
1answer
16 views

Analysis of iterative optimization methods using lyapunov analysis

In analysis of iterative methods, is it possible that we have to use two time-lagged version of the time-varying system to analyze its convergence? (that is, we construct the evolution of x^k, ...
0
votes
2answers
66 views

Finding the minimum value of a function

Find the least value of $f(x)=3^{-x+1} + e^{-x-1}$. I tried to use the maxima/minima concept but it was of no use. Please help.
4
votes
2answers
145 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
4
votes
1answer
1k views

Mana Maximization (Hearthstone)

I recently started playing Hearthstone and a statistic / probability question came up my mind. Here's a quick breakdown: The game is a turn-based card game which involves "points" that you can used ...
1
vote
2answers
415 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
1
vote
1answer
39 views

Has extremum or not?

I'm learning calculus and I have to do with functions $x^2\sin(\frac{1}{x})$ where x!=0 and 0 when x=0 and $x^3\sin(\frac{1}{x})$ where x!=0 and 0 when x=0 If I computed this well, both of them have ...
0
votes
0answers
10 views

Mixed Integer Linear Program (MILP) question

I am trying to solve an MILP problem. I was wondering if Branch and Cut/Branch and Bound methods find optimal solution or not? Isn't the complexity exponential? Are there heuristic solvers available? ...
0
votes
2answers
31 views

Quite rare kind of proof of convexity for a quadratic function!

Excuse me all of you in advance. I got this problem as an assignment but I am not really good doing proofs! If $f(x)=\frac12x^TQx+b^Tx+a$ is quadratic in $n$ variables, where $Q$ is symmetric. Show ...
0
votes
2answers
860 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
1answer
23 views

Least sum of products of powers

Numbers from the set $\{2^1, 2^2, ..., 2^{10}\}$ are somehow permuted and paired with numbers from the set $\{3^1, 3^2, ..., 3^{10}\}$. Numbers in each pair are multiplied and the products are summed. ...
1
vote
0answers
16 views

Determine min and max of the following expressions

Let $a_1,\; ...\;, a_n$ and $b_1,\; ...\;, b_n\in \mathbb R$ be positive real numbers. Find $$ max \;(a_1x_1 + a_2x_2 + ... + a_nx_n) $$ and $$ min \;(a_1x_1 + a_2x_2 + ... + a_nx_n) $$ over $x_1, ...
0
votes
1answer
25 views

What is the approach to solve simple constrained optimization when first order condition $\nabla f = 0$ yields solution outside of domain

I wish to solve the problem min $ f(x_1, x_2) = x_1^2 - x_1 + x_2 + x_1x_2$ subj $x_1\ge 0, x_2 \ge 0$ We find $\nabla f = [2x_1 - 1 + x_2, 1+x_1] = 0$ yields $x_1 = -1, x_2 = 3$ which is outside ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
0
votes
1answer
437 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
3
votes
2answers
51 views

Finite difference method

I wanted to ask something regarding the finite difference approximation. I used the finite difference to calculate the numerical derivatives of my function. The finite difference is given by the ...
0
votes
0answers
15 views

Optimizing the trace of a matrix product

I have a problem where I have a NxT matrix P (lets just assume full rank for now, where N>>T) and a TxN inclusion matrix S. Each column of S must contain exactly one 1 and the rest 0's i.e. 1_T*S = 1, ...